sage/graphs/graph.py: multigraph recognition in init fails

[darijgr]

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

CC: @nathanncohen @sagetrac-sage-combinat @sagetrac-tmonteil @videlec @dcoudert

Component: graph theory

Keywords: sage-combinat

Author: Nathann Cohen

Branch/Commit: 197bc18

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/18067

[nathanncohen]

comment:1

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

[darijgr]

comment:2

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.

[nathanncohen]

comment:3

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

[darijgr]

comment:4

Thanks a lot!

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

[nathanncohen]

Branch: public/18067

[nathanncohen]

Author: Nathann Cohen

[nathanncohen]

comment:5

Just added a branch, and explained what in does in this ticket's description. Needs review :-)

Nathann

[sagetrac-git]

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

155b464

trac #18067: multigraph recognition in init fails

[sagetrac-git]

Commit: 155b464

[videlec]

comment:8

more beautiful description!

[sagetrac-git]

Changed commit from 155b464 to 0447069

[sagetrac-git]

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

0447069

trac #18067: Broken doctests and weight

[nathanncohen]

New commits:

0447069

trac #18067: Broken doctests and weight

[darijgr]

comment:11

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.

[nathanncohen]

comment:12

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

[darijgr]

comment:13

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()?

[nathanncohen]

comment:14

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

[nathanncohen]

comment:15

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

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:16

For me the patch is OK. All tests pass (sage/graphs/ and sage/graphs/*/) and the doc builds normally.
David.

[nathanncohen]

comment:17

THaaaaaaaaaaaaaanks !!!!

Nathann

[sagetrac-git]

Changed commit from 0447069 to 197bc18

[sagetrac-git]

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

a15b92f	Fix minor typo.
c500bfa	Make Sandpiles copyable
e4c701d	Implement GenericGraph.__copy__
197bc18	Merge #18032 into #18067

[vbraun]

comment:19

Fixed merge failure...

[vbraun]

Changed branch from public/18067 to 197bc18