4 Replies - 486 Views - Last Post: 10 October 2018 - 09:20 PM

#1 MentalFloss   User is offline

  • .
  • member icon

Reputation: 619
  • View blog
  • Posts: 1,590
  • Joined: 02-September 09

Directed Graph Dependency Detection

Posted 07 October 2018 - 06:34 PM

I am building a directed graph where nodes in the future depend upon nodes in the past, and there can be a situation where a current node has been entered to be a dependency on some node A, that is a dependency of some node B, where node B depends on current node.

This is not a cycle, but in context it is a problem.

Here is a diagram:

Posted Image

The red arrow creates an illegal path because it would bypass A.

This can happen anywhere in a graph, so I need a general way of detecting them. I would only need to detect the first one, and error in such case.

Does this type of configuration have a name? Or associated algorithm of detection?

Please do not provide deep solutions, because it's an assignment. I am pretty stumped though.

Thank you.

EDIT:

I think I might need this: https://en.wikipedia...logical_sorting

Does that seem reasonable?

EDIT:

OK. It seems like if I use Kahn's algorithm to construct a topological sort of start nodes, and the resultant set matches my set of all nodes in graph, then there is no violation of dependencies in the graph, otherwise there is.

Does this seem correct to you?

This post has been edited by MentalFloss: 07 October 2018 - 06:46 PM


Is This A Good Question/Topic? 1
  • +

Replies To: Directed Graph Dependency Detection

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12648
  • View blog
  • Posts: 45,822
  • Joined: 27-December 08

Re: Directed Graph Dependency Detection

Posted 07 October 2018 - 07:08 PM

Granted, your example does not form a directed cycle. However, if we remove the orientation from the graph (i.e., take the undirected graph corresponding to your digraph), it looks like it suffices to check for an undirected cycle. This is fairly straight-forward to do, using something like a BFS or DFS.

More generally, I think the Floyd-Warshall algorithm for the all-pairs shortest path problem will be helpful. In particular, suppose C < A, C < B, and A < B (where C < A denotes that C comes before A). If there is a path from C->A and C->B, then we have an issue if there is a path from A->B.

By the way, do you mind if I move this to the Computer Science forum? If your questions are not over specific Java implementation (or at least, Java debugging), then I think this could generate some good discussion in the CS forum. :)

Based on your edit:

Quote

OK. It seems like if I use Kahn's algorithm to construct a topological sort of start nodes, and the resultant set matches my set of all nodes in graph, then there is no violation of dependencies in the graph, otherwise there is.

Does this seem correct to you?


There could be multiple correct topological orders. A topological sort wouldn't detect issues in your dependency graph, so much as allow you to avoid them (so long as your dependency graph did not have a directed cycle).
Was This Post Helpful? 1
  • +
  • -

#3 MentalFloss   User is offline

  • .
  • member icon

Reputation: 619
  • View blog
  • Posts: 1,590
  • Joined: 02-September 09

Re: Directed Graph Dependency Detection

Posted 07 October 2018 - 07:11 PM

Quote

By the way, do you mind if I move this to the Computer Science forum?


Sure.

Quote

More generally, I think the Floyd-Warshall algorithm for the all-pairs shortest path problem will be helpful.


My graph is not weighted on edges.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12648
  • View blog
  • Posts: 45,822
  • Joined: 27-December 08

Re: Directed Graph Dependency Detection

Posted 07 October 2018 - 07:16 PM

Moved to Computer Science!

An unweighted graph can be viewed as a directed graph with all edges having the same weight. We simply care about whether there is a directed path between two vertices, and Floyd's algorithm will take care of this (as well as provide some extra information, which we can safely ignore).
Was This Post Helpful? 1
  • +
  • -

#5 MentalFloss   User is offline

  • .
  • member icon

Reputation: 619
  • View blog
  • Posts: 1,590
  • Joined: 02-September 09

Re: Directed Graph Dependency Detection

Posted 10 October 2018 - 09:20 PM

This was actually too difficult for me to get implemented in the required time. Serendipitously, it turned out to be a feature that was not even meant to be implemented, and we would have lost points.

If you feel like writing a tutorial on it, I would be excited to read it. I'm definitely going to try implementing it again when I have a bit of time.

Thanks for the information.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1