I have an undirected graph which gets loaded as an adjacency matrix. I have a method to detect a cycle in a graph using BFS algorithm. What I am trying to achieve is to print all the edges in a way that they indicate a cycle which has been found.
I am able to print all the edges in a graph, but I am unable to print only those edges which create a cycle. How do I make it work?
Here is the graph implementation:
Edge:
public class Edge {
int source, dest;
public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}
Graph:
public class Graph {
// A List of Lists to represent an adjacency list
// Each insideList contains pointers to the next vertex
// list with an index of 1 (vertex 1) contains elements 2 and 3 (where 2, 3 are vertices connected to 1)
List<List<Integer>> adjList = null;
// Constructor
public Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge : edges) {
int src = edge.source;
int dest = edge.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
Node:
public class Node {
int v, parent;
public Node(int v, int parent) {
this.v = v;
this.parent = parent;
}
}
Algorithm and test:
public class GraphTest {
// Perform BFS on graph starting from vertex src and
// returns true if cycle is found in the graph
// while traversing the graph, it should display the edges which create a cycle, but I am unable to do it (the result is wrong)
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
boolean[] discovered = new boolean[N];
// mark source vertex as discovered
discovered[src] = true;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(src, -1));
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (!discovered[u]) {
// mark it as discovered
discovered[u] = true;
// construct the queue node containing info
// about vertex and push it into the queue
System.out.println(node.v + " -- " + u);
q.add(new Node(u, node.v));
}
// u is discovered and u is not a parent
else if (u != node.parent) {
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
// Check if an undirected graph contains cycle or not
public static void main(String[] args) {
// In my case I load an adjacency matrix from file and then perform an action to create Edges.
// 0 1 1 0
// 1 0 1 0
// 1 1 0 1
// 0 0 1 0
// Edge(1, 2), Edge(2, 3), Edge(3, 1), Edge(3, 4)
// Edge(3, 1) introduces a cycle in the graph
List<Edge> edges = new ArrayList<Edge>();
ArrayList<ArrayList<Integer>> matrixList = loadFromFile(filePath);
System.out.println("Graph: (Adjacency Matrix)");
for (int i = 0; i < matrixList.size(); i++) {
for (int j = 0; j < matrixList.size(); j++) {
System.out.print(matrixList.get(i).get(j) + " ");
}
System.out.println();
}
System.out.println("All the edges: ");
for (int i = 0; i < matrixList.size(); i++) {
// ' + 1' is added so as to start vertices from 1 instead of 0
int temp = i + 1;
for (int j = 0; j < matrixList.size(); j++) {
if (matrixList.get(i).get(j) == 1) {
System.out.println(temp + "--" + (j + 1) + " ");
// each edge is added one-way only since it is an undirected graph
// if Edge(1,3) is already present, Edge(3,1) is not added
boolean isFound = false;
for (Edge e : edges) {
if (e.dest == temp && e.source == (j + 1)) {
isFound = true;
}
}
if (!isFound)
edges.add(new Edge(temp, j + 1));
}
}
System.out.println();
}
// sets number of vertices in the graph
final int N = 5;
// creates a graph from edges
Graph graph = new Graph(edges, N);
boolean[] discovered = new boolean[N];
// do BFS traversal in connected components of graph
System.out.println("Detect a cycle: ");
if (BFS(graph, 1, N))
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain any cycle");
}
Input: an adjacency matrix (or a prebuilt list of edges)
Current wrong output: displays some edges, but not all the edges of a cycle
Expected output: to print all the edges which create a cycle, as shown in an example above,
I would like to display: 1--2, 2--3, 3--1
The ending vertex of one edge is a starting vertex of another edge in a cycle.
I'm not claiming this is the best way to achieve the result, but it's one of the ways.
First of all, I'd change the definition of your Node:
public class Node {
int v;
Node parent;
public Node(int v, Node parent) {
this.v = v;
this.parent = parent;
}
}
Then in your method BFS, I'd change the boolean array discovered to Node array, so you know, which path leads to this Node.
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
Your BFS method would work then like this:
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
// mark source vertex as discovered
Node start = new Node(src, null);
discovered[src] = start;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new LinkedList<>();
q.add(start);
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (discovered[u] == null) {
// mark it as discovered
Node newNode = new Node(u, node);
discovered[u] = newNode;
// construct the queue node containing info
// about vertex and push it into the queue
q.add(newNode);
}
// u is discovered and u is not a parent
else if (u != node.parent.v) {
Node newNode = new Node(u, node);
int commonParent = findCommonParent(discovered[u], newNode);
String result = "";
Node current;
current = discovered[u];
while(current.v != commonParent) {
result = current.parent.v + "--" + current.v + ", " + result;
current = current.parent;
}
current = newNode;
while(current.v != commonParent) {
result = result + current.v + "--" + current.parent.v + ", ";
current = current.parent;
}
result = result.substring(0, result.length() - 2);
System.out.println(result);
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
The method findCommonParent can be implemented for example like this:
private static int findCommonParent(Node n1, Node n2) {
Set<Integer> n1Parents = new HashSet<Integer>();
Node temp = n1.parent;
while(temp != null) {
n1Parents.add(temp.v);
temp = temp.parent;
}
temp = n2.parent;
while(temp != null) {
if(n1Parents.contains(temp.v)) {
break;
}
temp = temp.parent;
}
return temp.v;
}