Opened 7 years ago
Closed 7 years ago
#18067 closed defect (fixed)
sage/graphs/graph.py: multigraph recognition in init fails
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.6 |
Component: | graph theory | Keywords: | graphs, sage-combinat, |
Cc: | ncohen, sage-combinat, tmonteil, vdelecroix, dcoudert | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 197bc18 (Commits, GitHub, GitLab) | Commit: | 197bc184f518fd6a773b2a28aea72507c3908ac2 |
Dependencies: | Stopgaps: |
Description (last modified by )
Sage is slightly inconsistent when it comes to detect multiple edges in
Graph(list_of_edges)
:
sage: Graph([[1,2],[1,2]]) Multi-graph on 2 vertices sage: Graph([[1,2],[2,1]]) Graph on 2 vertices
This branch fixes that bug while removing code from Graph.__init__
and
DiGraph.__init__
, which now relies GenericGraph.add_edges
. More precisely:
- Make Sage build a (di)graph from a list of edges with the following procedure:
- Create an empty graph allowing loops and multiple edges
- Call
self.add_edges(list_of_edges)
- Check whether multiedges/loops have been created, and display the pre-existing warnings accordingly.
- Update the
allow_loops
andallow_multiple_edges
parameters accordingly.
- 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.
- As a consequence it is not possible to create a graph from a Numpy matrix
anymore, though that can be done easily through
Graph(Matrix(my_matrix))
so it is not that bad either (in particular, copying the matrix is not more expensive than creating a NetworkX graph)
Furthermore, the graphs created from a Numpy matrix inherited the 'weird' NetworkX standards:
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}})]
- 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.:
Before:
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.
After:
sage: g = Graph([(1,2,3),(1,2,4)], multiedges = False) sage: g.edges() [(1, 2, 4)]
Note that it actually makes
Graph(list_of_edges)
behave asadd_edges
already does, as in the latest release we have:sage: g = Graph() sage: g.add_edges([(1,2,3),(1,2,4)]) sage: g.edges() [(1, 2, 4)]
- Fix a bug in
GenericGraph.has_multiple_edges
:sage: g = Graph(loops=True,multiedges=True) sage: g.add_edge(0,0) sage: g.has_multiple_edges() True
What this branch does will also help us reduce further the complexity of those
(awful) __init__
functions.
Nathann
Change History (20)
comment:1 Changed 7 years ago by
comment:2 follow-up: ↓ 3 Changed 7 years ago by
Sorry, Nathann; I have no idea how to fix this mess short of replacing the catch-all __init__
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.
comment:3 in reply to: ↑ 2 Changed 7 years ago by
Sorry, Nathann; I have no idea how to fix this mess short of replacing the catch-all
__init__
by a bunch of separate constructors each of which does one thing well and has a predictable return type.
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.
I would also like to turn this huge __init__
into independent functions, but that is not totally straightforward either. I do want to make it shorter, though.
Guessing the user's intent shouldn't happen unless the user asks for it.
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.
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.
Nathann
comment:4 Changed 7 years ago by
Thanks a lot!
Yes, efficiency is too a reason to get rid of this ducktyping orgy.
comment:5 Changed 7 years ago by
- Branch set to public/18067
- Cc tmonteil vdelecroix dcoudert added
- Description modified (diff)
- Status changed from new to needs_review
Just added a branch, and explained what in does in this ticket's description. Needs review :-)
Nathann
comment:6 Changed 7 years ago by
- Commit set to 155b464eb0dee397be91f06dff894281e295d84e
Branch pushed to git repo; I updated commit sha1. New commits:
155b464 | trac #18067: multigraph recognition in init fails
|
comment:7 Changed 7 years ago by
- Description modified (diff)
comment:9 Changed 7 years ago by
- Commit changed from 155b464eb0dee397be91f06dff894281e295d84e to 04470691505336f5ce54b60569354d747fe80b76
Branch pushed to git repo; I updated commit sha1. New commits:
0447069 | trac #18067: Broken doctests and weight
|
comment:10 Changed 7 years ago by
- Description modified (diff)
New commits:
0447069 | trac #18067: Broken doctests and weight
|
comment:11 follow-up: ↓ 12 Changed 7 years ago by
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.
Meanwhile, this:
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: "
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
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
as either incidence or adjacency matrix.
comment:12 in reply to: ↑ 11 Changed 7 years ago by
Hello,
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.
Well, this code really needs to be rewritten properly.
is so ugly it is almost ridiculous.
+1
Good job improving the if-condition, but IMHO the whole logic should go to hell.
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.
To drive the point home, maybe add a doctest with the matrix
I do not believe in adding doctests to explain that our code is bad. Let us change the code.
Nathann
comment:13 follow-up: ↓ 14 Changed 7 years ago by
That's fine -- it doesn't need to be fixed in this one ticket.
For reference, what is the rationale behind replacing _weighted
by weighted()
?
comment:14 in reply to: ↑ 13 Changed 7 years ago by
For reference, what is the rationale behind replacing
_weighted
byweighted()
?
Nothing smart. Only the trace of some debugging I did, before I noticed that I did not set _weighted
to something different from None in an early version of the branch.
Nathann
comment:15 Changed 7 years ago by
Hellos guys! It would help if somebody could reviw this ticket, for I have more changes to make in the constructors (speed and clarity).
Nathann
comment:16 Changed 7 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
For me the patch is OK. All tests pass (sage/graphs/ and sage/graphs/*/) and the doc builds normally. David.
comment:17 Changed 7 years ago by
THaaaaaaaaaaaaaanks !!!!
Nathann
comment:18 Changed 7 years ago by
- Commit changed from 04470691505336f5ce54b60569354d747fe80b76 to 197bc184f518fd6a773b2a28aea72507c3908ac2
- Status changed from positive_review to needs_review
comment:19 Changed 7 years ago by
- Status changed from needs_review to positive_review
Fixed merge failure...
comment:20 Changed 7 years ago by
- Branch changed from public/18067 to 197bc184f518fd6a773b2a28aea72507c3908ac2
- Resolution set to fixed
- Status changed from positive_review to closed
Hello !
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
multiedges=True
flag. Nowadays, I am not so sure anymore.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):
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?
Right now, giving the adjacencies in both direction or giving them only once yields the same result
And of course, saying twice that 2 is a neighbor of 1 yields a multigraph
I will fix this bug soon, by making
Graph(list_of_edges)
calladd_edge
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.Nathann