001package org.clafer.graph;
002
003import java.util.ArrayList;
004import java.util.HashMap;
005import java.util.HashSet;
006import java.util.List;
007import java.util.Map;
008import java.util.Set;
009import java.util.Stack;
010import org.clafer.collection.Counter;
011
012/**
013 *
014 * @author jimmy
015 */
016public class GraphUtil {
017
018    private GraphUtil() {
019    }
020
021    public static <V> boolean hasPath(Vertex<V> start, Vertex<V> end, Graph<V> graph) {
022        Set<Vertex<V>> visited = new HashSet<>();
023        return findPath(start, end, graph, visited);
024    }
025
026    private static <V> boolean findPath(Vertex<V> cur, Vertex<V> end, Graph<V> graph, Set<Vertex<V>> visited) {
027        if (cur.equals(end)) {
028            return true;
029        }
030        if (!visited.add(cur)) {
031            return false;
032        }
033        for (Vertex<V> neighbour : cur.getNeighbours()) {
034            if (findPath(neighbour, end, graph, visited)) {
035                return true;
036            }
037        }
038        return false;
039    }
040
041    /**
042     * Compute the strongly connected components in the graph in topological
043     * order. Implementation of Tarjan's algorithm.
044     *
045     * @param <V>
046     * @param graph
047     * @return the strongly connected components in topological order.
048     * @see <a
049     * href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">Tarjan's
050     * algorithm</a>
051     */
052    public static <V> List<Set<V>> computeStronglyConnectedComponents(Graph<V> graph) {
053        Counter counter = new Counter();
054        Map<Vertex<V>, Index> vertexIndices = new HashMap<>();
055        Stack<Vertex<V>> S = new Stack<>();
056        List<Set<V>> components = new ArrayList<>();
057
058        for (Vertex<V> vertex : graph.getVertices()) {
059            if (!vertexIndices.containsKey(vertex)) {
060                strongConnect(vertex, counter, vertexIndices, S, components);
061            }
062        }
063        return components;
064    }
065
066    private static <V> Index strongConnect(Vertex<V> vertex, Counter counter, Map<Vertex<V>, Index> vertexIndices,
067            Stack<Vertex<V>> S, List<Set<V>> components) {
068        int index = counter.next();
069        Index vertexIndex = new Index(index, index);
070        vertexIndices.put(vertex, vertexIndex);
071
072        S.push(vertex);
073
074        for (Vertex<V> neighbour : vertex.getNeighbours()) {
075            Index neighbourIndex = vertexIndices.get(neighbour);
076            if (neighbourIndex == null) {
077                neighbourIndex = strongConnect(neighbour, counter, vertexIndices, S, components);
078                vertexIndex.setLowIndexMin(neighbourIndex.getLowIndex());
079            } else if (S.contains(neighbour)) {
080                vertexIndex.setLowIndexMin(neighbourIndex.getIndex());
081            }
082        }
083
084        if (vertexIndex.getLowIndex() == vertexIndex.getIndex()) {
085            Set<V> component = new HashSet<>();
086
087            Vertex<V> cycle;
088            do {
089                cycle = S.pop();
090                component.add(cycle.getData());
091            } while (cycle != vertex);
092
093            components.add(component);
094        }
095        return vertexIndex;
096    }
097
098    private static class Index {
099
100        private int index;
101        private int lowIndex;
102
103        Index(int index, int lowIndex) {
104            this.index = index;
105            this.lowIndex = lowIndex;
106        }
107
108        int getIndex() {
109            return index;
110        }
111
112        int getLowIndex() {
113            return lowIndex;
114        }
115
116        void setLowIndexMin(int lowIndex) {
117            if (this.lowIndex >= lowIndex) {
118                this.lowIndex = lowIndex;
119            }
120        }
121    }
122}