#14667: Matroid union
-------------------------------------+-------------------------------------
Reporter: Stefan | Owner: Stefanf
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.2
Component: matroid theory | Resolution:
Keywords: matroid | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/Rajesh_Veeranki/ticket/14667 | 3f0e407ab7f9e145e029fa0a13423ab47c01e4d6
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by Rajesh_Veeranki):
* changetime: 02/17/14 11:26:04 => 02/17/14 11:26:04
Comment:
Dear Prof.Stefan,
I have implemented the matroid union (for 2 matroids) using Rank
Matroid.The rank function I used is
rank_(M1UM2)(X) = max ( |Y|+rM2(X)) where Y belongs to M1 intersection
M2*, Y subset of X
{{{
def MatroidUnion(M0,M1):
#Constructing matroid union from two matroids
#rank(X) = max ( |Y| + rM2(X) ) where Y subset of X, and Y belongs
to M0 \cap M1.dual()
common_ground_set = M0.groundset()
common_ground_set = common_ground_set.union(M1.groundset())
def f(X):
ground_set = common_ground_set.intersection(X)
delSet = common_ground_set-ground_set
def h(X):
return
M0.rank(set(X).intersection(M0.groundset()))
#Extending matroid M0 to the union of groundsets
I0 =
RankMatroid(groundset=common_ground_set,rank_function=h)
def g(X):
return
M1.rank(set(X).intersection(M1.groundset()))
#Extending matroid M1 to the union of groundsets
I1 =
RankMatroid(groundset=common_ground_set,rank_function=g)
#Restricting matroid M0 to set X
I0 = I0.delete(delSet)
#Taking M1 dual and restricting to set X
I1 = I1.dual()
I1 = I1.delete(delSet)
# rank(X) = max ( |Y| + rM2(X) ) where Y subset of X, and
Y belongs to I0 \cap I1
r1 = len(I0.intersection(I1))
r2 = M1.rank(set(X).intersection(M1.groundset()))
return r1+r2
return RankMatroid(groundset=common_ground_set,rank_function=f)
}}}
This works just fine. What are your comments on this?
I plan to implement MatroidUnion for any no.of matroids, by calling
MatriodUnion for 2 matroids each time.
Thanks!
--
Ticket URL: <http://trac.sagemath.org/ticket/14667#comment:9>
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/groups/opt_out.
