Opened 8 years ago
Closed 3 years ago
#14667 closed enhancement (wontfix)
Matroid union
Reported by:  Stefan  Owned by:  Stefanf 

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  matroid theory  Keywords:  matroid 
Cc:  darij  Merged in:  
Authors:  Reviewers:  Stefan van Zwam  
Report Upstream:  N/A  Work issues:  
Branch:  u/Rajesh_Veeranki/ticket/14667 (Commits)  Commit:  3f0e407ab7f9e145e029fa0a13423ab47c01e4d6 
Dependencies:  Stopgaps: 
Description
Add matroid union to the matroids module.
Change History (14)
comment:1 Changed 8 years ago by
 Cc darij added
comment:2 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 7 years ago by
 Component changed from combinatorics to matroid theory
 Owner changed from sagecombinat to Stefanf
comment:4 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 7 years ago by
 Created changed from 05/30/13 18:17:54 to 05/30/13 18:17:54
 Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52
comment:6 Changed 7 years ago by
 Branch set to u/Rajesh_Veeranki/ticket/14667
comment:7 Changed 7 years ago by
 Modified changed from 02/16/14 02:39:43 to 02/16/14 02:39:43
 Status changed from new to needs_review
comment:8 Changed 7 years ago by
 Commit set to 3f0e407ab7f9e145e029fa0a13423ab47c01e4d6
 Status changed from needs_review to needs_work
1) I would not import this into the main namespace; rather I'd create a "submenu" matroids.constructions, just like we have matroids.named_matroids now.
2) Instead of computing the full list of bases, which is an expensive operation, I'd return a RankMatroid? with the appropriate rank function (implemented efficiently using matroid intersection). Matroid Union is likely to be applied to fairly large matroids, derived from graphs, whereas BasisMatroid? is optimized for small matroids.
New commits:
3f0e407  Added MatroidUnion function in constructions.py

comment:9 Changed 7 years ago by
 Modified changed from 02/17/14 19:26:04 to 02/17/14 19:26:04
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_setground_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!
comment:10 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:11 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:12 Changed 5 years ago by
 Milestone changed from sage6.4 to sageduplicate/invalid/wontfix
 Reviewers set to Stefan van Zwam
Already implemented in sage.matroids.union_matroid
comment:13 Changed 4 years ago by
 Status changed from needs_work to positive_review
comment:14 Changed 3 years ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
Closing tickets in the sageduplicate/invalid/wontfix module with positive_review (i.e. someone has confirmed they should be closed).
Hi, I want to implement the function.May i know the preferred signature of the function and where should i add it. Thanks!