#13440: Adding reverse_edge() function to DiGraph
---------------------------------+------------------------------------------
Reporter: egunawan | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.7
Component: graph theory | Resolution:
Keywords: digraph | Work issues:
Report Upstream: N/A | Reviewers: Gregg Musiker
Authors: Emily Gunawan | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Old description:
> Adding reverse_edge() function to DiGraph (related to #7720)
>
> Apply:
>
> * [attachment:trac_13440-reverse-edge.patch]
New description:
Adding reverse_edge() function to DiGraph
Apply:
* [attachment:trac_13440-reverse-edge.patch]
--
Comment:
Hellooooooooo !
Several remarks :
- By default we should have ``inplace = False``, as this is how all graph
methods (add_vertices, add_edges,delete_vertices/edges) currently behave.
- The default ``multiedges = True`` is not a good behaviour. Just picture
somebody reversing the edges of an oriented graph (i.e. a graph without
2-cycles). All these operations are totally neutral with respect to
multiple edges, and meanwhile the graph would be set to allow multiple
edges for no reason at all. I think that the default should be
``multiedges = False``, but that is not a good idea either. I think that
the best behaviour is to say "unless the user explicitely told me what he
wants to do let's not do things he may not want to see happen". Here's how
it can be implemented.
- By default, ``multiedges = None``.
If `(2,1)` is to be reversed and `(1,2)` exists with `multiedges =
None`, then an exception is raised "You have a choice to make there !".
This can only be done if `multiedges = True` (in which case there will be
two edges `(2,1)`) or `multiedges = False` (in which case the edge `(1,2)`
will be removed).
Note that there is another problem with that :
{{{
sage: D = DiGraph( [(1,2,None), (2,1,"label")] )
sage: D.edges()
[(1, 2, None), (2, 1, 'label')]
sage: D.reverse_edge(2, 1, 'label', multiedges = False)
}}}
This should not be possible because *even though there is no edge
`(1,2,label)`* it is impossible to reverse edge `(2,1)` without destroying
some information :
{{{
sage: D = DiGraph( [(1,2,None), (2,1,"label")] )
sage: D.edges()
[(1, 2, None), (2, 1, 'label')]
sage: D.add_edge(1,2,'hey')
sage: D.edges()
[(1, 2, 'hey'), (2, 1, 'label')]
}}}
So this should also raise an exception unless the graph allows
multiple edges already, or unless the user explicely said `multiedges =
True` (in which case the graph will be set to allow multiple edges anyway)
- In the documentation, `edge` is not an input of the methods, so it is a
bit weird to see it appear in the list. The list of "accepted forms" is
sufficient, so I guess that the `edge` entry can be removed, as it's
rather confusing.
- The output of these methods is not always a digraph, but that's what the
OUTPUT section says.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13440#comment:29>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
