#18067: sage/graphs/graph.py: multigraph recognition in init fails
------------------------------------------+----------------------------
Reporter: darij | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.6
Component: graph theory | Resolution:
Keywords: graphs, sage-combinat, | Merged in:
Authors: Nathann Cohen | Reviewers:
Report Upstream: N/A | Work issues:
Branch: public/18067 | Commit:
Dependencies: | Stopgaps:
------------------------------------------+----------------------------
Changes (by {'newvalue': u'Nathann Cohen', 'oldvalue': ''}):
* status: new => needs_review
* cc: tmonteil, vdelecroix, dcoudert (added)
* branch: => public/18067
* author: => Nathann Cohen
Old description:
> 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:
>
> {{{
> sage: Graph([[1,2],[1,2]])
> Multi-graph on 2 vertices
> sage: Graph([[1,2],[2,1]])
> Graph on 2 vertices
> }}}
>
> 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.
New description:
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
--
Comment:
Just added a branch, and explained what in does in this ticket's
description. Needs review `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18067#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
