#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- | Merged in:
combinat, | Reviewers:
Authors: Nathann Cohen | Work issues:
Report Upstream: N/A | Commit:
Branch: public/18067 | 155b464eb0dee397be91f06dff894281e295d84e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by ncohen:
Old 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
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
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18067#comment:7>
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.
