Opened 4 years ago

Last modified 12 months ago

#14667 needs_work enhancement

Matroid union

Reported by: Stefan Owned by: Stefanf
Priority: major Milestone: sage-duplicate/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 (12)

comment:1 Changed 4 years ago by darij

  • Cc darij added

comment:2 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 4 years ago by Stefan

  • Component changed from combinatorics to matroid theory
  • Owner changed from sage-combinat to Stefanf

comment:4 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 3 years ago by Rajesh_Veeranki

  • 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

Hi, I want to implement the function.May i know the preferred signature of the function and where should i add it. Thanks!

comment:6 Changed 3 years ago by Rajesh_Veeranki

  • Branch set to u/Rajesh_Veeranki/ticket/14667

comment:7 Changed 3 years ago by Rajesh_Veeranki

  • 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 3 years ago by Stefan

  • 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:

3f0e407Added MatroidUnion function in constructions.py

comment:9 Changed 3 years ago by Rajesh_Veeranki

  • 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_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!

comment:10 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:12 Changed 12 months ago by Stefan

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Reviewers set to Stefan van Zwam

Already implemented in sage.matroids.union_matroid

Note: See TracTickets for help on using tickets.