write code in Java that reads a (any) text file of adjacency lists for a *direct

Question

write code in Java that reads a (any) text file of adjacency lists for a *directed graph*; for example,

D,A,B

A,B

B,C

As you know, this means that

D is connected to A

D is connected to B

A is connected to B

B is connected to C

The output of your code should be D,A,B,C; which is the topological ordering for the graph.

Use the linear algorithm described in the slides: Find node/vertex with 0 in-bound edges (in degree 0)

Remove that element (with its out-bound degrees) Repeat.

You will (most likely) need to use dictionaries to decrement the number of inbound edges in O(1), refer to the Java files provided earlier; also, you will probably need to use a queue to queue the nodes with 0 inbound edges; you can use the Java implementation of queues.

Lastly, if you encounter a cycle, print that there isn't a topological ordering for the graph.

Please and thank you for your help.

Explanation / Answer

import java.util.*;

public class Q004_Topological_Sorting {

static class Graph {
int V;
List[] lists;

Graph(int x) {
V = x;
lists = new List[V];

// Initialize each adjacency list as empty by making head as NULL
for (int i = 0; i < V; i++) {
lists[i] = new List();
}
}

// Add edge
void addEdge(int u, int v) {
List list;
// directed graph
list = lists[u];
list.addNode(v);
}

void print() {
for (int i = 0; i < V; i++) {
List list = lists[i];
System.out.format("%d: ", i);
list.print();
}
}

void topologicalSort() {
Stack<Integer> stack = new Stack();

// Mark all the vertices as not visited
boolean[] visited = new boolean[V];

// Call the recursive helper function to store Topological Sort
    // starting from all vertices one by one
for (int i = 0; i < V; i++) {
topologicalHelper(i, visited, stack);
}

// print contents of stack
while (!stack.isEmpty()) {
System.out.format("%d ", stack.pop());
}
}

void topologicalHelper(int i, boolean[] visited, Stack<Integer> stack) {
if (visited[i]) {
return;
}

// Mark the current node as visited
visited[i] = true;

// Recur for all the vertices adjacent to this vertex
ListNode p = lists[i].head;
while (p != null) {
if (visited[p.index] == false) {
topologicalHelper(p.index, visited, stack);
}
p = p.next;
}

// Push current vertx to stack with stores result
stack.push(i);
}
}

// Adjacency list
static class List {
ListNode head;

List() {
head = null;
}

void addNode(int x) {
ListNode node = new ListNode(x);
node.next = head;
head = node;
}

void print() {
ListNode p = head;
while (p != null) {
System.out.format("%d", p.index);
p = p.next;
if (p != null) {
System.out.format(" -> ");
}
}
System.out.println();
}
}

// Adjacency list node
static class ListNode {
int index;
ListNode next;

ListNode(int d) {
index = d;
next = null;
}
}

public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);

graph.print();

System.out.format("Following is a Topological Sort of the given graph ");
graph.topologicalSort();
}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.