Can you help with this question please?

(Part 3 Java)

Codes:

DiGraphADT:

import java.util.*;

/**

* An interface for a simple unweighted digraph, for use in CS207.

* No node data is maintained. Nodes are numbered from 0.

*

*/

public interface DiGraphADT

{

/** the number of nodes in the graph

@return returns the number of nodes in the graph

*/

int nNodes();

/** the number of edges in the graph

@return returns the number of edges in the graph

*/

int nEdges();

/** Adds an edge from node1 to node2

If the edge is already present in the graph it should not be duplicated

and the method should return false. Otherwise the edge should be added

and the method should return true.

@param node1 source node

@param node2 destination node

@return returns true if the edge was not already present. Otherwise

returns false.

*/

boolean addEdge(int node1, int node2);

/** true if there is an edge from node1 to node2

@param node1 source node

@param node2 destination node

@return returns true iff there is an edge from node1 to node2

*/

boolean isEdge(int node1, int node2);

/** The successors of a given node in the graph

@param node a node in the graph

@return returns an ArrayList of Integers which represent the successor

nodes of the given node

*/

ArrayList successors(int node);

/** The predecessors of a given node in the graph

@param node a node in the graph

@return returns an ArrayList of Integers which represent the predecessor nodes of the given node

*/

ArrayList predecessors(int node);

/** The outDegree of a node in the graph

@param node a node in the graph

@return returns the outDegree of the given node

*/

int outDegree(int node);

/** The inDegree of a node in the graph

@param node a node in the graph

@return returns the inDegree of the given node

*/

int inDegree(int node);

}

DiGraphEdgeList:

import java.util.*;

/**

* DiGraphEdgeList provides an implementation of a digraph using

* an edge list

*

*/

public class DiGraphEdgeList implements DiGraphADT

