# Directed Graph Question(s)

Todd Thor

Greenhorn

Posts: 6

posted 1 week ago

Hi everyone,

Beginner Java user, first post here:

I need to complete the implementation of two methods...

1) boolean hasNoIncomingEdges that takes in two parameters: G - a Graph object; and v - the integer identifier of a node in G. The methods returns true is v has no incoming edges, and false otherwise. Here's what I have (unsuccessfully tried so far):

I guess what I am trying to do in this solution is refer to the adjacency matrix of G, and iterate through the column to see if any of the values in that column are true (=1).

2) questProgression which takes in a graph (G) and returns a LinkedList topologically sorted. I have been stuck on the first question so I haven't really made any progress here.

Any help or hints would be very much appreciated.

Beginner Java user, first post here:

I need to complete the implementation of two methods...

1) boolean hasNoIncomingEdges that takes in two parameters: G - a Graph object; and v - the integer identifier of a node in G. The methods returns true is v has no incoming edges, and false otherwise. Here's what I have (unsuccessfully tried so far):

I guess what I am trying to do in this solution is refer to the adjacency matrix of G, and iterate through the column to see if any of the values in that column are true (=1).

2) questProgression which takes in a graph (G) and returns a LinkedList topologically sorted. I have been stuck on the first question so I haven't really made any progress here.

Any help or hints would be very much appreciated.

posted 1 week ago

Yes, looking at the adjacency matrix of G would be the right way to start. And then you'd have to go through that matrix and see if there is any row which represents an edge which terminates at node v.

But as far as I can see your code doesn't do that. It appears to be trying to iterate through the vertices, for a start. However I know nothing about your Graph class so I have no way of knowing if there is even a method which allows you to get at the adjacency matrix. There might be a method which, given a vertex, returns a list of edges terminating at that vertex, for all I know. If you want suggestions it would help if you told us about the Graph class's API.

- 1

Todd Thor wrote:I guess what I am trying to do in this solution is refer to the adjacency matrix of G, and iterate through the column to see if any of the values in that column are true (=1).

Yes, looking at the adjacency matrix of G would be the right way to start. And then you'd have to go through that matrix and see if there is any row which represents an edge which terminates at node v.

But as far as I can see your code doesn't do that. It appears to be trying to iterate through the vertices, for a start. However I know nothing about your Graph class so I have no way of knowing if there is even a method which allows you to get at the adjacency matrix. There might be a method which, given a vertex, returns a list of edges terminating at that vertex, for all I know. If you want suggestions it would help if you told us about the Graph class's API.

Todd Thor

Greenhorn

Posts: 6

posted 1 week ago

Thanks for the response, Paul!

Here is the link to the Graph class:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/Graph280.java

Graph Matrix Representation:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/GraphMatrixRep280.java

Graph with Cursors:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/GraphWithCursors280.java

Here is the link to the Graph class:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/Graph280.java

Graph Matrix Representation:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/GraphMatrixRep280.java

Graph with Cursors:

https://github.com/thorsness/lib280-asn7/blob/master/src/lib280/graph/GraphWithCursors280.java

Todd Thor

Greenhorn

Posts: 6

Todd Thor

Greenhorn

Posts: 6

It is sorta covered in the JavaRanch Style Guide. |