programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Directed Graph Question(s)

Greenhorn
Posts: 6
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.

Sheriff
Posts: 23594
48
• 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.

Paul Clapham
Sheriff
Posts: 23594
48
Okay, so now I see why iterating through the vertices makes sense. For each vertex you need to find out whether there's an edge from that vertex to the chosen vertex v. Right?

Todd Thor
Greenhorn
Posts: 6

Paul Clapham wrote:Okay, so now I see why iterating through the vertices makes sense. For each vertex you need to find out whether there's an edge from that vertex to the chosen vertex v. Right?

Yep, that is correct. 'v' is actually just the index of the vertex though.

Paul Clapham
Sheriff
Posts: 23594
48
Right. So, problem solved?

Todd Thor
Greenhorn
Posts: 6
Haven't quite solved this one yet...

(1) Here is what I have for the first question:

(2) And the second question, which is supposed to perform a topological sort of the graph G and return a linked list.

Paul Clapham
Sheriff
Posts: 23594
48
Well, I see that you've declared those methods to return something of a particular type, but your code fails to do that reliably. So you'd be getting compiler errors for that. But is that actually your question? It's better to actually ask your question than to make people guess.

Sheriff
Posts: 4966
136
Don't write if (condition == false), write if (!condition).

 The glass is neither half full or half empty. It is too big. But this tiny ad is just right: Why should you try IntelliJ IDEA ? https://coderanch.com/wiki/696337/IntelliJ-IDEA