Transitive closure fails?

[GoogleCodeExporter]

Python 2.6.2,
easy_install python-graph

# Graph creation
gr = pygraph.digraph()

# Add nodes and edges

gr.add_nodes( [ "1", "2", "3" ] );
gr.add_edge( "1", "2" )
gr.add_edge( "2", "3" )

trs = transitive_edges( gr )
print trs

I would expect to see the edge "1" "3" printed, instead, I get an empty list 
"[]".

I also added a call to transitive_edges to ex1.py after changing

gr = pygraph.graph()

to

gr = pygraph.digraph()

...
At the bottom of the file:

trs = transitive_edges( gr )
for tr in trs:
   print tr

...

output

('Switzerland', 'Germany')
('Switzerland', 'Italy')
('Switzerland', 'Germany')
('Switzerland', 'Germany')
('Switzerland', 'Italy')
('Austria', 'Slovakia')
('Austria', 'Germany')
('Austria', 'Hungary')
('Poland', 'Slovakia')
('Poland', 'Germany')
('England', 'Wales')
('France', 'Belgium')
('Germany', 'Netherlands')

Note that this does not produce an edge between Portugal and France, which you 
would expect 
since there is an edge from Portugal to Spain and an edge from Spain to France.

Original issue reported on code.google.com by aleaver...@gmail.com on 1 Sep 2009 at 6:36

[GoogleCodeExporter]

Ah -- this detects edges already present in the graph that could be inferred 
through transitive closure.  It does 
not describe a set of edges whose addition would produce the transitive closure 
of the graph.

I misread the description.

Does this library have a transitive closure routine?

Original comment by aleaver...@gmail.com on 1 Sep 2009 at 8:12

[GoogleCodeExporter]

As you noticed yourself this is just a simple algorithm that detects transitive 
edges
in a directed acyclic graph. Example:
http://code.google.com/p/python-graph/source/browse/trunk/examples/critical.py

> Does this library have a transitive closure routine?
Not yet. Feel free to contribute.

I'm changing the status of the issue as Invalid.

Regards, Tomaž

Original comment by tomaz.ko...@gmail.com on 3 Sep 2009 at 9:18

• Changed state: Invalid