Algorithm for efficient graph traversal

Question

I am searching an algorithm or an idea for an algorithm for the following use case:

A directed graph consists of multiple vertices. Some of these vertices are annotated with a value (like a number) and have no parent vertices (predecessors). All other vertices are representing operations. An operation can be only performed if all annotated values of the parent vertices (predecessors) are known. The result or value of the operation is then stored in the vertex.

My solution idea:

Store all vertices that have at least one parent vertex (predecessor) in a set
While the set is not empty:
1. Get the next vertex from the set
2. Check if the value for all parent vertices (predecessors) are known
3. If all values are known:
  1. Remove the vertex from the set
  2. Perform the operation
  3. Store the result of the operation in the vertex
  4. Loop (go to 2.)
4. Else: Loop (go to 2.)

My problem: I think this solution idea could work but it is not efficient (especially for large graph structures).

Are there more efficient approaches to solve this problem?

user555045 · Accepted Answer · 2017-10-26 19:04:20Z

2

There are some possibilities that avoid rechecking vertexes aimlessly, for example:

Initialize an array of integers storing, for each vertex, the number of parents.
Initialize a set of vertexes that have 0 parents (can be done at the same time as step 1).
Until that set is empty:
1. Take some vertex a from that set and process it.
2. For every edge from a to a vertex b, decrement the parent-count of vertex b. If the count reaches 0, add b to the set of vertexes that are ready to process.

answered Oct 26, 2017 at 19:04

user555045

65.8k6 gold badges95 silver badges180 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Matt Timmermans · Accepted Answer · 2017-10-26 19:31:43Z

1

What want to do is called a 'topological sort' -- in the order in which you process the vertices, every node's predecessors must occur before it does: https://en.wikipedia.org/wiki/Topological_sorting

There are several efficient algorithms. One is pretty close to yours, but you only put a vertex in the set when it has no unfinished predecessors. (harold's answer)

answered Oct 26, 2017 at 19:31

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Comments

displayName · Accepted Answer · 2017-10-26 19:38:25Z

Isn't this essentially a level-order traversal kind of problem?

Given that,

An operation can be only performed if all annotated values of the parent vertices (predecessors) are known.

you should start with the vertices that have no parent vertices. (This part has already been figured out by you.)

Next, instead of putting them in a set, put them in a queue so that the first in, first out funda actually allows you to address each vertex in the level-wise order.

If the current vertex's value cannot be computed, put it back in the queue, otherwise put the vertex that are reachable from the current vertex in the queue. Keep computing values for the vertices that have the required parent vertices' value available.

I can almost argue that with some optimizations, this would be the most efficient method.

Collectives™ on Stack Overflow

Algorithm for efficient graph traversal

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related