-
Notifications
You must be signed in to change notification settings - Fork 158
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Simplify throws NameError, and, as implemented, doesn't work #92
Simplify throws NameError, and, as implemented, doesn't work #92
Comments
Or if you prefer to retain encapsulation: --- /usr/lib/python2.6/site-packages/pydot.py 2014-06-12 06:22:57.000000000
+0400
+++ virtenv/lib/python2.6/site-packages/pydot.py 2014-06-12 06:58:20.478835432
+0400
@@ -834,6 +834,11 @@
return False
+ def __hash__(self):
+ if self.get_parent_graph().get_top_graph_type() == 'graph':
+ return hash(min(self.get_source(), self.get_destination())
+ + max(self.get_source(), self.get_destination()))
+ return hash(self.get_source() + self.get_destination())
def parse_node_ref(self, node_str):
@@ -1455,7 +1460,7 @@
edge = Edge(obj_dict=obj)
- if self.obj_dict.get('simplify', False) and elm in edges_done:
+ if self.obj_dict.get('simplify', False) and edge in edges_done:
continue
graph.append( edge.to_string() + '\n' ) Original comment by Attachments: |
This test tests the output of `Graph.to_string()` for graphs with multiple (parallel) edges and combinations of `simplify` set to `True` or `False` and the graph being directed or undirected. This test was originally created for issue [pydot#92][1] ("Simplify throws NameError, and, as implemented, doesn't work"). It can also help catch regressions when doing future work on `Graph.to_string()`, `Edge.__eq__()` or `Edge.__hash__()`. [1]: pydot#92
These tests test `Edge` equality comparison and hashing for regressions and point out some current issues. For equality comparison (`Edge.__eq__()`): - Our current definition of edge equality: Same endpoints and, if the parent graph is directed, the same order of endpoints. (Changes to that definition may require changing some of these tests as well.) - [Identical objects should compare equal][1] (reflexivity). - [Comparisons should be symmetric][1]. - Rich comparison methods should [return `NotImplemented` if they do not implement the operation for the operands provided][2] (see also [here][3]). - Availability of equality comparison before the edge has a parent graph. For hashing (`Edge.__hash__()`): - [Hashable objects which compare equal must have the same hash value][4] (see also [here][5]). - [The hash value of an hashable object should never change during its lifetime][4] (see also [here][5]). - Try to prevent hash collisions, because they may degrade performance. - Availability of the hash method before the edge has a parent graph. Some tests are based on problems seen with the bug and patches reported in issue [pydot#92][6]. Some other tests are based on examples from articles by [Aaron Meurer][7] and [Roy Williams][8] and adapted to our `Edge` class. The tests that are currently failing have [`expectedFailure`][9] decorators that will be removed as their underlying issues are addressed in future commits. The PR for this commit is [pydot#249][10]. It should get links to spin-off issues and PRs that discuss the various issues brought up by these tests in more detail. [1]: https://docs.python.org/3.9/reference/expressions.html#value-comparisons [2]: https://docs.python.org/3.9/reference/datamodel.html#the-standard-type-hierarchy [3]: https://docs.python.org/3.9/reference/datamodel.html#object.__eq__ [4]: https://docs.python.org/3.9/glossary.html#term-hashable [5]: https://docs.python.org/3.9/reference/datamodel.html#object.__hash__ [6]: pydot#92 [7]: https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/ [8]: https://eng.lyft.com/hashing-and-equality-in-python-2ea8c738fb9d [9]: https://docs.python.org/3.9/library/unittest.html#unittest.expectedFailure [10]: pydot#249
Table of contents
The bug ¶ ^Minimal reproducible example (MRE)The following test case for the test suite contains a minimal reproducible example for the bug reported at the top of this post: def test_graph_simplify(self):
# Fail example: pydot 1.0.2. GH pydot/pydot#92 OP patch 1.
g = pydot.Graph()
g.add_edge(pydot.Edge('a', 'b'))
g.add_edge(pydot.Edge('a', 'b'))
g.add_edge(pydot.Edge('b', 'a'))
g.add_edge(pydot.Edge('b', 'a'))
test_combinations = [
('graph', False,
'graph G { a -- b; a -- b; b -- a; b -- a; }'),
('graph', True,
'graph G { a -- b; }'),
('digraph', False,
'digraph G { a -> b; a -> b; b -> a; b -> a; }'),
('digraph', True,
'digraph G { a -> b; b -> a; }')]
expected_concat = observed_concat = ''
for (graph_type, simplify, expected) in test_combinations:
expected_concat += 'graph_type %s, simplify %s: %s\n' % (
graph_type, simplify, expected)
g.set_type(graph_type)
g.set_simplify(simplify)
try:
observed = ' '.join(g.to_string().split())
except (NameError, TypeError) as e:
observed = '%s: %s' % (type(e).__name__, e)
observed_concat += 'graph_type %s, simplify %s: %s\n' % (
graph_type, simplify, observed)
self.maxDiff = None
self.assertMultiLineEqual(expected_concat, observed_concat) PR #247 was created to add this test in the test suite. MRE results
Bug already solved in pydot 1.0.3The CauseThe SolutionThe solution in pydot 1.0.3 was to rename that variable... - if self.obj_dict.get('simplify', False) and elm in edges_done:
+ if self.obj_dict.get('simplify', False) and edge in edges_done: ..., and at the same time implement an def __hash__(self):
return hash( hash(self.get_source()) + hash(self.get_destination()) ) That hash method is still unchanged in pydot today (1.4.2.dev0). Note that it would not have been possible to keep track of
Patch 1 by the OP ¶ ^The OP's first patch proposes not to use the complete OP patch 1 diff for pydot 1.0.2 (including a small fix for`Edge.__eq__()`)diff --git a/pydot.py b/pydot.py
index c2c81bcb..ba527fa6 100644
--- a/pydot.py
+++ b/pydot.py
@@ -826,3 +826,3 @@ class Edge(object, Common ):
if ( ( self.get_source()==edge.get_source() and self.get_destination()==edge.get_destination() ) or
- ( edge.get_source() == get_destination() and self.get_destination() == edge.get_source() ) ):
+ ( edge.get_source() == self.get_destination() and self.get_destination() == edge.get_source() ) ):
return True
@@ -1457,7 +1457,7 @@ class Graph(object, Common):
- if self.obj_dict.get('simplify', False) and elm in edges_done:
+ if self.obj_dict.get('simplify', False) and edge.obj_dict['points'] in edges_done:
continue
graph.append( edge.to_string() + '\n' )
- edges_done.add(edge)
+ edges_done.add(edge.obj_dict['points'])
OP patch 1 diff for pydot 1.4.1diff --git a/pydot.py b/pydot.py
index 9c085863..7419d855 100644
--- a/pydot.py
+++ b/pydot.py
@@ -754,7 +754,2 @@ class Edge(Common):
- def __hash__(self):
-
- return hash( hash(self.get_source()) +
- hash(self.get_destination()) )
-
@@ -1559,7 +1554,7 @@ class Graph(Common):
if (self.obj_dict.get('simplify', False) and
- edge in edges_done):
+ edge.obj_dict['points'] in edges_done):
continue
graph.append( edge.to_string() + '\n' )
- edges_done.add(edge)
+ edges_done.add(edge.obj_dict['points'])
With OP patch 1, the MRE fails for an undirected simple graph, as can been seen in the diff-like lines in the MRE results below. In addition to MRE results of OP patch 1 on both pydot 1.0.2 on Python 2.7.16 and pydot 1.4.1 on Python 2.7.16 or 3.7.3:
Review of OP patch 1:
Conclusion: OP patch 1 is not an improvement over the current implementation. It does invite a critical look at our current implementation, to be discussed in PR #249 and issues/PRs linked to from there.
Patch 2 by the OP ¶ ^The OP's second patch looks a bit more like the current (pydot 1.4.1) implementation. It renames def __hash__(self):
if self.get_parent_graph().get_top_graph_type() == 'graph':
return hash(min(self.get_source(), self.get_destination())
+ max(self.get_source(), self.get_destination()))
return hash(self.get_source() + self.get_destination()) OP patch 2 diff for pydot 1.0.2 (including a small fix for `Edge.__eq__()`)diff --git a/pydot.py b/pydot.py
index c2c81bcb..2093f8e8 100644
--- a/pydot.py
+++ b/pydot.py
@@ -826,3 +826,3 @@ class Edge(object, Common ):
if ( ( self.get_source()==edge.get_source() and self.get_destination()==edge.get_destination() ) or
- ( edge.get_source() == get_destination() and self.get_destination() == edge.get_source() ) ):
+ ( edge.get_source() == self.get_destination() and self.get_destination() == edge.get_source() ) ):
return True
@@ -836,2 +836,7 @@ class Edge(object, Common ):
+ def __hash__(self):
+ if self.get_parent_graph().get_top_graph_type() == 'graph':
+ return hash(min(self.get_source(), self.get_destination())
+ + max(self.get_source(), self.get_destination()))
+ return hash(self.get_source() + self.get_destination())
@@ -1457,3 +1462,3 @@ class Graph(object, Common):
- if self.obj_dict.get('simplify', False) and elm in edges_done:
+ if self.obj_dict.get('simplify', False) and edge in edges_done:
continue OP patch 2 diff for pydot 1.4.1diff --git a/pydot.py b/pydot.py
index 9c085863..8301c408 100644
--- a/pydot.py
+++ b/pydot.py
@@ -755,6 +755,8 @@ class Edge(Common):
def __hash__(self):
- return hash( hash(self.get_source()) +
- hash(self.get_destination()) )
+ if self.get_parent_graph().get_top_graph_type() == 'graph':
+ return hash(min(self.get_source(), self.get_destination())
+ + max(self.get_source(), self.get_destination()))
+ return hash(self.get_source() + self.get_destination())
With OP patch 2, the MRE tests all pass (Ok) on both pydot 1.0.2 on Python 2.7.16 and pydot 1.4.1 on Python 2.7.16 or 3.7.3:
Review of OP patch 2:
Conclusion: OP patch 2 is problematic in that it makes hashes depend on parent graph directedness without addressing the problem of mutability. It also adds some hash collisions. Still, it provides some inspiration for rethinking the current implementation.
Follow-up ¶ ^With the bug already solved and the patches provided by the OP not immediately having clear advantages over the current implementation, I will be closing this issue. The following PRs are spin-offs of this issue:
Versions used for examples in this post, unless otherwise noted: pydot 1.4.1, Python 3.7.3, Debian 10 buster, Linux 4.19 amd64. |
This test tests the output of `Graph.to_string()` for graphs with multiple (parallel) edges and combinations of `simplify` set to `True` or `False` and the graph being directed or undirected. This test was originally created for issue [#92][1] ("Simplify throws NameError, and, as implemented, doesn't work"). It can also help catch regressions when doing future work on `Graph.to_string()`, `Edge.__eq__()` or `Edge.__hash__()`. [1]: #92
What steps will reproduce the problem?
set_simplify(true)
on a graphto_string()
What is the expected output? What do you see instead?
Extraneous edges removed from dot output
What version of the product are you using? On what operating system?
1.0.2
Please provide any additional information below.
This is a patch which both resolves the
NameError
and enables the desired behavior:Original issue reported on code.google.com by
TheSoup...@gmail.com
on 12 Jun 2014 at 2:30Attachments:
The text was updated successfully, but these errors were encountered: