Changes between Initial Version and Version 5 of Ticket #18067


Ignore:
Timestamp:
04/01/15 09:19:29 (6 years ago)
Author:
ncohen
Comment:

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

Nathann

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #18067

    • Property Cc tmonteil vdelecroix dcoudert added
    • Property Status changed from new to needs_review
    • Property Branch changed from to public/18067
    • Property Authors changed from to Nathann Cohen

  • Ticket #18067 – Description

    initial v5  
    1 The idea seems to be that the `__init__` method of `Graph` should check if the user provides some edges more than 1 time, and, if so, return a multigraph instead of a graph. In reality, whether this happens depends on the order of vertices the user provides:
     1Sage is slightly inconsistent when it comes to detect multiple edges in
     2`Graph(list_of_edges)`:
    23
    34{{{
    … …  
    89}}}
    910
    10 Apparently, it is the `if len(set(data[u])) != len(data[u])` conditional on line 1497 of graph.py which fails to fire in the second example.
     11This branch fixes that bug while removing code from `Graph.__init__` and
     12`DiGraph.__init__`, which now relies `GenericGraph.add_edges`. More precisely:
     13
     14- Make Sage build a (di)graph from a list of edges with the following procedure:
     15
     16    - Create an empty graph allowing loops and multiple edges
     17
     18    - Call `self.add_edges(list_of_edges)`
     19
     20    - Check whether multiedges/loops have been created, and display the
     21      pre-existing warnings accordingly.
     22
     23    - Update the `allow_loops` and `allow_multiple_edges` parameters
     24      accordingly.
     25
     26- When Sage does not know how to create a graph from the provided data, it
     27  currently gives it to NetworkX hoping that it will work, then convert the
     28  result into a Sage graph. With this branch, we now raise an exception instead.
     29
     30- As a consequence it is not possible to create a graph from a Numpy matrix
     31  anymore, though that can be done easily through `Graph(Matrix(my_matrix))` so
     32  it is not that bad either (in particular, copying the matrix is not more
     33  expensive than creating a NetworkX graph)
     34
     35  Furthermore, the graphs created from a Numpy matrix inherited the 'weird'
     36  NetworkX standards:
     37
     38      sage: import numpy
     39      sage: A = numpy.array([[0,1,1],[1,0,1],[1,1,0]])
     40      sage: Graph(A).edges()
     41      [(0, 1, {0: {'weight': 1}, 1: {'weight': 1}}),
     42       (0, 2, {0: {'weight': 1}, 1: {'weight': 1}}),
     43       (1, 2, {0: {'weight': 1}, 1: {'weight': 1}})]
     44
     45- Several corner-cases of Graph creation are now handled differently as a
     46  result. I merely removed the doctests, thinking that they were not actually
     47  testing a property that we want to keep, e.g.:
     48
     49  Before:
     50
     51      sage: g = Graph([(1,2,3),(1,2,4)], multiedges = False)
     52      ...
     53      ValueError: Two different labels given for the same edge in a graph without multiple edges.
     54
     55  After:
     56
     57      sage: g = Graph([(1,2,3),(1,2,4)], multiedges = False)
     58      sage: g.edges()
     59      [(1, 2, 4)]
     60
     61  Note that it actually makes `Graph(list_of_edges)` behave as `add_edges`
     62  already does, as in the latest release we have:
     63
     64      sage: g = Graph()
     65      sage: g.add_edges([(1,2,3),(1,2,4)])
     66      sage: g.edges()
     67      [(1, 2, 4)]
     68
     69- Fix a bug in `GenericGraph.has_multiple_edges`:
     70
     71      sage: g = Graph(loops=True,multiedges=True)
     72      sage: g.add_edge(0,0)
     73      sage: g.has_multiple_edges()
     74      True
     75
     76What this branch does will also help us reduce further the complexity of those
     77(awful) `__init__` functions.
     78
     79Nathann