#17132: Perfect Matchings for Graphs
-------------------------------------+-------------------------------------
Reporter: ayyer | Owner:
Type: task | Status: new
Priority: minor | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: perfect | Merged in:
matchings, graphs | Reviewers:
Authors: Arvind Ayyer | Work issues:
Report Upstream: N/A | Commit:
Branch: | 88e58625775dfa5cea13db7336dc5f5371ab3768
public/ayyer/perfect_matchings | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ayyer):
Hi Nathann,
> I was thinking of this ticket again: instead of creating copies of the
graph, it may be cheaper to remove the two vertices before calling the
subprocedure, and to add them back when the subprocedure returns. Depends
on the actual timings.
Here's what I tried. I replaced the three lines
{{{
H = G.copy()
H.delete_vertices([g,h])
P = perfect_matchings(H)
}}}
by the single line
{{{
P = perfect_matchings(G.delete_vertices([g,h]))
}}}
But that gives me the following error:
{{{
AttributeError Traceback (most recent call
last)
<ipython-input-4-7551fac4dada> in <module>()
----> 1 G.perfect_matchings()
/Applications/Sage-6.2.app/Contents/Resources/sage/local/lib/python2.7
/site-packages/sage/graphs/perfect_matchings.pyc in perfect_matchings(G)
72 # H = G.copy()
73 # H.delete_vertices([g,h])
---> 74 P = perfect_matchings(G.delete_vertices([g,h]))
75 for p in P:
76 p.append((g,h))
/Applications/Sage-6.2.app/Contents/Resources/sage/local/lib/python2.7
/site-packages/sage/graphs/perfect_matchings.pyc in perfect_matchings(G)
59 ValueError: there is no perfect matching for a graph with an
odd number of vertices
60 """
---> 61 n = G.num_verts()
62
63 if n == 0:
AttributeError: 'NoneType' object has no attribute 'num_verts'
}}}
It looks like it treats {{{G.delete_vertices([g,h])}}} as a {{{NoneType}}}
object. But on the sage command line, {{{G.delete_vertices([g,h])}}}
actually returns the modified graph. How else can I do this without making
a copy? Thanks!
--
Ticket URL: <http://trac.sagemath.org/ticket/17132#comment:23>
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.
