The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

DAGs, scene graphs and cycles

I'd appreciate some help from those more knowledgable.

I'm starting to implement a scene graph for my first 3D application. I'm looking at OpenSceneGraph as a good example of how it should be done, along with Eberly's 3D books. My implementation is turning into a fairly standard Composite-Visitor.

So, my question is this: how do I make sure my DAG is *always* acyclic ? If it's not, I think my visitors will recurse until the stack overflows. But what's to stop me (or one who comes later) adding a node to the graph that is already in there ? Of course, my Add() methods could check, but doesn't that mean I have to search the whole graph for each Add() ?

Apologies if this is really obvious, or the question makes no sense, but I'm puzzled right now. I guess this puts me in the 3D equivalent of "doesn't get pointers".
Count Almasy
Friday, September 21, 2007
 
 
I've never implemented a scene graph (or any other 3D software), but I've had to detect cycles in directed graphs before (to implement circular dependency detection in a compiler for a particular domain-specific language).

The algorithm is actually pretty simple. Here's what I did:

1. Create a stack of node identifiers.

2. Crawl through all of the nodes in the graph. For each node, visit all of its children.

3. Upon visiting a node, check to see that node already exists on the node stack.

4. If you find the node already on the stack, stop executing. You've detected a cycle in the graph. If you kept crawling the graph, you'd enter an infinite loop (and you'd quickly blow through the call stack).

5. If you don't find the node on the stack, push the current node onto the stack and then visit each of the children of this node.

6. After visiting a node, pop it off the stack.

Voila! That's the whole algorithm. You'll probably implement it kind of like this...

void validateAcyclic(Stack s, Node n) {
  if (s.contains(n)) {
    throw new Exception("found a cycle!!");
  } else {
    s.push(n);
    foreach (Node child in n.children()) {
      validateAcyclic(child);
    }
    s.pop;
  }
}
BenjiSmith Send private email
Friday, September 21, 2007
 
 
Oops. I forgot the parentheses on the 'pop' method call. Obviously, that should have been...

  s.pop();

Once you've implemented this function, call it like this:

  Node root = getRootNodeFromSomewhere();
  Stack stack = new Stack();
  validateAcyclic(stack, root);

Easy-peasy, lemon-squeezy!
BenjiSmith Send private email
Friday, September 21, 2007
 
 
Dammit. Why doesn't this forum have a pseudocode compiler??

The recursive call to the validateAcyclic method also needs to include the stack parameter.

Replace this broken code...

  validateAcyclic(child);

...with this...

  validateAcyclic(s, child);
BenjiSmith Send private email
Friday, September 21, 2007
 
 
BenjiSmith

Things become clearer....I shall think some more.

Thanks.
Count Almasy
Friday, September 21, 2007
 
 
Incidentally, if your graph doesn't have a root node (or if you can't find some node to TREAT as the root node), then you'll have to implement a graph-coloring algorithm, to remember which nodes have been visited.

Then, during the navigation of your graph, you visit a node that's already been colored, you know you've hit a cycle somewhere.

Depending on the topology of your graph, you'll also need to implement some methodology that ensures you've painted all nodes before you quit looking for cycles.
BenjiSmith Send private email
Friday, September 21, 2007
 
 
The simple answer: you don't.

The more complex answer: you don't because the cost is high, and all you'd be doing is protecting the users from themselves.  Besides, if they do create a cycle they'll realize it the first time they render when they blow the stack, and that's not exactly a subtle problem.

By the way, +1 for looking at OpenSceneGraph.  It's very well designed and you can learn a lot about scene graphs and state-of-the-art graphics rendering techniques from it.
mipmap
Friday, September 21, 2007
 
 
In each node, have a parent member.  This builds a tree, which is a definitional DAG.

Then, when you add it to another node:

Parent {
  void add (Node n) {
    if (debug) {
        Node p = this;
        while (p != null) {
            if (p == n) {
              ERROR!
            }
            p = p.getParent ();
        }
    }
    n.setParent(this);
    children.add(n);
  }
}

The only cycle you could build in a tree is a node being its own ancestor.  So, scan for it in debug mode.

Again, in debug mode, you can make sure you don't visit the same node twice.  Just shove pointers to them in a Set when you're traversing, and make sure that every new one you traverse isn't in the Set.
Lally Singh Send private email
Saturday, September 22, 2007
 
 
To summarise, if I've understood correctly:

I can force the graph to be tree by ensuring that each node has exactly one parent (except of course for the root). This eliminates any possibility of a cycle.

and

If it's necessary for a node to have more than one parent, then I need to check for cycles by traversing the graph and check each node is visited only once.

Of course, my visitors traverse the tree every frame, so adding a debug check wouldn't necessarily be very expensive.

And to make it even better, I can probably get away with a tree. The OpenSceneGraph model has the drawable items (which are the memory intensive objects I don't want to duplicate) held in lists that are contained in the leaf nodes of the graph. If I follow that example then my graph can be a tree.

Thanks everyone.
Count Almasy
Saturday, September 22, 2007
 
 
"If it's necessary for a node to have more than one parent, then I need to check for cycles by traversing the graph and check each node is visited only once. "

That's not what I meant.  Don't give a node more than one parent.  The debugging code I suggested was to make sure you don't somehow make a node an ancestor of itself.  E.g. A node who's it's own grandparent.
Lally Singh Send private email
Saturday, September 22, 2007
 
 
OK, thanks, I missed the "node as its own parent" cycle in a tree.

My comment was really about the situation where I *need* to allow multiple parents, and so can't use a tree.
Count Almasy
Monday, September 24, 2007
 
 
If those elements with multiple parents don't have any children, then you're still OK.  Consider them like flyweight leaf nodes.

Otherwise, you're in arbitrary graph land.  Use a Set to cover the edges you've already covered to make sure you don't insert a cycle into your graph.

Well... use the Set in debug mode and test all the insertion types that you do to make sure that they don't insert cycles.  Then you can try taking out the cycle check.
Lally Singh Send private email
Monday, September 24, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz