Opened 4 years ago

Closed 4 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) Commit: 197bc184f518fd6a773b2a28aea72507c3908ac2
Dependencies: Stopgaps:

Description (last modified by ncohen)

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 and allow_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 as add_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 4 years ago by ncohen

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):

sage: Graph({1:[2],2:[1]}).edges()
[(1, 2, None)]

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

sage: Graph({1:[2],2:[1]}) == Graph({1:[2]})
True

And of course, saying twice that 2 is a neighbor of 1 yields a multigraph

sage: Graph({1:[2,2]})
Multi-graph on 2 vertices

I will fix this bug soon, by making Graph(list_of_edges) call add_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

comment:2 follow-up: Changed 4 years ago by darij

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 4 years ago by ncohen

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 4 years ago by darij

Thanks a lot!

Yes, efficiency is too a reason to get rid of this ducktyping orgy.

comment:5 Changed 4 years ago by ncohen

  • Authors set to Nathann Cohen
  • 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 4 years ago by git

  • Commit set to 155b464eb0dee397be91f06dff894281e295d84e

Branch pushed to git repo; I updated commit sha1. New commits:

155b464trac #18067: multigraph recognition in init fails

comment:7 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:8 Changed 4 years ago by vdelecroix

  • Description modified (diff)

more beautiful description!

comment:9 Changed 4 years ago by git

  • Commit changed from 155b464eb0dee397be91f06dff894281e295d84e to 04470691505336f5ce54b60569354d747fe80b76

Branch pushed to git repo; I updated commit sha1. New commits:

0447069trac #18067: Broken doctests and weight

comment:10 Changed 4 years ago by ncohen

  • Description modified (diff)

New commits:

0447069trac #18067: Broken doctests and weight

comment:11 follow-up: Changed 4 years ago by darij

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 4 years ago by ncohen

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: Changed 4 years ago by darij

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 4 years ago by ncohen

For reference, what is the rationale behind replacing _weighted by weighted()?

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 4 years ago by ncohen

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 4 years ago by dcoudert

  • 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 4 years ago by ncohen

THaaaaaaaaaaaaaanks !!!!

Nathann

comment:18 Changed 4 years ago by git

  • Commit changed from 04470691505336f5ce54b60569354d747fe80b76 to 197bc184f518fd6a773b2a28aea72507c3908ac2
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

a15b92fFix minor typo.
c500bfaMake Sandpiles copyable
e4c701dImplement GenericGraph.__copy__
197bc18Merge #18032 into #18067

comment:19 Changed 4 years ago by vbraun

  • Status changed from needs_review to positive_review

Fixed merge failure...

comment:20 Changed 4 years ago by vbraun

  • Branch changed from public/18067 to 197bc184f518fd6a773b2a28aea72507c3908ac2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.