Sage: Ticket #18067: sage/graphs/graph.py: multigraph recognition in init fails
https://trac.sagemath.org/ticket/18067
<p>
Sage is slightly inconsistent when it comes to detect multiple edges in
<code>Graph(list_of_edges)</code>:
</p>
<pre class="wiki">sage: Graph([[1,2],[1,2]])
Multi-graph on 2 vertices
sage: Graph([[1,2],[2,1]])
Graph on 2 vertices
</pre><p>
This branch fixes that bug while removing code from <code>Graph.__init__</code> and
<code>DiGraph.__init__</code>, which now relies <code>GenericGraph.add_edges</code>. More precisely:
</p>
<ul><li>Make Sage build a (di)graph from a list of edges with the following procedure:
<ul><li>Create an empty graph allowing loops and multiple edges
</li><li>Call <code>self.add_edges(list_of_edges)</code>
</li><li>Check whether multiedges/loops have been created, and display the
pre-existing warnings accordingly.
</li><li>Update the <code>allow_loops</code> and <code>allow_multiple_edges</code> parameters
accordingly.
</li></ul></li></ul><ul><li>When Sage does not know how to create a graph from the provided data, it
currently gives it to NetworkX hoping that it will work, then convert the
result into a Sage graph. With this branch, we now raise an exception instead.
</li></ul><ul><li>As a consequence it is not possible to create a graph from a Numpy matrix
anymore, though that can be done easily through <code>Graph(Matrix(my_matrix))</code> so
it is not that bad either (in particular, copying the matrix is not more
expensive than creating a NetworkX graph)
</li></ul><blockquote>
<p>
Furthermore, the graphs created from a Numpy matrix inherited the 'weird'
NetworkX standards:
</p>
<pre class="wiki">sage: import numpy
sage: A = numpy.array([[0,1,1],[1,0,1],[1,1,0]])
sage: Graph(A).edges()
[(0, 1, {0: {'weight': 1}, 1: {'weight': 1}}),
(0, 2, {0: {'weight': 1}, 1: {'weight': 1}}),
(1, 2, {0: {'weight': 1}, 1: {'weight': 1}})]
</pre></blockquote>
<ul><li>Several corner-cases of Graph creation are now handled differently as a
result. I merely removed the doctests, thinking that they were not actually
testing a property that we want to keep, e.g.:
</li></ul><blockquote>
<p>
Before:
</p>
<pre class="wiki">sage: g = Graph([(1,2,3),(1,2,4)], multiedges = False)
...
ValueError: Two different labels given for the same edge in a graph without multiple edges.
</pre></blockquote>
<blockquote>
<p>
After:
</p>
<pre class="wiki">sage: g = Graph([(1,2,3),(1,2,4)], multiedges = False)
sage: g.edges()
[(1, 2, 4)]
</pre></blockquote>
<blockquote>
<p>
Note that it actually makes <code>Graph(list_of_edges)</code> behave as <code>add_edges</code>
already does, as in the latest release we have:
</p>
<pre class="wiki">sage: g = Graph()
sage: g.add_edges([(1,2,3),(1,2,4)])
sage: g.edges()
[(1, 2, 4)]
</pre></blockquote>
<ul><li>Fix a bug in <code>GenericGraph.has_multiple_edges</code>:
<pre class="wiki">sage: g = Graph(loops=True,multiedges=True)
sage: g.add_edge(0,0)
sage: g.has_multiple_edges()
True
</pre></li></ul><p>
What this branch does will also help us reduce further the complexity of those
(awful) <code>__init__</code> functions.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18067
Trac 1.1.6ncohenFri, 27 Mar 2015 09:49:29 GMT
https://trac.sagemath.org/ticket/18067#comment:1
https://trac.sagemath.org/ticket/18067#comment:1
<p>
Hello !
</p>
<p>
I was actually thinking of this very behaviour last week, as many things in the (di)Graph constructors should be rewritten. A lot of time is also wasted because we have to detect what the user 'intends' to build, and at some point I thought that this could be solved by asking the user to tell us explicitly whether (s)he wants a simple graph or a multigraph, using the <code>multiedges=True</code> flag. Nowadays, I am not so sure anymore.
</p>
<p>
In this specific case, I also believe that, as you advise, we should return a multigraph. But to understand better what it works this way, see how it works for dictionary input (note that 'list of edges' input is converted into dictionary input):
</p>
<pre class="wiki">sage: Graph({1:[2],2:[1]}).edges()
[(1, 2, None)]
</pre><p>
What do you think the user wants in this case ? Is (s)he giving us a multigraph, or merely giving the adjacencies between the vertices in both directions?
</p>
<p>
Right now, giving the adjacencies in both direction or giving them only once yields the same result
</p>
<pre class="wiki">sage: Graph({1:[2],2:[1]}) == Graph({1:[2]})
True
</pre><p>
And of course, saying twice that 2 is a neighbor of 1 yields a multigraph
</p>
<pre class="wiki">sage: Graph({1:[2,2]})
Multi-graph on 2 vertices
</pre><p>
I will fix this bug soon, by making <code>Graph(list_of_edges)</code> call <code>add_edge</code> immediately. The code will also be shorter. But the graph constructors will have to be rewritten, and standards will change. We cannot guess the user's intent without guessing wrong at times, and we want to avoid that.
</p>
<p>
Nathann
</p>
TicketdarijFri, 27 Mar 2015 19:39:20 GMT
https://trac.sagemath.org/ticket/18067#comment:2
https://trac.sagemath.org/ticket/18067#comment:2
<p>
Sorry, Nathann; I have no idea how to fix this mess short of replacing the catch-all <code>__init__</code> by a bunch of separate constructors each of which does one thing well and has a predictable return type. Guessing the user's intent shouldn't happen unless the user asks for it.
</p>
TicketncohenFri, 27 Mar 2015 21:48:11 GMT
https://trac.sagemath.org/ticket/18067#comment:3
https://trac.sagemath.org/ticket/18067#comment:3
<blockquote class="citation">
<p>
Sorry, Nathann; I have no idea how to fix this mess short of replacing the catch-all <code>__init__</code> by a bunch of separate constructors each of which does one thing well and has a predictable return type.
</p>
</blockquote>
<p>
Don't worry, I will write some code for that very soon. I am about to leave to Liege (Belgium) for some Sage days so I will not be able to do it this week-end most probably (I'll be backpacking) but it will definitely be done during the week.
</p>
<p>
I would also like to turn this huge <code>__init__</code> into independent functions, but that is not totally straightforward either. I do want to make it shorter, though.
</p>
<blockquote class="citation">
<p>
Guessing the user's intent shouldn't happen unless the user asks for it.
</p>
</blockquote>
<p>
I agree with you. But I already wrote something to make those argument mandatory, and noticed that it broke doctests.. Because a complete graph stored as a multigraph is not (for Sage) equal to a complete graph (stored as a simple graph) and other problems like that.
</p>
<p>
Well. 1) I will fix this in the next days and 2) I am aware that this code has to be changed, and I will do something about it. Especially since David Coudert would like to be able to load huge graphs in Sage, and that it is currently impossible.
</p>
<p>
Nathann
</p>
TicketdarijFri, 27 Mar 2015 21:58:04 GMT
https://trac.sagemath.org/ticket/18067#comment:4
https://trac.sagemath.org/ticket/18067#comment:4
<p>
Thanks a lot!
</p>
<p>
Yes, efficiency is too a reason to get rid of this ducktyping orgy.
</p>
TicketncohenWed, 01 Apr 2015 09:19:29 GMTcc, status, description changed; branch, author set
https://trac.sagemath.org/ticket/18067#comment:5
https://trac.sagemath.org/ticket/18067#comment:5
<ul>
<li><strong>cc</strong>
<em>tmonteil</em> <em>vdelecroix</em> <em>dcoudert</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/18067?action=diff&version=5">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>public/18067</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Just added a branch, and explained what in does in this ticket's description. Needs review <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketgitWed, 01 Apr 2015 09:20:57 GMTcommit set
https://trac.sagemath.org/ticket/18067#comment:6
https://trac.sagemath.org/ticket/18067#comment:6
<ul>
<li><strong>commit</strong>
set to <em>155b464eb0dee397be91f06dff894281e295d84e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=155b464eb0dee397be91f06dff894281e295d84e"><span class="icon"></span>155b464</a></td><td><code>trac #18067: multigraph recognition in init fails</code>
</td></tr></table>
TicketncohenWed, 01 Apr 2015 09:24:25 GMTdescription changed
https://trac.sagemath.org/ticket/18067#comment:7
https://trac.sagemath.org/ticket/18067#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18067?action=diff&version=7">diff</a>)
</li>
</ul>
TicketvdelecroixWed, 01 Apr 2015 09:29:42 GMTdescription changed
https://trac.sagemath.org/ticket/18067#comment:8
https://trac.sagemath.org/ticket/18067#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18067?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
more beautiful description!
</p>
TicketgitWed, 01 Apr 2015 14:28:55 GMTcommit changed
https://trac.sagemath.org/ticket/18067#comment:9
https://trac.sagemath.org/ticket/18067#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>155b464eb0dee397be91f06dff894281e295d84e</em> to <em>04470691505336f5ce54b60569354d747fe80b76</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=04470691505336f5ce54b60569354d747fe80b76"><span class="icon"></span>0447069</a></td><td><code>trac #18067: Broken doctests and weight</code>
</td></tr></table>
TicketncohenWed, 01 Apr 2015 14:30:43 GMTdescription changed
https://trac.sagemath.org/ticket/18067#comment:10
https://trac.sagemath.org/ticket/18067#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18067?action=diff&version=10">diff</a>)
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=04470691505336f5ce54b60569354d747fe80b76"><span class="icon"></span>0447069</a></td><td><code>trac #18067: Broken doctests and weight</code>
</td></tr></table>
TicketdarijThu, 02 Apr 2015 01:09:22 GMT
https://trac.sagemath.org/ticket/18067#comment:11
https://trac.sagemath.org/ticket/18067#comment:11
<p>
I have nowhere near the expertise required to review this, but you have my thanks. This is a courageous and overdue step towards cleaning up the Augean stables of Sage's constructors.
</p>
<p>
Meanwhile, this:
</p>
<pre class="wiki"> if format is None and is_Matrix(data):
if data.is_square() and data == data.transpose():
format = 'adjacency_matrix'
else:
format = 'incidence_matrix'
msg += "Non-symmetric or non-square matrix assumed to be an incidence matrix: "
</pre><p>
is so ugly it is almost ridiculous. Good job improving the if-condition, but IMHO the whole logic should go to hell. To drive the point home, maybe add a doctest with the matrix
</p>
<pre class="wiki">0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
</pre><p>
as either incidence or adjacency matrix.
</p>
TicketncohenThu, 02 Apr 2015 11:17:27 GMT
https://trac.sagemath.org/ticket/18067#comment:12
https://trac.sagemath.org/ticket/18067#comment:12
<p>
Hello,
</p>
<blockquote class="citation">
<p>
I have nowhere near the expertise required to review this, but you have my thanks. This is a courageous and overdue step towards cleaning up the Augean stables of Sage's constructors.
</p>
</blockquote>
<p>
Well, this code really needs to be rewritten properly.
</p>
<blockquote class="citation">
<p>
is so ugly it is almost ridiculous.
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
Good job improving the if-condition, but IMHO the whole logic should go to hell.
</p>
</blockquote>
<p>
Ahahaha. Well, I also agree with you on that point, but I cannot get code in Sage by myself. I know that I only fixed a small part of the problem in this ticket, but doing too many things at once makes it impossible to find a reviewer. Soooooo while I already know what the next ticket will be about, I thought that it was better to write a smaller patch first. Then the other will come.
</p>
<blockquote class="citation">
<p>
To drive the point home, maybe add a doctest with the matrix
</p>
</blockquote>
<p>
I do not believe in adding doctests to explain that our code is bad. Let us change the code.
</p>
<p>
Nathann
</p>
TicketdarijThu, 02 Apr 2015 18:52:06 GMT
https://trac.sagemath.org/ticket/18067#comment:13
https://trac.sagemath.org/ticket/18067#comment:13
<p>
That's fine -- it doesn't need to be fixed in this one ticket.
</p>
<p>
For reference, what is the rationale behind replacing <code>_weighted</code> by <code>weighted()</code>?
</p>
TicketncohenThu, 02 Apr 2015 21:48:21 GMT
https://trac.sagemath.org/ticket/18067#comment:14
https://trac.sagemath.org/ticket/18067#comment:14
<blockquote class="citation">
<p>
For reference, what is the rationale behind replacing <code>_weighted</code> by <code>weighted()</code>?
</p>
</blockquote>
<p>
Nothing smart. Only the trace of some debugging I did, before I noticed that I did not set <code>_weighted</code> to something different from None in an early version of the branch.
</p>
<p>
Nathann
</p>
TicketncohenThu, 09 Apr 2015 06:56:16 GMT
https://trac.sagemath.org/ticket/18067#comment:15
https://trac.sagemath.org/ticket/18067#comment:15
<p>
Hellos guys! It would help if somebody could reviw this ticket, for I have more changes to make in the constructors (speed and clarity).
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 10 Apr 2015 03:52:37 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/18067#comment:16
https://trac.sagemath.org/ticket/18067#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
For me the patch is OK. All tests pass (sage/graphs/ and sage/graphs/*/) and the doc builds normally.
David.
</p>
TicketncohenFri, 10 Apr 2015 06:23:51 GMT
https://trac.sagemath.org/ticket/18067#comment:17
https://trac.sagemath.org/ticket/18067#comment:17
<p>
THaaaaaaaaaaaaaanks !!!!
</p>
<p>
Nathann
</p>
TicketgitSat, 11 Apr 2015 22:59:00 GMTstatus, commit changed
https://trac.sagemath.org/ticket/18067#comment:18
https://trac.sagemath.org/ticket/18067#comment:18
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>04470691505336f5ce54b60569354d747fe80b76</em> to <em>197bc184f518fd6a773b2a28aea72507c3908ac2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a15b92f7e0fe83cf39064c334d26195b7ff5a056"><span class="icon"></span>a15b92f</a></td><td><code>Fix minor typo.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c500bfa13492c6c51ea52a5b9c0b91fe7b47806a"><span class="icon"></span>c500bfa</a></td><td><code>Make Sandpiles copyable</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e4c701d3c7c713de540b8e351674093a9ceb6266"><span class="icon"></span>e4c701d</a></td><td><code>Implement GenericGraph.__copy__</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=197bc184f518fd6a773b2a28aea72507c3908ac2"><span class="icon"></span>197bc18</a></td><td><code>Merge #18032 into #18067</code>
</td></tr></table>
TicketvbraunSat, 11 Apr 2015 22:59:37 GMTstatus changed
https://trac.sagemath.org/ticket/18067#comment:19
https://trac.sagemath.org/ticket/18067#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Fixed merge failure...
</p>
TicketvbraunTue, 14 Apr 2015 19:43:31 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/18067#comment:20
https://trac.sagemath.org/ticket/18067#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/18067</em> to <em>197bc184f518fd6a773b2a28aea72507c3908ac2</em>
</li>
</ul>
Ticket