Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Directed Graph Question(s)  RSS feed

 
Todd Thor
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.


 
Paul Clapham
Sheriff
Posts: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Right. So, problem solved?
 
Todd Thor
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't write if (condition == false), write if (!condition).
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!