Opened 5 years ago
Closed 5 years ago
#19385 closed enhancement (fixed)
Refactor DiGraph.__init__
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  borassi, dcoudert, dimpase, vdelecroix, SimonKing  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  ced3658 (Commits)  Commit:  ced36581c5258b40dc9e72a986fbaa9b7e12a8cc 
Dependencies:  #19381  Stopgaps: 
Description
As was done earlier with #19381, this branch strips some code out of digraph.py and stores it in graph_input.py
.
Fortunately, most of graph_input.py
can be reused for digraphs, so that's a net decrease in code volume in general.
Nathann
P.S.: I cannot believe all that this code does in order to guess what the user meants when he provides bad/incomplete/crazy input.
Change History (29)
comment:1 followup: ↓ 2 Changed 5 years ago by
 Branch set to u/ncohen/19385
 Commit set to cf53613abb473f53411b50bd2ddc049050cd6dbc
 Dependencies set to #19381
 Status changed from new to needs_review
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 5 years ago by
Replying to ncohen:
File "digraph.py", line 2671, in sage.graphs.digraph.DiGraph.path_semigroup Failed example: F = Q.path_semigroup(); F Exception raised: ... File "sage/misc/cachefunc.pyx", line 563, in genexpr (build/cythonized/sage/misc/cachefunc.c:2439) return tuple(_cache_key(item) for item in o) File "sage/misc/cachefunc.pyx", line 561, in sage.misc.cachefunc._cache_key (build/cythonized/sage/misc/cachefunc.c:2644) o = o._cache_key() File "sage/structure/sage_object.pyx", line 410, in sage.structure.sage_object.SageObject._cache_key (build/cythonized/sage/structure/sage_object.c:2918) raise TypeError("{} is not hashable and does not implement _cache_key()".format(type(self))) TypeError: <class 'sage.graphs.digraph.DiGraph'> is not hashable and does not implement _cache_key() **********************************************************************
I'll have a look. Obviously, we should either use an immutable version of a digraph, or (something which seems to be new) implement _cache_key.
comment:3 in reply to: ↑ 2 Changed 5 years ago by
I'll have a look. Obviously, we should either use an immutable version of a digraph, or (something which seems to be new) implement _cache_key.
I tried to make Q
immutable but the result was the same. And anyway, this branch shouldn't have any effect on that :/
Nathann
comment:4 Changed 5 years ago by
Somehow you're breaking this behavior:
Q = Q.copy(immutable=True, weighted=True)
and the result is a mutable digraph.
comment:5 Changed 5 years ago by
sage: hash(Q.copy(immutable=True)) 8019503473919971649 sage: hash(Q.copy(immutable=True, weighted=True))  TypeError Traceback (most recent call last) <ipythoninput4dab47b1641ed> in <module>() > 1 hash(Q.copy(immutable=True, weighted=True)) /home/travis/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/home/travis/sage/src/build/cythonized/sage/misc/cachefunc.c:14346)() 2213 if self.cache is None: 2214 f = self.f > 2215 self.cache = f(self._instance) 2216 return self.cache 2217 /home/travis/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in __hash__(self) 576 if self.allows_multiple_edges(): 577 from collections import Counter > 578 edge_items = Counter(edge_items).items() 579 return hash((frozenset(self.vertex_iterator()), 580 self._weighted, /home/travis/sage/local/lib/python/collections.pyc in __init__(self, iterable, **kwds) 451 ''' 452 super(Counter, self).__init__() > 453 self.update(iterable, **kwds) 454 455 def __missing__(self, key): /home/travis/sage/local/lib/python/collections.pyc in update(self, iterable, **kwds) 533 self_get = self.get 534 for elem in iterable: > 535 self[elem] = self_get(elem, 0) + 1 536 if kwds: 537 self.update(kwds) TypeError: unhashable type: 'list'
comment:6 Changed 5 years ago by
Oh. Great, thanks !!
Nathann
comment:7 Changed 5 years ago by
Working it down a little more. With this branch:
sage: Q = DiGraph({1:{2:['a','c']}, 2:{3:['b']}}, immutable=True, weighted=True) sage: Q.weighted() True sage: hash(Q)  TypeError Traceback (most recent call last) <ipythoninput159389487dfecf> in <module>() > 1 hash(Q) /home/travis/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/home/travis/sage/src/build/cythonized/sage/misc/cachefunc.c:14346)() 2213 if self.cache is None: 2214 f = self.f > 2215 self.cache = f(self._instance) 2216 return self.cache 2217 /home/travis/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in __hash__(self) 579 return hash((frozenset(self.vertex_iterator()), 580 self._weighted, > 581 frozenset(edge_items))) 582 raise TypeError("This graph is mutable, and thus not hashable. " 583 "Create an immutable copy by `g.copy(immutable=True)`") TypeError: unhashable type: 'list'
comment:8 Changed 5 years ago by
However this seems to work for normal graphs:
sage: Q = Graph({1:{2:['a','c']}, 2:{3:['b']}}, immutable=True, weighted=True) sage: hash(Q) 2304336980638771825
comment:9 Changed 5 years ago by
Yeah yeah the problem is very simple: instead of creating several edges labelled 'a','b','c' it creates one edge with a list as a label. Which is not hashable.
Nathann
comment:10 followup: ↓ 21 Changed 5 years ago by
I hate multiple edges, and I hate labels. Dozens of lines of copy/paste to handle stupid combinations of cases that nobody uses.
comment:11 Changed 5 years ago by
 Commit changed from cf53613abb473f53411b50bd2ddc049050cd6dbc to 99c8601b947b746cfd0cbbca4c836b82b3ac5dde
Branch pushed to git repo; I updated commit sha1. New commits:
99c8601  trac #19385: Dictionary of lists for a digraph with labelled multiple edges. How I wish I could forget those stupid things.

comment:12 Changed 5 years ago by
Fixed. Thanks for your help T_T
Nathann
comment:13 followup: ↓ 14 Changed 5 years ago by
 Reviewers set to Travis Scrimshaw
This LGTM except for this change:
 sage: G = DiGraph(M,sparse=True); G + sage: G = DiGraph(M,sparse=True,weighted=True); G
I'm worried that this change of behavior of how you handle weighted graphs could break other people's code. Unfortunately I can't comment on the correctness of either behavior, but it might have been a "feature" that others were using.
comment:14 in reply to: ↑ 13 Changed 5 years ago by
I'm worried that this change of behavior of how you handle weighted graphs could break other people's code. Unfortunately I can't comment on the correctness of either behavior, but it might have been a "feature" that others were using.
If you build a graph from a matrix in which all weights are 1 it is not considered as weighted. If any weight is different from 1 then it is considered to be weighted.
To me, this looks like a dangerous behaviour.
Nathann
comment:15 Changed 5 years ago by
Do you insist on my adding a heuristic which you admit you do not use, which will set this unreliable behaviour to what it was? This way everybody will be able to create weighted graphs without knowing exactly how, and have bugs once in a while when all weights happen to be one.
It just takes one line, and it will be dedicated.
Nathann
comment:16 Changed 5 years ago by
Of course, if the matrix has weights different from +11 BUT the graph is considered to have multiple edges, then those weights will be considered as multiple edges.
This constructor is full of corner cases like that. Where we try to guess what exactly the user did not know he wanted.
Half of the code sets flags depending on the values of others. And I am sick of trying to analyse cornercases where you are really not sure of what should happen.
Nathann
comment:17 Changed 5 years ago by
I don't even know what the default behaviour is when neither weighted nor mutiple edges is specified, and if the matrix has weights different from +1/1. Will it be multiple edges? Will it be weights? *suspense*
sage: Graph(2*graphs.PetersenGraph().adjacency_matrix()) Multigraph on 10 vertices
Wouhou ! It's multiple edges.
Nathann
comment:18 Changed 5 years ago by
Of course, if now some of the weights is not integer, then what will it be ?...
sage: Graph(0.5*graphs.PetersenGraph().adjacency_matrix()) Graph on 10 vertices sage: Graph(0.5*graphs.PetersenGraph().adjacency_matrix()).weighted() True
Weighted !!!!
Nathann
comment:19 Changed 5 years ago by
So please, help me and let us drop those unsufferable behaviour that makes this code 90% bullshit trying to figure out some sensible interpretation for the many kind of garbage that it accepts.
comment:20 followup: ↓ 24 Changed 5 years ago by
If you are willing to help whoever posts to sagedevel asking why their weighted graph code no longers works, than you can set a positive review to this.
comment:21 in reply to: ↑ 10 Changed 5 years ago by
Replying to ncohen:
I hate multiple edges, and I hate labels. Dozens of lines of copy/paste to handle stupid combinations of cases that nobody uses.
I do use multiple edges, loops and labels.
comment:22 followup: ↓ 23 Changed 5 years ago by
I believe explicit is better than implicit. And it induces a very bad gut feeling when c*G
for a graph G returns a weighted graph or a multigraph depending on whether c is integer or rational.
comment:23 in reply to: ↑ 22 Changed 5 years ago by
I believe explicit is better than implicit. And it induces a very bad gut feeling when
c*G
for a graph G returns a weighted graph or a multigraph depending on whether c is integer or rational.
+1 here. Not only it drives me mad, but the code has to deal with all that and decide it (and God it is ugly), and of course this comes at the cost of overanalysing the input, which takes time.
Nathann
comment:24 in reply to: ↑ 20 Changed 5 years ago by
 Status changed from needs_review to positive_review
If you are willing to help whoever posts to sagedevel asking why their weighted graph code no longers works, than you can set a positive review to this.
Gladly. Anyway, I prefer to explain why people have to be explicit in what they want rather than explain the 10 different combinations of parameters that [will/will not] yield what they expect.
Thank you.
Nathann
comment:25 Changed 5 years ago by
 Status changed from positive_review to needs_work
Documentation doesn't build as is evident from the patchbot log
comment:26 Changed 5 years ago by
 Commit changed from 99c8601b947b746cfd0cbbca4c836b82b3ac5dde to d09d3847fcf55f661e9be98cd4dfb3226e8d9a9d
comment:27 Changed 5 years ago by
 Commit changed from d09d3847fcf55f661e9be98cd4dfb3226e8d9a9d to ced36581c5258b40dc9e72a986fbaa9b7e12a8cc
Branch pushed to git repo; I updated commit sha1. New commits:
ced3658  trac #19385: Typo T_T

comment:29 Changed 5 years ago by
 Branch changed from u/ncohen/19385 to ced36581c5258b40dc9e72a986fbaa9b7e12a8cc
 Resolution set to fixed
 Status changed from positive_review to closed
Simon: sorry to disturb, but I think I will need your help for this branch. All doctests pass in graph/ except for a test in
DiGraph.path_semigroup
that I absolutely do not understand:/
Here is a trace, though it will appear soon on the patchbot (and I expect other related doctests to fail in combinat/).
Nathann
Last 10 new commits:
trac #19381: disclaimer
trac #19381: seidel adjacency matrix
trac #19381: adjacency matrix
trac #19381: Fix seidel adjacency
trac #19381: Incidence matrix
trac #19381: dict_of_dicts
trac #19381: dict of lists
trac #19381: dig6
trac #19381: Typo
trac #19385: Refactor DiGraph.__init__