{

// instance variable

private ArrayListedges; // edge list

private int numNodes; // number of nodes

//internal class

class Edge {

int node1, node2;

Edge(int node1, int node2){

this.node1 = node1;

this.node2 = node2;

}

}

/**

* Constructor for objects of class GraphEdgeList

* @param n number of nodes in the graph

*/

public DiGraphEdgeList(int n)

{

// initialise instance variables

edges = new ArrayList();

numNodes = n;

}

/** the number of nodes in the graph

@return returns the number of nodes in the graph

*/

public int nNodes()

{

return numNodes;

}

/** the number of edges in the graph

@return returns the number of edges in the graph

*/

public int nEdges()

{

return edges.size();

}

/** Adds an edge from node1 to node2

If the edge is already present in the graph it should not be duplicated

and the method should return false. Otherwise the edge should be added

and the method should return true.

@param node1 source node

@param node2 destination node

@return returns true if the edge was not previously present. Otherwise returns false.

*/

public boolean addEdge(int node1, int node2)

{

if (isEdge(node1,node2))

return false;

Edge edge = new Edge(node1,node2);

edges.add(edge);

return true;

}

/** true if there is an edge from node1 to node2

@param node1 source node

@param node2 destination node

@return returns true iff there is an edge from node1 to node2

*/

public boolean isEdge(int node1, int node2)

{

int i=0;

boolean found = false;

while (!found && i

{

if ((edges.get(i).node1 == node1) && (edges.get(i).node2 == node2))

found = true;

else

i++;

}

return found;

}

/** The successors of a given node in the graph

@param node a node in the graph

@return returns an ArrayList of Integers which represent the successor nodes of the given node

*/

public ArrayList successors(int node)

{

ArrayList successorNodes = new ArrayList();

for (int i=0; i

if (edges.get(i).node1 == node)

successorNodes.add(edges.get(i).node2);

return successorNodes;

};

/** The predecssors of a given node in the graph

@param node a node in the graph

@return returns an ArrayList of Integers which represent the predecessor nodes of the given node

*/

public ArrayList predecessors(int node)

{

ArrayList predecessorNodes = new ArrayList();

for (int i=0; i

if (edges.get(i).node2 == node)

predecessorNodes.add(edges.get(i).node1);

return predecessorNodes;

};

/** The outDegree of a node in the graph

@param node a node in the graph

@return returns the outDegree of the given node

*/

public int outDegree(int node)

{

return successors(node).size();

}

/** The inDegree of a node in the graph

@param node a node in the graph

@return returns the inDegree of the given node

*/

public int inDegree(int node)

{

return predecessors(node).size();

}

}

Edges:

1 5

4 3

2 1

7 6

8 5

9 5

0 1

6 0

7 4

9 1

1 8

3 9

3 0

4 2

6 3

-

Topological:

import java.util.*;

import java.io.*;

/**

* Class Topological

* The main method creates and populates a graph from edges in file

* Edges.txt. It then calls method topologicalOrder() which you are asked to

* code using the final algorithm for this presented in lectures (slide 13

* of MyPlace item 10.5.)

*

*/

public class Topological

{

// instance variables - do not alter

private DiGraphADT g;

private int n;

/**

* Constructor for objects of class Topological - do not alter except

* that you may wish to replace the instance of DiGraphEdgeList with an

* instance of a different implementation of DiGraphADT

*/

public Topological()

{

// initialise instance variables

n = 10; // example graph used here has 10 nodes

g = new DiGraphEdgeList(n);

try {

readGraph();

}

catch (Exception e){

System.out.println("Invalid file content");

}

}

/**

* populates the graph taking data from file Edges.txt - do not alter

*/

private void readGraph() throws Exception

{

int firstNode, secNode;

Reader r = new BufferedReader(new FileReader("Edges.txt"));

StreamTokenizer st = new StreamTokenizer(r);

st.parseNumbers();

st.nextToken();

while (st.ttype != StreamTokenizer.TT_EOF) {

firstNode = (int) st.nval;

st.nextToken();

secNode = (int) st.nval;

System.out.println(firstNode + " " + secNode);

g.addEdge(firstNode,secNode);

st.nextToken();

}

}

/** prints a topological ordering of the nodes in the graph, using

* the improved algorithm presented in lectures. This algorithm makes use

* of a queue holding nodes of degree 0

*/

public void topologicalOrder()

{

// declare local variables

// create an empty queue

// populate an array with initially holding the indegrees of nodes

// and place nodes with indegree 0 on the queue

// repeatedly remove a node from the queue, print it (i.e. display

// the node number), decrement the array entry for all its successor

// nodes and add to the queue any nodes whose indegree hence falls to 0

}

/** creates and populates a graph and then prints a topological

* ordering of the nodes - do not alter

*/

public static void main(String[] args)

{

Topological gr = new Topological();

gr.topologicalOrder();

}

}

Task . . a Download and unzip file GraphFiles.zip from MyPlace. You are supplied with: a simple interface DiGraphADT.java file DiGraphEdgeList.java which provides an edge list implementation of the interface an incomplete program Topological.java which reads in a text file, builds a graph from it and displays a topological ordering of nodes. a text file Edges.txt containing some data for a graph for use in the topological ordering program provided for part 3. Part 1: Produce an implementation of the DiGraphADT interface which uses an adjacency matrix representation. There should be a single constructor which takes the number of nodes as argument. Part 2: Produce an implementation of the DiGraphADT interface which uses an adjacency list representation. There should be a single constructor which takes the number of nodes as argument. Part 3: Complete method topologicalOrder() in class Topological, such that it implements the algorithm described on page 13 of MyPlace item 10.5. This is the version which makes use of an additional queue to aid efficiency. (Note: Queue is an interface in the Java Collections Framework and so although Queue should be used for the static type of the relevant variable, a concrete type - from the Java Collections framework - which implements this interface should be used for its dynamic type.) For each node Initialise count to in-degree of node if count is 0 Place node on queue While queue is not empty Take next node v from queue Visit node v (print it or record its position in the topological ordering) For each successor x of node v Decrement count of x if count of x is 0 Place node x on queue Notes: For the purposes of this exercise, you may assume that the node numbers passed to various methods are valid, i.e. you don't need to include checks or raise exceptions to deal with a node number which is out of range being passed as an argument. Parts 1, 2 and 3 are independent of each other, so for example part 3 can be attempted without having completed earlier parts. It is recommended that you tackle part 3 prior to tackling part 4. You should ensure that you test your work appropriately. At the time of the demonstration you will be issued with a Driver class to use when demonstrating your work. You should be able to describe how your code works