Implement the Topological sort algorithm using the Graph class defined in the program.

There is line 125an empty function definition in the program (line 125). There is a comment describing the algorithm implementation in pseudo-code.

This program implements a graph data structure and implements a Depth First Search (DFS) algorithm. This is intended to serve as an example of how to use the graph structure:

import java.util.ArrayList;

//-------------------------------------------------------------

// One Node in the Graph

//

class Node

{

public Node(String name)

{

this.name = name;

}

public String name;

public boolean visited = false;

public ArrayList out_edge_list = new ArrayList<>();

public String toString(){ return name; }

}

//-------------------------------------------------------------

// A Directed Edge in the Graph

//

class Edge

{

public Edge(String name, double weight, Node from, Node to)

{

this.name = name;

this.weight = weight;

this.from = from;

this.to = to;

}

public String toString(){ return name + ": " + from + " " + to; }

public String name;

public double weight;

public Node from;

public Node to;

}

//-------------------------------------------------------------

// A Directed Graph of Nodes and Edges

//

class Graph

{

public ArrayList node_list = new ArrayList<>();

public ArrayList edge_list = new ArrayList<>();

//----------------------------------------------------------

// Initialize a graph (State before DFS performed)

//

public void init_graph()

{

for(Node n : node_list) n.visited = false;

}

//----------------------------------------------------------

// Find a Node by Node name

//

public int find_node_index(String name)

{

for(int i = 0; i < node_list.size(); ++i)

if (node_list.get(i).name.equals(name)) return i;

return -1;

}

public Node find_node(String name)

{

for(Node n : node_list)

if (n.name.equals(name)) return n;

return null;

}

//----------------------------------------------------------

// Add a new edge ( and possibly new nodes) to the graph.

//

public void add_edge(String name, double weight, String node_name_from, String node_name_to)

{

Node node_from, node_to;

if ((node_from = find_node(node_name_from)) == null)

node_list.add(node_from = new Node(node_name_from));

if ((node_to = find_node(node_name_to)) == null)

node_list.add(node_to = new Node(node_name_to));

Edge new_edge = new Edge(name, weight, node_from, node_to);

edge_list.add(new_edge);

node_from.out_edge_list.add(new_edge);

}

//----------------------------------------------------------

// Describe a Graph

//

public String toString()

{

String s = " Nodes --------------- ";

for(Node n : node_list)

{

s += n + " " + n.visited + " ";

}

s += " Edges --------------- ";

for(Edge e : edge_list)

{

s += e + " ";

}

return s;

}

//----------------------------------------------------------

// Depth First Search (DFS)

//

public void dfs(String node_name)

{

System.out.println(" DFS Source Node: " + node_name + " -------------------- ");

init_graph();

dfs(find_node(node_name));

}

private void dfs(Node n)

{

System.out.println("Visiting Node " + n);

n.visited = true;

for (Edge e : n.out_edge_list)

if (e.to.visited == false)

{

System.out.println("\tFollow Edge " + e);

dfs(e.to);

System.out.println("\tReverse Edge " + e);

}

System.out.println("Backup From " + n);

}

//----------------------------------------------------------

// Topological Sort

//

public boolean top_sort()

{

/*

Initialize all Nodes as unvisited, and

all Node in_counts to zero (add a data member

in_counts to the Node class, and set it to zero

in the init_graph() method)

NOTE: you may want to add local variables to count

how many nodes have been visited, and to check if

the if statement was ever true. (You could do this

by initializing a Node variable node_found to null,

then if a Node n is found meeting the if test,

node_found = n. When the for loop exits the while

can test if node_found is still null).

do

for each Node n in the graph

if n is unvisited and it's in_count is zero

print n

mark n as visited

for each Edge e outgoing from n

decrement in_count of the "to" Node

break out of the for loop

while the if statement was true

if all the nodes have been visited

return true

else

return false

*/

return false;

}

}

//-------------------------------------------------------------

// Main. Performs DFS for graph in image topo_07.png

//

class Graph_DFS_Top_0

{

public static void main(String[] args) throws Exception

{

Graph g = new Graph();

g.add_edge("14", 1.0, "1", "4");

g.add_edge("15", 1.0, "1", "5");

g.add_edge("23", 1.0, "2", "3");

g.add_edge("24", 1.0, "2", "4");

g.add_edge("34", 1.0, "3", "4");

g.add_edge("36", 1.0, "3", "6");

g.add_edge("38", 1.0, "3", "8");

g.add_edge("45", 1.0, "4", "5");

g.add_edge("57", 1.0, "5", "7");

g.add_edge("59", 1.0, "5", "9");

g.add_edge("67", 1.0, "6", "7");

g.add_edge("79", 1.0, "7", "9");

g.add_edge("89", 1.0, "8", "9");

System.out.println(g);

g.dfs("1");

g.dfs("2");

if (g.top_sort())

System.out.print(" Sort Complete ");

else

System.out.print(" Graph COntains a Cycle ");

g = new Graph();

g.add_edge("14", 1.0, "1", "4");

g.add_edge("15", 1.0, "1", "5");

g.add_edge("23", 1.0, "2", "3");

g.add_edge("24", 1.0, "2", "4");

g.add_edge("34", 1.0, "3", "4");

g.add_edge("36", 1.0, "3", "6");

g.add_edge("38", 1.0, "3", "8");

g.add_edge("45", 1.0, "4", "5");

g.add_edge("57", 1.0, "5", "7");

g.add_edge("95", 1.0, "9", "5");

g.add_edge("67", 1.0, "6", "7");

g.add_edge("79", 1.0, "7", "9");

g.add_edge("89", 1.0, "8", "9");

System.out.println(g);

g.dfs("1");

g.dfs("2");

if (g.top_sort())

System.out.print(" Sort Complete ");

else

System.out.print(" Graph COntains a Cycle ");

System.out.print(" Press Enter to Exit");

System.in.read();

}

}

/*

Nodes

---------------

1 false

4 false

5 false

2 false

3 false

6 false

8 false

7 false

9 false

Edges

---------------

14: 1 4

15: 1 5

23: 2 3

24: 2 4

34: 3 4

36: 3 6

38: 3 8

45: 4 5

57: 5 7

59: 5 9

67: 6 7

79: 7 9

89: 8 9

DFS Source Node: 1

--------------------

Visiting Node 1

Follow Edge 14: 1 4

Visiting Node 4

Follow Edge 45: 4 5

Visiting Node 5

Follow Edge 57: 5 7

Visiting Node 7

Follow Edge 79: 7 9

Visiting Node 9

Backup From 9

Reverse Edge 79: 7 9

Backup From 7

Reverse Edge 57: 5 7

Backup From 5

Reverse Edge 45: 4 5

Backup From 4

Reverse Edge 14: 1 4

Backup From 1

DFS Source Node: 2

--------------------

Visiting Node 2

Follow Edge 23: 2 3

Visiting Node 3

Follow Edge 34: 3 4

Visiting Node 4

Follow Edge 45: 4 5

Visiting Node 5

Follow Edge 57: 5 7

Visiting Node 7

Follow Edge 79: 7 9

Visiting Node 9

Backup From 9

Reverse Edge 79: 7 9

Backup From 7

Reverse Edge 57: 5 7

Backup From 5

Reverse Edge 45: 4 5

Backup From 4

Reverse Edge 34: 3 4

Follow Edge 36: 3 6

Visiting Node 6

Backup From 6

Reverse Edge 36: 3 6

Follow Edge 38: 3 8

Visiting Node 8

Backup From 8

Reverse Edge 38: 3 8

Backup From 3

Reverse Edge 23: 2 3

Backup From 2

Press Enter to Exit

*/