CODEWITHSUNDEEP
graph
Thijs Koerselman
Thijs Koerselman

Reputation: 23290

What is this type of graph and what algorithm can I use to traverse it?

I have a network of "nodes", each node produces "results". Each node and result have a unique name/id. Results are used as both input and output for each node. When all input results are available for a node, it can be executed. When the node finished executing its output results will be available.

So for example:

input node output
       A    x
x      B    y,z
x,z    C    q

In the above network. Node A has no inputs and can be executed first. Then B can be executed when result x becomes available. When both A and B are done, C can be executed because it depends on results from A and B. A result can also be a final product, like y in this case, which is not used as input to any node.

The network can be much more complex. Each node can produce a number of results, and it can have a number of input dependencies.

I would like to be able to select a result, say "q" and figure out what nodes need to be executed in order to get there. I want to do this for multiple results in a larger network of nodes.

I feel that this is a common algorithm but I have no experience in this field. It is not hierarchical like a tree, since dependencies can create circles. From what I've read I think it must be a type of forest graph.

In any case it must be traversable. There is always at least one node that can be executed first, and all the others should be able to follow in some order, without creating a deadlock where 2 nodes are waiting for each other to finish.

What is a common way to describe this network/its nodes in code, and what would be an official name for such a network?

Upvotes: 1

Views: 241

Answers (2)

mikyra
mikyra

Reputation: 10377

The name you are looking for is 'dependency graph'.

The algorithm used to break down is called 'topological sorting' (see: http://en.wikipedia.org/wiki/Topological_sorting)

One of the most famous tools resolving such dependencies is called make.

The Makefile corresponding to your example would look something like this:

x :
    echo node A

y z : x
    echo node B

q   : x z
    echo node C

As you can see the syntax is almost the same as the one used in the table of your example. The only main difference is that the order of the "columns" is reversed - saying rather "to get to ... I will first need ..." instead of "from ... I could go to ...".

Typing make <TARGET> you can easily verify it resolves the nodes in the order you want it to. Here some examples:

make q
  * node A
  * node B
  * node C

make x
  * node A

make z
  * node A
  * node B

(To make the output a little bit prettier this is the version used for the output above:

x :
    @echo " * node A"

y z : x
    @echo " * node B"

q   : x z
    @echo " * node C"

)

Upvotes: 1

Gian
Gian

Reputation: 13955

Aside from just being a type of graph, it sounds like the semantics you want are something like a Petri net with coloured tokens. Reachability analysis over Petri nets is a well-established problem for which algorithms exist in the literature. Perhaps the Wikipedia article will give you some ideas from which to start.

Upvotes: 0

Related Questions