Provide class for directed acyclic graphs (DAGs)

[GoogleCodeExporter]

Looking over the source code, it is obvious that people are using DAGs a lot. 
It might be nice to 
have an explicit class that make sure the graph is acyclic, and raised an error 
if an edge was 
added that created a cycle. I attach a patch that provides a simple subclass of 
digraph, with two 
test cases. 

The subclass uses breadth_first_search with the child node as the root to find 
if the new edge 
would create a circle. This is obviously non-optimal for large graphs; however, 
the alternative (as 
well as I can understand) would be to maintain a complicated series of caching, 
or perhaps to 
create a separate iterable breadth-first search that ends when a condition is 
met. Probably you 
can do the second option already, but the patch attached is OK for my needs for 
now. I don't 
know if there is a difference between breadth and depth-first in this case, and 
chose breadth 
first arbitrarily.

I tried to follow the library coding style; if you have any critiques or 
opportunities for 
improvement, please let me know. I am only a beginning programmer, so please 
forgive any 
stupid mistakes.

Original issue reported on code.google.com by cmu...@gmail.com on 11 Jun 2009 at 8:01

Attachments:

• dag.patch

[GoogleCodeExporter]

Sorry, this should obviously be an enhancement, not a defect.

Original comment by cmu...@gmail.com on 11 Jun 2009 at 8:02

[GoogleCodeExporter]

Doing a cycle check on every edge added seems a bit excessive and uneeded as a 
class.

  I do use DAGs for my work, and to confirm that a graph I have is a DAG, I typically
just make sure by checking the find_cycle function (if it doesn't return 
anything,
then you're all set).

  I'm just not sure that it warrants it's own class since there aren't separate
operations for it (ie. all of the algorithms written for directed graphs should 
work
on DAGs).

Original comment by christian.muise on 12 Jun 2009 at 2:51

[GoogleCodeExporter]

Yes. Also, I think the best way to implement DAGs would be inheriting from 
digraphs
and overwriting the add_edge() method to make the circuit checking.

I won't accept the patch. But thanks anyway for the interest. :)

Original comment by pmatiello on 12 Jun 2009 at 4:23

• Changed state: WontFix
• Added labels: Type-Enhancement, Priority-Low
• Removed labels: Type-Defect, Priority-Medium