Created
August 6, 2016 16:01
-
-
Save tareq-si-salem/548d2c1fb972ac4ac8f55a465cfe38c9 to your computer and use it in GitHub Desktop.
DiGraph class definition (adjacency list) with depth first search results
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Scanner; | |
public class DiGraph { | |
public int[] vertices; | |
public ArrayList<Integer> adjacencyList[]; | |
private boolean[] explored, visited; | |
public int dfs_numbers[]; | |
public ArrayList<Edge> treeEdges = new ArrayList<>(); | |
public ArrayList<Edge> forwardEdges = new ArrayList<>(); | |
public ArrayList<Edge> backEdges = new ArrayList<>(); | |
public ArrayList<Edge> crossEdges = new ArrayList<>(); | |
boolean planarLayout; | |
public DiGraph() { | |
Scanner s = new Scanner(System.in); | |
System.out.print("Planar Layout: "); | |
planarLayout = s.nextBoolean(); | |
System.out.print("Start vertex: "); | |
int start = s.nextInt(); | |
init(s); | |
dfs(start); | |
for (int u = 0; u < dfs_numbers.length; u++) { | |
if (dfs_numbers[u] == 0) { | |
// this node hasn't been visited | |
// edges going out from this node are | |
// cross edges | |
dfs_numbers[u] = nbr++; | |
for (Integer v : adjacencyList[u]) { | |
crossEdges.add(new Edge(u, v)); | |
} | |
} | |
} | |
} | |
private void init(Scanner s) { | |
System.out.print("Enter vertices number: "); | |
int verticesNbr = s.nextInt(); | |
vertices = new int[verticesNbr]; | |
adjacencyList = new ArrayList[verticesNbr]; | |
explored = new boolean[verticesNbr]; | |
visited = new boolean[verticesNbr]; | |
dfs_numbers = new int[verticesNbr]; | |
for (int u = 0; u < vertices.length; u++) { | |
adjacencyList[u] = new ArrayList<>(); | |
vertices[u] = u; | |
System.out.printf("Enter vertices adjacent to node %d [-1 to stop ]: ", u); | |
int v; | |
while ((v = s.nextInt()) != -1) { | |
adjacencyList[u].add(v); | |
} | |
} | |
} | |
int nbr = 1; | |
private void dfs(int u) { | |
visited[u] = true; | |
dfs_numbers[u] = nbr++; | |
adjacencyList[u].stream().forEach((Integer v) -> { | |
Edge edge = new Edge(u, v); | |
if (!visited[v]) { | |
treeEdges.add(edge); | |
dfs(v); | |
} else if (dfs_numbers[u] < dfs_numbers[v]) { | |
forwardEdges.add(edge); | |
} else if (!explored[v]) { | |
backEdges.add(edge); | |
} else { | |
crossEdges.add(edge); | |
} | |
}); | |
explored[u] = true; | |
} | |
@Override | |
public String toString() { | |
String definition = "Graph:" | |
+ "\n" | |
+ "Vertices: " + Arrays.toString(vertices) | |
+ "\n" | |
+ "AdjacencyLists: " | |
+ "\n"; | |
for (ArrayList<Integer> lists : adjacencyList) { | |
definition += lists.toString() + "\n"; | |
} | |
definition += "Tree Edges: " + treeEdges.toString() + "\n"; | |
definition += "Forward Edges: " + forwardEdges.toString() + "\n"; | |
definition += "Back Edges: " + backEdges.toString() + "\n"; | |
definition += "Cross Edges: " + crossEdges.toString() + "\n"; | |
definition += "DFS Numbers: \n"; | |
for (int i = 0; i < dfs_numbers.length; i++) { | |
definition += i + "\t" + dfs_numbers[i] + "\n"; | |
} | |
return definition; | |
} | |
} | |
class Edge { | |
int u, v; | |
public Edge(int u, int v) { | |
this.u = u; | |
this.v = v; | |
} | |
@Override | |
public String toString() { | |
return String.format("<%d, %d>", u, v); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment