In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. Wikipedia
An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. Wikipedia
The strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path. Wikipedia
public void strongConnect(AdjMatrixDirectGraph<T> graph, Vertex<T> start) {
start.index = index;
start.lowval = index;
index++;
stack.push(start);
List<Vertex<T>> neighbors = graph.getNeighbors(start);
for(int i = 0; i < neighbors.size(); i++) {
Vertex<T> neighbor = neighbors.get(i);
if(neighbor.index == null) {
strongConnect(graph, neighbor);
start.lowval = Math.min(start.lowval, neighbor.lowval);
}
else if(stack.contains(neighbor)) {
start.lowval = Math.min(start.lowval, neighbor.index);
}
}
if(start.lowval == start.index) {
List<Vertex<T>> subset = new ArrayList<Vertex<T>>();
Vertex<T> neighbor = null;
while(start != neighbor) {
neighbor = stack.pop();
subset.add(neighbor);
}
set.add(subset);
}
}
}
public List<Edge<T>> findCycle(List<Edge<T>> prefix, Vertex<T> start) {
Stack<Edge<T>> forward =new Stack<Edge<T>>();
Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
Edge<T> e = getUnvisitedEdge(start);
while (e!=null) {
e.visited=true;
forward.push(e);
e = getUnvisitedEdge(e.end);
}
while ( ( !forward.isEmpty() ) ) {
e = forward.pop();
backtrack.push(e);
}
List<Edge<T>> path = new LinkedList<Edge<T>>();
if (prefix!=null) {
for (Edge<T> e1 : prefix) {
path.add(e1);
}
}
while(!backtrack.isEmpty()) {
Edge<T> edge = backtrack.pop();
path.add(edge);
}
return path;
}
Here is the entire source code with a test case:
package com.stones333.algorithm.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
* Find all cycles in DAG
*
* @author stones
*
*/
public class GraphFindCycles {
static private class Vertex<T> {
public T label;
public boolean visited=false;
public Integer index=null;
public Integer lowval=null;
public Vertex(T n) {
this.label=n;
}
@Override
public String toString() {
return "Vertex-" + label;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((label == null) ? 0 : label.hashCode());
result = prime * result + (visited ? 1231 : 1237);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Vertex other = (Vertex) obj;
if (label == null) {
if (other.label != null) return false;
} else if (!label.equals(other.label)) return false;
if (visited != other.visited) return false;
return true;
}
}
static private class Edge<T> {
public Vertex<T> start;
public Vertex<T> end;
public boolean visited=false;
public Edge(Vertex<T> start, Vertex<T> end) {
this.start=start;
this.end=end;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", visited="
+ visited + "]";
}
}
static private interface GraphInterface<T> {
public void addVertex(Vertex<T> n) ;
public boolean isVertexExist(Vertex<T> vertex);
public void addEdge(Vertex<T> start, Vertex<T> end, double weight) ;
public Vertex<T> getUnvisitedChildren(Vertex<T> n);
}
static private abstract class Graph<T> implements GraphInterface<T> {
//DFS traversal of a tree is performed by the dfs() function
public void dfs(Vertex<T> start) {
//DFS uses Stack data structure
Stack<Vertex<T>> stack =new Stack<Vertex<T>>();
start.visited=true;
stack.push(start);
printNode(start);
while(!stack.isEmpty()) {
Vertex<T> n= stack.peek();
Vertex<T> child=getUnvisitedChildren(n);
if(child!=null) {
child.visited=true;
stack.push(child);
printNode(child);
} else {
stack.pop();
}
}
}
//BFS traversal of a graph is performed by the bfs() function
public void bfs(Vertex<T> start)
{
//BFS uses Queue data structure
Queue<Vertex<T>> que=new LinkedList<Vertex<T>>();
start.visited=true;
que.add(start);
printNode(start);
while(!que.isEmpty()) {
Vertex<T> n=(Vertex<T>)que.remove();
Vertex<T> child=null;
while((child=getUnvisitedChildren(n))!=null) {
child.visited=true;
que.add(child);
printNode(child);
}
}
}
public void printNode(Vertex<T> n) {
System.out.print(n.label+" ");
}
}
static public class DirectedGraphFindAllPath<T> {
List<Edge<T>> edges=new ArrayList<Edge<T>>();
List<Vertex<T>> vetexes=new ArrayList<Vertex<T>>();
public DirectedGraphFindAllPath (StronglyConnectedTarjan<T> scc, Vertex<T> start) {
List<WeightedEdge<T>> edges = scc.findStrongConnectEdges (start);
for (WeightedEdge<T> edge : edges ) {
this.addEdge(edge.start, edge.end);
}
}
public DirectedGraphFindAllPath<T> addVetex(Vertex<T> n) {
vetexes.add(n);
return this;
}
public boolean isVetexExist(Vertex<T> vetex) {
return ( vetexes.indexOf(vetex) >=0 ) ;
}
public boolean isAllEdgeVisited() {
for (Edge<T> e : edges) {
if (! e.visited) return false;
}
return true;
}
public List<List<Edge<T>>> findCycles(Vertex<T> start) {
List<List<Edge<T>>> pathes = new LinkedList<List<Edge<T>>>();
List<Edge<T>> cycle = findCycle(null, start);
pathes.add(cycle);
List<Edge<T>> current = new LinkedList<Edge<T>>();
for (Edge<T> edge : cycle ) {
current.add(edge);
if ( hasUnvisitedEdge (edge.end) ) {
List<Edge<T>> p = findCycle(current, edge.end);
pathes.add(p);
}
}
return pathes;
}
/**
* The key of the algorithm is to have two stacks,
* the first one is for storing the forward path and the other is for backtracking.
* The backtracking is needed to cover unvisited edges for vertexes with multiple edges.
*
* @param prefix
* @param start
* @return
*/
public List<Edge<T>> findCycle(List<Edge<T>> prefix, Vertex<T> start) {
Stack<Edge<T>> forward =new Stack<Edge<T>>();
Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
Edge<T> e = getUnvisitedEdge(start);
while (e!=null) {
e.visited=true;
forward.push(e);
e = getUnvisitedEdge(e.end);
}
while ( ( !forward.isEmpty() ) ) {
e = forward.pop();
backtrack.push(e);
}
List<Edge<T>> path = new LinkedList<Edge<T>>();
if (prefix!=null) {
for (Edge<T> e1 : prefix) {
path.add(e1);
}
}
while(!backtrack.isEmpty()) {
Edge<T> edge = backtrack.pop();
path.add(edge);
}
return path;
}
/**
* 1. Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v.
* It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that,
* when the trail enters another vertex w there must be an unused edge leaving w.
* The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
*
* 2. As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour,
* start another trail from v, following unused edges until returning to v,
* and join the tour formed in this way to the previous tour.
*
* @param start
* @return
*/
public List<Edge<T>> findHierholzerPath(Vertex<T> start) {
Stack<Edge<T>> forward =new Stack<Edge<T>>();
Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
Edge<T> e = getUnvisitedEdge(start);
while (e!=null) {
e.visited=true;
forward.push(e);
e = getUnvisitedEdge(e.end);
}
while ( ( !forward.isEmpty() ) ) {
e = forward.pop();
backtrack.push(e);
e = getUnvisitedEdge(e.start);
while (e!=null) {
e.visited = true;
forward.push(e);
e = getUnvisitedEdge(e.end);
}
}
List<Edge<T>> path = new LinkedList<Edge<T>>();
while(!backtrack.isEmpty()) {
Edge<T> edge = backtrack.pop();
path.add(edge);
}
return path;
}
public void printPath(List<Edge<T>> path) {
for (int i=0; i<path.size(); i++) {
System.out.print(path.get(i).start.label + "->" + path.get(i).end.label + " ");
}
}
public List<Edge<T>> findHierholzerPath(Vertex<T> start, Vertex<T> end) {
List<Edge<T>> path = findHierholzerPath(start);
if (path==null || path.size()==0) {
System.out.println ("No Eulerian path found!");
} else {
if ( path.get(path.size()-1).end == end ) {
System.out.println ("Eulerian path found:");
this.printPath(path);
} else {
System.out.println ("No Eulerian path found!");
}
}
return path;
}
//This method will be called to make connect two nodes
public DirectedGraphFindAllPath<T> addEdge(Vertex<T> start, Vertex<T> end, int weight ) {
if ( ! isVetexExist(start) ) addVetex(start);
if ( ! isVetexExist(end) ) addVetex(end);
Edge<T> edge = new Edge<T>(start, end);
edges.add(edge);
return this;
}
//This method will be called to make connect two nodes
public DirectedGraphFindAllPath<T> addEdge(Vertex<T> start, Vertex<T> end) {
if ( ! isVetexExist(start) ) addVetex(start);
if ( ! isVetexExist(end) ) addVetex(end);
Edge<T> edge = new Edge<T>(start, end);
edges.add(edge);
return this;
}
public Vertex<T> getUnvisitedChildren(Vertex<T> n) {
for (Edge<T> e : edges) {
if ( e.visited==false && e.start.equals(n) ) {
e.visited=true;
return e.end;
}
}
return null;
}
public boolean hasUnvisitedEdge(Vertex<T> n) {
for (Edge<T> e : edges) {
if ( e.visited==false && e.start.equals(n) ) {
return true;
}
}
return false;
}
public Edge<T> getUnvisitedEdge(Vertex<T> n) {
for (Edge<T> e : edges) {
if ( e.visited==false && e.start.equals(n) ) {
e.visited=true;
return e;
}
}
return null;
}
public void clearNodes() {
for ( Edge<T> e : edges)
e.visited=false;
for ( Vertex<T> v : vetexes)
v.visited=false;
}
}
static private class AdjMatrixDirectGraph<T> extends Graph<T> implements GraphInterface<T> {
public ArrayList<Vertex<T>> vertexes=new ArrayList<Vertex<T>>();
public double[][] adjMatrix;
public void addVertex(Vertex<T> n) {
vertexes.add(n);
}
public boolean isVertexExist(Vertex<T> vertex) {
return ( vertexes.indexOf(vertex) >=0 ) ;
}
public List<Vertex<T>> getVertexes () {
return vertexes;
}
public void addEdge(Vertex<T> start, Vertex<T> end) {
addEdge(start, end, 1);
}
//This method will be called to make connect two nodes
public void addEdge(Vertex<T> start, Vertex<T> end, double weight) {
if ( ! isVertexExist(start) ) addVertex(start);
if ( ! isVertexExist(end) ) addVertex(end);
if ( initAdjMatrix() ) {
int startIndex=vertexes.indexOf(start);
int endIndex=vertexes.indexOf(end);
if (startIndex>=0 && endIndex>=0) {
adjMatrix[startIndex][endIndex]=weight;
}
}
}
public boolean initAdjMatrix() {
if (vertexes.size()<=0) return false;
adjMatrix=buildAdjMatrix(adjMatrix, vertexes.size());
return true;
}
private double [][] buildAdjMatrix(double[][] prevMatrix, int newSize) {
if (newSize==0) return null;
double[][] matrix=new double[newSize][newSize];
for (int i=0; i<newSize; i++)
for (int j=0; j<newSize; j++)
matrix[i][j] = Double.POSITIVE_INFINITY;
if (prevMatrix!=null) {
for (int i=0; i<prevMatrix.length; i++)
for (int j=0; j<prevMatrix[i].length; j++)
matrix[i][j] = prevMatrix[i][j];
}
return matrix;
}
public List<Vertex<T>> getNeighbors(Vertex<T> n) {
List<Vertex<T>> list = new ArrayList <Vertex<T>>();
int index=vertexes.indexOf(n);
for (int j=0; j<vertexes.size(); j++) {
if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY ) {
list.add((Vertex<T>)vertexes.get(j));
}
}
return list;
}
public Vertex<T> getUnvisitedChildren(Vertex<T> n) {
int index=vertexes.indexOf(n);
int j=0;
while(j<vertexes.size()) {
if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY && vertexes.get(j).visited==false ) {
return (Vertex<T>)vertexes.get(j);
}
j++;
}
return null;
}
public List<WeightedEdge<T>> getEdges(Vertex<T> n) {
List<WeightedEdge<T>> edges = new LinkedList<WeightedEdge<T>>();
int index=vertexes.indexOf(n);
int j=0;
while(j<vertexes.size()) {
if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY ) {
edges.add(new WeightedEdge<T> (n, vertexes.get(j), adjMatrix[index][j]) );
}
j++;
}
return edges;
}
public List<WeightedEdge<T>> getEdges() {
List<WeightedEdge<T>> edges = new LinkedList<WeightedEdge<T>>();
for (int i=0; i<adjMatrix.length; i++) {
for (int j=0; j<adjMatrix[i].length; j++) {
if( adjMatrix[i][j]!=Double.POSITIVE_INFINITY ) {
edges.add(new WeightedEdge<T> (vertexes.get(i), vertexes.get(j), adjMatrix[i][j]) );
}
}
}
return edges;
}
public void printVertexes() {
for (int i=0; i<vertexes.size(); i++ ) {
System.out.print(vertexes.get(i) + " " );
}
System.out.println();
}
//Utility methods for clearing visited property of node
public void clearNodes() {
int i=0;
while(i<vertexes.size()) {
vertexes.get(i).visited=false;
i++;
}
}
}
static private class WeightedEdge<T> extends Edge<T> {
public final double weight;
public boolean visited=false;
public WeightedEdge(Vertex<T> start, Vertex<T> end, double weight) {
super(start, end);
this.weight=weight;
}
public int compareTo(WeightedEdge<T> that) {
if (this.weight < that.weight)
return -1;
else if (this.weight > that.weight)
return +1;
else
return 0;
}
@Override
public String toString() {
return "WeightedEdge [start=" + start + ", end=" + end
+ ", weight=" + weight + ", visited=" + visited + "]";
}
}
static public class StronglyConnectedTarjan<T> {
public AdjMatrixDirectGraph<T> graph;
public int index;
public Stack<Vertex<T>> stack;
public List<List<Vertex<T>>> set;
public void printConnected () {
for(int i = 0; i < set.size(); i++) {
System.out.println("Set " + i + ": " + Arrays.toString(set.get(i).toArray()));
}
}
public StronglyConnectedTarjan(AdjMatrixDirectGraph<T> graph) {
this.graph = graph;
stack = new Stack<Vertex<T>> ();
set = new ArrayList<List<Vertex<T>>> ();
for( Vertex<T> node : graph.vertexes) {
if(node.index == null)
strongConnect(graph, node);
}
}
public List<WeightedEdge<T>> findStrongConnectEdges (Vertex<T> node) {
List<WeightedEdge<T>> edges = new ArrayList<WeightedEdge<T>>();
for (List<Vertex<T>> c : set) {
if ( c.contains(node) ) {
for (int i=0; i<graph.adjMatrix.length; i++) {
for (int j=0; j<graph.adjMatrix[i].length; j++) {
if( graph.adjMatrix[i][j]!=Double.POSITIVE_INFINITY
&& c.contains(graph.vertexes.get(i))
&& c.contains(graph.vertexes.get(j)) ) {
edges.add(new WeightedEdge<T> (graph.vertexes.get(i), graph.vertexes.get(j), graph.adjMatrix[i][j]) );
}
}
}
}
}
return edges;
}
/**
*
* 1. Start from any arbitrary vertex.
*
* 2. DFS from that vertex. For each node x, keep two numbers, dfs_index[x] and dfs_lowval[x].
* dfs_index[x] stores when that node is visited, while dfs_lowval[x] = min( dfs_low[k]) where
* k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
*
* 3. All nodes with the same dfs_lowval[x] are in the same strongly connected component.
*
* @param graph
* @param start
*/
public void strongConnect(AdjMatrixDirectGraph<T> graph, Vertex<T> start) {
start.index = index;
start.lowval = index;
index++;
stack.push(start);
List<Vertex<T>> neighbors = graph.getNeighbors(start);
for(int i = 0; i < neighbors.size(); i++) {
Vertex<T> neighbor = neighbors.get(i);
if(neighbor.index == null) {
strongConnect(graph, neighbor);
start.lowval = Math.min(start.lowval, neighbor.lowval);
}
else if(stack.contains(neighbor)) {
start.lowval = Math.min(start.lowval, neighbor.index);
}
}
if(start.lowval == start.index) {
List<Vertex<T>> subset = new ArrayList<Vertex<T>>();
Vertex<T> neighbor = null;
while(start != neighbor) {
neighbor = stack.pop();
subset.add(neighbor);
}
set.add(subset);
}
}
}
public static void main(String[] args) {
System.out.println("testFindCycle -->");
testFindCycle();
}
private static void testFindCycle() {
Vertex<String> nA = new Vertex<String>("A");
Vertex<String> nB = new Vertex<String>("B");
Vertex<String> nC = new Vertex<String>("C");
Vertex<String> nD = new Vertex<String>("D");
Vertex<String> nE = new Vertex<String>("E");
Vertex<String> nF = new Vertex<String>("F");
Vertex<String> nG = new Vertex<String>("G");
Vertex<String> nH = new Vertex<String>("H");
//Create the graph, add nodes, create edges between nodes
AdjMatrixDirectGraph<String> g=new AdjMatrixDirectGraph<String>();
g.addEdge(nA, nB); g.addEdge(nB, nC); g.addEdge(nC, nA); g.addEdge(nB, nA);
g.addEdge(nD, nB); g.addEdge(nD, nC); g.addEdge(nD, nF);
g.addEdge(nF, nD); g.addEdge(nE, nC);
g.addEdge(nE, nG); g.addEdge(nG, nE);
g.addEdge(nH, nF); g.addEdge(nH, nH);
StronglyConnectedTarjan<String> scc = new StronglyConnectedTarjan<String>(g);
// scc.printConnected();
// List<WeightedEdge<String>> edges = scc.findStrongConnectEdges (nA);
// for (WeightedEdge<String> e: edges) {
// System.out.println(e);
// }
DirectedGraphFindAllPath<String> findCycle = new DirectedGraphFindAllPath<String> (scc, nA);
List<List<Edge<String>>> pathes = findCycle.findCycles(nA);
for (List<Edge<String>> path : pathes) {
System.out.println("");
System.out.print("cycle: ");
findCycle.printPath(path);
}
}
}
The graph edges are
(nA, nB), (nB, nC), (nC, nA), addEdge(nB, nA); (nD, nB), (nD, nC), (nD, nF); (nF, nD), (nE, nC), (nE, nG); (nG, nE), (nH, nF), (nH, nH);
The output:
cycle: A->B B->A cycle: A->B B->C C->A
Enjoy the journey, have fun.
