Skip to content

Instantly share code, notes, and snippets.

@tareq-si-salem
Created August 6, 2016 16:01
Show Gist options
  • Save tareq-si-salem/548d2c1fb972ac4ac8f55a465cfe38c9 to your computer and use it in GitHub Desktop.
Save tareq-si-salem/548d2c1fb972ac4ac8f55a465cfe38c9 to your computer and use it in GitHub Desktop.
DiGraph class definition (adjacency list) with depth first search results
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