Depth-First Search, How to detect diamond dependencies?

Question

Hi there,

I was wondering if anyone can provide some pointers on how to check for diamond dependencies whilst performing a Depth-First Search over a graph...I have the following graph A -> B, A -> F, B -> C, B-> E, C -> D, E -> D.

I am trying to construct a hirearchy of containers that represent the specified graph however when i reach a diamond dependency i am not sure what to do. For example, in my graph, C and E are both child containers of B, when i resolve D i need to reference C and E. Could i detect a diamond dependency and combine C and E into a single container?

Thanks

Rohan

Answer 1

I do not know how you are defining the Nodes of the graph. Lets say one way to represent the node is as below -

public interface Node {
            int getValue();
            List<Node> getChildren();
        }

The problem with such implementation is - we do not know the parent of one Node. If we have some way to know who are the paretent of one node, we can figure out the diamond dependency.

For example, in your case, We should start from the bottom of the tree, and we can see that D has two Parenets and they are coming from B. So I would say Build your graph which takes care of not only childerns but also parents. Then in one pass, figure out which Nodes have more than one parent (like D has) and if those parenets (C and E) have the same parent (B).

Answer 2

I find it easiest to think of graph algorithms using colors.

All nodes start off white.

A node that's being processed is colored gray.

Once a node has been processed color it black.

You color a node gray as soon as you encounter it.

You color a node black once you've finished processing its children.

If you encounter a black node then you've hit a diamond dependency.

Answer 3

Graph theory is a very large and complex field of mathematics. It's one of those things where a little knowledge can be a dangerous thing :) It can also be difficult to find simple explanations for even basic applications of graph theory. Chances are very good that anything you are likely to encounter with graphs has been beaten to death and has 5 times more pitfalls and gotchas then you imagined there could be when you tackled the problem.

I'm guessing you will see some very reasonable suggestions here and then a little later they will be identified as partly or even mostly wrong. Step carefully.

Answer 4

I'm not really sure what you are trying to do, but at the latest when your graph contains cycles you really need to detect nodes you find repeatedly during your search. Usually this is done by marking the nodes in some way while you process them, so that you can see later if you already visited them before. How well this works in your case depends on your implementation and how these nodes look like...

Answer 5

Rohan, since I sometimes teach algorithms and data structures I may be biased, but I suspect you need to look into a graph algorithms book. There are a lot of different ways to do things that this seems to suggest, but it's not completely clear what you are really trying to do. Yes, in this case where you have two nodes with the incoming edges and outgoing edges to/from the same nodes (here, (B,E),(B,C) (C,D), (E,D)) it would be legit to combine the two nodes C and E into a "C,E" node. It would also be legit to break D into D₁ and D₂ have make this a tree instead of a DAG.

That is, it would be legit to do so depending on the problem.

Answer 6

Rohan you can use depth-first-search to detect "diamond-deps" by looking for cross or forward edges. If you take a look at the pseudo-code implementation of depth-first-search on the boost-graph-library homepage.

... else if (color[v] = BLACK) (u,v) is a cross or forward edge ...