Remove cycle in directed graph and convert graph to tree – code

A graph is a data structure that consists of a set of vertices (aka nodes) connected by edges. A graph is cyclic if the graph comprises a path that starts from a vertex and ends at the same vertex. A tree is a simple graph with no cycle. In theory, we can convert graph to tree by remove the cycle in graph.

But it’s much harder to do than to say. Please refer to Find the Simple Cycles in a Directed Graph By Donald B.Johnson. After finding nodes in cycle, we can remove one or more edges in the cycle.

In this post, we give simplified examples to demonstrate how to convert graph to tree. In these two examples, we guarantee there is only one cycle in the graph. And we can remove one edge to convert graph to tree.

First we build a directed graph. There we two ways to build graph. The first example uses pre-defined Graph class. We call GraphNode and Graph class directly. The second example is a simplified version. We build graph by calling addEdge(). Next we use DFS (Depth first search) to detect cycle in directed graph. If there is cycle, we remove one edge in the cycle. Finally we can display the tree in three ways:
(1) adjacent list of graph.
(2) hierarchy view of tree.
(3) Pre-order of the tree.


I. Detect cycle in directed graph and remove cycle

Facebook Interview Question (CareerCup):
class DirectedGraphNode {
int label;
List neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
}
check if there is a cycle in a directed graph, if there is a cycle, remove the cycle.

Java Code:

Output:
cycle:[0, 1, 2]

Graph Adjacent list:
[]
[2 ]
[0 , 3 ]
[]

O Notation:
Time complexity: O(V+E)
Space complexity: O(V)
V is number of vertices, E is number of edges.


II. Class dependencies and convert graph to tree

Question statement(github):
Writing a program that accepts information about the class dependencies in a Java program and creates a directed graph from that information. From the directed graph, convert to a tree and produce two different kinds of displays of those dependency relationships.

A sample input data is shown below:
ClassA ClassC ClassE ClassJ
ClassB ClassD ClassG
ClassC ClassA
ClassE ClassB ClassF ClassH
ClassJ ClassB
ClassI ClassC

The first name of each line is a Java class upon which other classes depend. The remaining names are the classes that depend upon the first class on that line. Create a class DirectedGraph, should be a generic class, whose generic parameter specifies the type of the labels that are associated with the vertices of the graph. The internal representation of the graph should be the adjacency list. this graph will not be a weighted graph.

Implement method to detect and remove the cycle so that you can convert the graph to tree . As output, print the tree as hierarchy list and parenthesized list.

The hierarchical representation is shown below:
ClassA
 ClassC
 ClassE
  ClassB
   ClassD
   ClassG
  ClassF
  ClassH
 ClassJ
  ClassB
   ClassD
   ClassG

The pre-order of the tree with nested parentheses is shown blow:
( ClassA ( ClassC ClassE ( ClassB ( ClassD ClassG ) ClassF ClassH ) ClassJ ( ClassB ( ClassD ClassG ))))

Java Code of DirectedGraph

Output:
Graph Adjacent list:
ClassA [ClassC, ClassE, ClassJ]
ClassB [ClassD, ClassG]
ClassC []
ClassD []
ClassE [ClassB, ClassF, ClassH]
ClassF []
ClassG []
ClassH []
ClassI [ClassC]
ClassJ [ClassB]

Java Code of HierarchyTree:

Output:
Hierarchy list:
ClassA
 ClassC
 ClassE
  ClassB
   ClassD
   ClassG
  ClassF
  ClassH
 ClassJ
  ClassB
   ClassD
   ClassG
Pre-order:
( ClassA ( ClassC ClassE ( ClassB ( ClassD ClassG ) ClassF ClassH ) ClassJ ( ClassB ( ClassD ClassG ) ) ) )

Note:
Please click the download button to download the both projects(Graph.java included).

Recommended:
Download graphToTree.zip
The complete list of coding interview questions

Comments are closed