CODEWITHSUNDEEP
algorithmgraph-algorithmdirected-acyclic-graphs
senloa
senloa

Reputation: 311

Ordered DAG traversal

I have a DAG that represents multiple arbitrary boolean expressions. DAG consists of two types of the nodes:

  1. Leaf node (predicate that consists of attribute, operator, value(s))
  2. Intermediate node (AND/OR)

Each node in the graph can be reused in other expressions as subexpression.

enter image description here

To compute an OR/AND node for example, it's predicates must be computed first (or intermediate nodes).

Is there any optimal algorithm that can provide this sort of bottom-up, level-order traversal for DAG staring with predicate nodes?

Upvotes: 1

Views: 486

Answers (1)

Muhteva
Muhteva

Reputation: 2832

What you are looking for is topological sort. Let me write the pseudocode with explanations for you. The idea is that if there is a path from u to v, then v appears after u in the ordering.

In both implementations, we'll create a data structure named output and append the vertices one by one to it. Eventually, output will give us the topological order.

First implementation:

  1. Compute the indegrees of all vertices.
    indegree of a vertex is the number of head ends adjacent to that vertex.
  2. Find a vertex u with indegree = 0, and store it in the output. If there is no such vertex, then it means that graph is not acyclic, therefore there is no topological order.
  3. Remove u and all its edges from the graph.
  4. Update the indegrees of the remaining vertices if necessary.
  5. Repeat the steps 2,3 and 4 V times, V being the number of vertices in the graph.
    Time complexity of this implementation is O(V^2).

More efficient implementation:

  1. Compute the indegrees of all vertices.
  2. Store all vertices with indegree 0 in an arbitrary data structure* A and store all vertices with positive indegree in another arbitrary data structure B.
  3. Remove vertex u from the A and store it in output.
  4. For all edges (u, v), update the indegree of v. If indegree of v is 0, take it from B and put it to the A.
  5. Repeat steps 3 and 4 until A and B become empty.
    Time complexity of this implementation is O(V + E), E being the number of edges in the graph.

*= Any data structure that allows adding and removing in O(1) (constant time) will be ok.

Notice that topological order may not be unique. For example there is no hierarchy between attr_2>=200 and attr_3 IN ["yellow", "green"] nodes in your graph. So their orders respective to each other may vary.

Upvotes: 2

Related Questions