#7304: Contract edge in graph
--------------------------+-------------------------------------------------
Reporter: AJonsson | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7
Component: graph theory | Resolution:
Keywords: | Author:
Upstream: N/A | Reviewer:
Merged: | Work_issues:
--------------------------+-------------------------------------------------
Comment(by Stefan):
My pairs would be edges. In an even more ideal world, I would refer to
them by their labels. For comparison, if M is a matroid with elements 'e',
'f', 'g', I currently have some experimental code allowing me to write
N = M / ['e'] \ ['f', 'g']
resulting in the matroid with e contracted and f,g deleted. From a
matroid-theoretic point of view, if you contract an edge, all edges
parallel to it should turn into loops. The current merge_vertices doesn't
do that, even if I call G.allow_loops(True) first. With this behavior,
contracting a loop should probably equal deleting a loop.
Anyway, my main point is that I feel there should be methods for deletion
and contraction that return a new graph, rather than modifying the graph
itself.
Real use case: the other day I was wondering about maximal planar
subgraphs of a small graph G. In that case you want to explore: first
delete edge 'e', then delete edge 'f', then 'f' and 'g', then 'f' and 'h',
and finally only edge 'h'. The current implementation makes such
exploration of minors a bit cumbersome: you frequently make copies of G,
which you then modify.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7304#comment:18>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
