5
$\begingroup$

I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B.

Vertex deletions have the following restrictions:

  1. When vertex B is removed, all dependent vertexes should also be removed.
  2. When vertex A is removed and vertex A was the only vertex that depends on B, vertex B should also be removed.

enter image description here

I need to list the vertixes which are deleted when

  1. Vertex B is deleted. My solution is B, E and J because

    • B -- deleted
    • E -- because of condition 2, B is removed and B was the only vertex that depends on E
    • J -- because of condition 2
  2. Vertex C is deleted. My solution is C, F, A, G, ... ?

    • C -- deleted
    • F -- because of condition 2 (C is the only vertex to F)
    • A -- condition 1 (depends on C)
    • G -- condition 2 (C is the only vertex to G)
    • I think here the process goes on and cascades. Is that correct?

What could be an algorithm for such vertexes dependency network which allows for the vertex deletion?

PS: this is an old exam exercise (2008/09); I use it as exercise for my one middle of June.

$\endgroup$
  • $\begingroup$ I don't know what "cascade" means here, but you will certainly have to iterate. $\endgroup$ – Raphael Jun 1 '12 at 12:38
6
$\begingroup$

The deletion process has two phases, one for each condition.

  1. Delete the specified node and all nodes that have a directed path to it.
  2. Delete all nodes that have no incoming edges anymore and are no sources (iterate).

There are two imporant observations that make this correct:

  • During phase two, we create no new nodes with dangling outgoing edges, that is we do not break more dependencies that would cause nodes to be removed by condition 1.
  • Phase two is a fixed-point iteration.

How you would implement this depends on your graph representation. For example, if graphs have a node list, a list of sources and every node has lists of incident nodes via incoming (pred) and outgoing (succ) edges, respectively, you can do it like this:

  void removeFancy(g : Graph, n : Node) {
    rem = collectReverse(g,n)
    g.removeAll(rem)
    removeRedundant(g)
  }

  Node[] collectReverse(g : Graph, n : Node) {
    result = [n]
    foreach ( n' in n.pred ) {
      result ++= collectReverse(g,n')
    }
    return result
  }

  removeRedundant(g : Graph) {
    oldSize = 0
    while ( oldSize != g.size ) {
      oldSize = g.size
      for ( n in g.nodes ) {
        if ( n.pred.empty? && !g.sources.contains(n) ) {
          g.remove(n)
        }
      }
    }
  }

You can also do it in a more recursive fashion:

  void removeFancy(g : Graph, n : Node) {
    for ( n' in n.pred ) {
      removeFancy(g, n')
    }

    succ = n.succ.copy
    g.remove(n)

    for ( n' in succ ) {
      if ( n'.pred.size == 0 ) {
        removeFancy(g, n')
      }
    }
  }

Here it is more challenging to see correctness because the two phases are interleaved. The essential argument is that nodes deleted in the second loop never cause new dependency breaks, therefore all nodes that have to be deleted because of condition 2 are identified thus by recursion spanned by the calls in the first loop.

If you apply any of those to your second example, you will see that in addition C, F, A and G also D will be deleted, but no other nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.