Ticket #7477: matroids-beezer-20110105.sage

File matroids-beezer-20110105.sage, 9.3 KB (added by rbeezer, 10 years ago)
Line 
1from sage.categories.category import Category
2
3class Matroid(SageObject):
4
5  def __init__(self):
6    r"""
7    - ground - some category of sets
8    - bases - a list of subsets of ``ground``
9    ground_set()  assumed
10    is_independent(s)  for any subset  s  of the ground set
11    """
12    t = verbose('making a matroid', level=2)
13    verbose('made a matroid', t, level=2)
14 
15  def independent_sets(self):
16    r"""
17    Better to return a generator, since could be huge.
18    Could build up independent sets due to inclusion, ala backtracking
19    """
20    t = verbose('into generic matroid independent sets', level = 2)
21    indies = [subset for subset in powerset(self.ground_set()) if self.is_independent(subset)]
22    verbose('leaving generic matroid independent sets', t, level = 2)
23    return indies
24   
25  def bases(self):
26    r"""
27    Maximal independent sets
28    Brute force, maybe as a generator
29    Build on indy sets generators
30    """
31    t = verbose('into generic matroid bases', level = 2)
32    bases = []
33    maximum = -1
34    for indy in self.independent_sets():
35      if len(indy) > maximum:
36        # reset collection of bases
37        bases = []
38        maximum = len(indy)
39      if len(indy) == maximum:
40        bases.append(indy)
41    verbose('leaving generic matroid bases', t, level = 2)
42    return bases
43
44  def is_isomorphic(self, other):
45    r"""
46    """
47    t = verbose('into matroid isomorphism', level = 2)
48    G1 = self._incidence_graph()
49    G2 = other._incidence_graph()
50    verbose('leaving matroid isomorphism', level=2)
51    return G1.is_isomorphic(G2)
52   
53  def _incidence_graph(self):
54    r"""
55    """
56    points = self.ground_set()
57    indies = self.independent_sets()
58    np = len(points)
59    ni = len(indies)
60    p = 0
61    adj = zero_matrix(ZZ, ni+3*np, ni+3*np)
62    for point in points:
63      i = np
64      for indy in indies:
65        if point in indy:
66          adj[p, i] = 1
67          adj[i, p] = 1
68        i += 1
69      p += 1
70    # Triangles distinguish points, since remainder is bipartite
71    p = 0
72    for point in points:
73      adj[p,np+ni+p] = 1
74      adj[p,np+ni+np+p] = 1
75      adj[np+ni+p, np+ni+np+p] = 1
76      adj[np+ni+p,p] = 1
77      adj[np+ni+np+p,p] = 1
78      adj[np+ni+np+p, np+ni+p] = 1
79      p += 1
80    return Graph(adj)
81       
82#################################
83#################################
84class VectorMatroid(Matroid):
85
86  def __init__(self, s):
87    r"""
88    - V - a subspace of a finite vector space
89    """
90    t = verbose('making a vector space matroid from %s' % V, level=2)
91    # next line is sloppy, do a check on parentage
92    self.ambient = s[0].parent()
93    self.space = (self.ambient).subspace(s)
94    self._dim = self.space.dimension()
95    self.ground = s
96    verbose('made a vector space matroid', t, level=2)
97
98  def ground_set(self):
99    r"""
100    """
101    return self.ground
102
103  def is_independent(self, s):
104    r"""
105    """
106    rm = matrix(s)
107    return rm.rank() == rm.nrows()
108   
109  def independent_sets(self):
110    r"""
111    Overrides generic.
112    """
113    t = verbose('into vector matroid independent sets', level = 2)
114    dim = V.dimension()
115    indies = []
116    for sub in powerset(self.ground_set()):
117      if len(sub) < self._dim:
118        indies.append(sub)
119      elif len(sub) == self._dim and self.is_independent(sub):
120        indies.append(sub)
121    verbose('leaving vector matroid independent sets', t, level = 2)
122    return indies
123
124  def bases(self):
125    r"""
126    Maximal independent sets
127    Usual vector space notion here
128    """
129    t = verbose('into vector matroid bases', level = 2)
130    dim = V.dimension() 
131    bases = [sub for sub in powerset(self.ground_set()) if len(sub) == self._dim and self.is_independent(sub)]
132    verbose('leaving vector matroid bases', t, level = 2)
133    return bases
134   
135
136#################################
137#################################
138class CycleMatroid(Matroid):
139 
140  def __init__(self, graph):
141    r"""
142   
143    """
144    t = verbose('making a cycle matroid from %s' % graph, level = 2)
145    self.graph = graph
146    verbose('made a cycle matroid', t, level = 2)
147
148  def ground_set(self):
149    r"""
150    """
151    return self.graph.edges()
152   
153  def is_independent(self, s):
154    r"""
155    """
156    return self.graph.subgraph(edges=s).is_forest()
157
158#################################
159#################################
160class BicircularMatroid(Matroid):
161 
162  def __init__(self, graph):
163    r"""
164   
165    """
166    t = verbose('making a cycle matroid from %s' % graph, level = 2)
167    self.graph = graph
168    verbose('made a cycle matroid', t, level = 2)
169
170  def ground_set(self):
171    r"""
172    """
173    return self.graph.edges()
174   
175  def is_independent(self, s):
176    r"""
177    """
178    induced = self.graph.subgraph(edges=s)
179    # Must span, could fail sooner
180    min_degree = min(induced.degree(induced.vertices()))
181    # print "Min degree", min_degree
182    if min_degree == 0:
183      return False
184    components = induced.connected_components()
185    # print "Components", components
186    return all ([len(self.graph.subgraph(vertices=c, edges=s).cycle_basis()) < 2  for c in components])
187
188#################################
189#################################
190class TransversalMatroid(Matroid):
191 
192  def __init__(self, points, sets):
193    r"""
194    """
195    self.points = points
196    self.sets = sets
197    self.np = len(points)
198    self.ns = len(sets)
199    am = zero_matrix(ZZ, self.np+self.ns, self.np+self.ns)
200    p = 0
201    for point in points:
202      s = self.np
203      for aset in sets:
204        if point in aset:
205          am[p, s] = 1
206          am[s, p] = 1
207        s += 1
208      p += 1
209    self.graph = Graph(am)
210
211  def ground_set(self):
212    r"""
213    """
214    return self.points
215   
216  def is_independent(self, s):
217    r"""
218    Gray code edge deletions, edge additions for matching graph would be better
219    """
220    if len(s) > self.ns:
221      return False
222    # all set vertices, then some point vertices
223    vertices = range(self.np, self.np + self.ns)
224    p = 0
225    for point in self.points:
226      if point in s:
227        vertices.append(p)
228      p += 1
229    g = self.graph.subgraph(vertices=vertices)
230    return len(g.matching()) == len(s)
231   
232#################################
233#################################
234class UniformMatroid(Matroid):
235 
236  def __init__(self, n, r):
237    r"""
238    """
239    self.r = r
240    self.n = n
241
242  def ground_set(self):
243    r"""
244    """
245    return range(self.n)
246   
247  def is_independent(self, s):
248    r"""
249    """
250    return len(s) <= self.r
251
252#################################
253#################################
254class DualMatroid(Matroid):
255
256  def __init__(self, m):
257    r"""
258    """
259    self.matroid = m
260    # compute complements of basis elements to save
261    bases = m.bases()
262    ground = self.matroid.ground_set()
263    compbases = []
264    for abasis in bases:
265      compbasis = copy(ground)
266      for p in abasis:
267        compbasis.remove(p)
268      compbases.append(compbasis)
269    self.compbases = compbases
270    # compute idependent sets as well
271    indies = []
272    for abasis in compbases:
273      subs = powerset(abasis)
274      for asubset in subs:
275        if not asubset in indies:
276          indies.append(asubset)
277    self.indies = indies
278   
279  def ground_set(self):
280    r"""
281    """
282    return self.matroid.ground_set()
283
284  def is_independent(self, s):
285    r"""
286    """
287    return sorted(s) in self.indies
288   
289#################################
290# to a simplicial complex?
291# 5-set, abcde
292# subsets of size 0,1,2; then 3-set except abc, ade
293# vertices/row-labels, edges/column labels, over Z2, vector = graphical, column-space
294#  or +/- incidence over reals
295
296
297set_verbose(2)
298a = Matroid()
299
300G = graphs.PetersenGraph()
301
302print "\n\nGF(3)^2 testing"
303
304V = FiniteField(3)^2
305m = VectorMatroid(V.list())
306print "ground", len(m.ground_set())
307print "indies", len(m.independent_sets())
308print m._incidence_graph()
309
310g = m.ground_set()
311print "Ground:", m.ground_set()
312
313indep = [g[2],g[3]]
314dep = [g[1],g[2]]
315toobig = [g[2],g[4],g[6]]
316print "Independent:", m.is_independent(indep)
317print "Independent:", m.is_independent(dep)
318print "Independent:", m.is_independent(toobig)
319
320#m.independent_sets()
321#print m.indy_sets()
322#g=graphs.CycleGraph(4)
323g=graphs.Grid2dGraph(2,3)
324cm = CycleMatroid(g)
325print cm.ground_set()
326print cm.independent_sets()
327print len(cm.bases())
328
329print "\n\n\nTesting Bicircular"
330bm = BicircularMatroid(g)
331print bm.ground_set()
332print "Independents:", bm.independent_sets()
333print "Bases:", bm.bases()
334print "N inds, bases:", len(bm.independent_sets()), len(bm.bases())
335
336print "\n\n\nBinary test"
337
338V=GF(2)^4
339x = V([1,1,0,0])
340y = V([0,0,1,1])
341z = V([1,1,1,1])
342vm = VectorMatroid([x,y,z])
343print "Independent:", vm.independent_sets()
344print "Bases:",vm.bases()
345
346print "\n\n\nIsomorphism testing"
347
348print "Isomorphic:"
349print cm.is_isomorphic(bm)
350print cm.is_isomorphic(cm)
351
352g = graphs.CycleGraph(4)
353cm = CycleMatroid(g)
354im = g.incidence_matrix().change_ring(QQ)
355vm = VectorMatroid(im.columns())
356print vm.is_isomorphic(cm)
357
358print "\n\n\nTransversal testing"
359base = [1,2,3,4]
360sets = [[1,2], [3,4]]
361tm = TransversalMatroid(base, sets)
362print tm.ground_set()
363print "Independents:", tm.independent_sets()
364print "Bases:", tm.bases()
365print "N inds, bases:", len(tm.independent_sets()), len(tm.bases())
366
367print "\n\n\nTransversal isomorphism testing"
368base1 = [1,2,3,4,5,6,7,8]
369sets1 = [[1,2,3,4,5,7,8], [1,2,6,7,8], [3,4,5,6,7,8]]
370tm1 = TransversalMatroid(base1, sets1)
371base2 = [1,2,3,4,5,6,7,8]
372sets2 = [[1,2,3,4,5,6,7], [1,3,4,5,6,7], [1,2,6,7,8]]
373tm2 = TransversalMatroid(base2, sets2)
374print "Transversal iso:", tm1.is_isomorphic(tm2)
375
376print "\n\n\nDual of uniform testing"
377m62 = UniformMatroid(6,2)
378dual = DualMatroid(m62)
379m64 = UniformMatroid(6,4)
380print m64.is_isomorphic(dual)
381
382