CODEWITHSUNDEEP
algorithmgraphlanguage-agnosticgraph-theory
paulm
paulm

Reputation: 5892

Interval (graph theory) algorithm explanation

I'm trying to calculate the intervals in a graph, I found a mathematical description of the algorithm on wikipedia:

http://en.wikipedia.org/wiki/Interval_(graph_theory)

   H = { n0 }                               // Initialize work list
   while H is not empty
       remove next h from H     
       create the interval I(h)
       I(h) += { h }
       while ∃n ∈ { succ(I(h)) — I(h) } such that pred(n) ⊆ I(h)
           I(h) += { n }
       while ∃n ∈ N such that n ∉ I(h) and    // find next headers
             ∃m ∈ pred(n) such that m ∈ I(h)
           H += n

However this is probably what code looks like to a non developer as it looks like gibberish to me, what would this look like in pesudo code? My final implementation will be in C++ and applied to a control flow graph data structure that has predecessors and successor edges for each node.

Upvotes: 2

Views: 254

Answers (1)

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18158

Looks like the wikipedia code is in first order logic; pseudocode would look something like the following, disclaimer: I'm not familiar with this algorithm and am only going off of the FOL "code"

Set<Node> pred(Node n);

Set<Node> succ(Node n);

Set<Node> succ(Set<Node> interval) {
  Set<Node> retVal = new Set()
  // union of all successor edge sets for nodes in the interval
  for(Node n: interval) {
    retVal.addAll(succ(n))
  }
  // only return nodes that have predecessor edges in the interval
  for(Node n: retval) {
    if(interval.intersect(pred(n)).isEmpty()) {
      retVal.remove(n)
    }
  }
  return retVal
}

void main(Set<Node> N) { // N is the set of all nodes 
  Queue H = new Queue(N.first()) // the work queue
  while(!H.isEmpty()) {
    Node h = H.poll() // remove the first node from the queue
    Set<Node> I = new Set() // the interval
    I.add(h)
    for(Node ni : succ(I)) {
      I.add(ni) // or I.addAll(succ(I))
    }
    for(Node ni: N) {
      if(!I.intersect(pred(ni)).isEmpty()) {
        H.add(ni) // add nodes whose predecessors are in I to the work queue
      }
    }
  }
}

Upvotes: 1

Related Questions