Adding an invalid edge to a digraph has unexpected side effects

[GoogleCodeExporter]

What steps will reproduce the problem?

>>> g = pygraph.digraph()
>>> [g.add_node(x) for x in range(5)]
[None, None, None, None, None]
>>> g.add_edge(1, 2)
>>> g.add_edge(1, 3)
>>> g.add_edge(2, 3)
>>> g.add_edge(3, 4)

# A thinko
>>> g.add_edge(2, 5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 221, in add_edge
KeyError: 5

# Correct behaviour (reject adding an edge to a nonexistant node) so far, 
buuuuut...

>>> g.add_edge(1, 0)

>>> list(g.traversal(1))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 508, in traversal
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 60, in traversal
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 82, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 82, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/algorithms/traversal.py", line 80, in _dfs
  File "/Users/owen/Library/Python/2.6/site-packages/python_graph-1.6.1-
py2.6.egg/pygraph/classes/Digraph.py", line 103, in __getitem__
KeyError: 5

The graph should know nothing about node 5 nor about the edge I accidentally 
tried to add.

What version of the product are you using? On what operating system?

pygraph-1.6.1 from pypi on Python 2.6

Original issue reported on code.google.com by angrybal...@gmail.com on 24 Aug 2009 at 8:11

[GoogleCodeExporter]

Have a patch. This should apply cleanly to trunk as of r523. It includes test 
cases for both digraph and graph and 
a fix for digraph that retains the current behaviour (by raising KeyError 
explicitly).

Original comment by angrybal...@gmail.com on 25 Aug 2009 at 4:06

Attachments:

• issue-35.patch

[GoogleCodeExporter]

That should probably check u explicitly as well. It's still a little too 
coincidental for my taste...

Original comment by angrybal...@gmail.com on 25 Aug 2009 at 4:09

[GoogleCodeExporter]

Original comment by pmatiello on 12 Sep 2009 at 5:42

• Changed state: Accepted

[GoogleCodeExporter]

Sorry for the late reply. I usually get mail when new issues are added but this 
one
somehow did not reach my inbox.

Also, I think I accidentally fixed this issue in my last commits. I can't 
reproduce
it. Could you please grab the source from the svn repository and check if the 
problem
still happens? If it's ok, I'll add some unit tests to prevent a future 
regression.

Thank you for you report an my apologies again.

Original comment by pmatiello on 13 Sep 2009 at 1:12

• Changed state: Started

[GoogleCodeExporter]

It's still happening with HEAD (r526):

{{{
>>> import pygraph.classes.digraph
>>> pygraph.classes.digraph
<module 'pygraph.classes.digraph' from 'pygraph/classes/digraph.py'>
>>> dg = pygraph.classes.digraph.digraph()
>>> dg.add_node(0)
>>> dg.add_node(1)
>>> dg.add_node(2)
>>> dg.add_edge(0, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "pygraph/classes/digraph.py", line 224, in add_edge
    self.node_incidence[v].append(u)
KeyError: 3
>>> dg.node_neighbors
{0: [3], 1: [], 2: []}
}}}

Original comment by angrybal...@gmail.com on 13 Sep 2009 at 1:36

[GoogleCodeExporter]

Reproduced. Thank you!

Original comment by pmatiello on 13 Sep 2009 at 3:30

[GoogleCodeExporter]

It should be fixed on HEAD now. I'll close this issue, but feel free to reopen 
it if
the problem persist.

Thanks for you report.

Original comment by pmatiello on 13 Sep 2009 at 2:02

• Changed state: Fixed