-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_matroid.py
155 lines (132 loc) · 5.55 KB
/
binary_matroid.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
from __future__ import print_function
from collections import Counter
from six.moves import range
import itertools
import operator
import sys
from sage.all import *
from sage.matroids.advanced import BinaryMatroid
# Various functions moved into a class.
# Most methods authored by Matthias Grezet.
class BinaryMatroid2(BinaryMatroid):
@classmethod
def from_matroid(cls, matroid, **kwargs):
try:
return cls(matroid.binary_matroid().representation(), **kwargs)
except AttributeError:
raise ValueError("not representable as binary matroid")
# Arguments:
# ranks: A rank or a list of ranks to find cyclic flats of.
# Optional, defaults to checking all ranks.
# print_progress: Print in real time where the program is.
# Returns: The list of cyclic flats of the matroid.
def cyclic_flats(self, ranks=None):
if ranks is None:
ranks = range(self.full_rank() + 2)
else:
try: # Did we get a list of ranks?
iter(ranks)
except TypeError: # Nope, assume we got a single integer
ranks = [ranks]
results = set()
dual = self.dual()
groundset = self.groundset()
for rank in ranks:
flats = self.flats(rank)
for index, flat in enumerate(flats, start=1):
if dual.is_closed(groundset.difference(flat)):
results.add(flat)
return results
# Returns: Boolean indicating whether a subset is cyclic.
def is_cyclic(self, subset):
return self.dual().is_closed(self.groundset().difference(subset))
# Returns: Boolean indicating whether a subset
# is a cyclic flat of the matroid.
def has_cyclic_flat(self, subset):
return (self.is_closed(subset)
and self.dual().is_closed(self.groundset().difference(subset)))
# Returns: Flats of rank r; or all flats, if r is None.
def flats(self, r=None):
if r is not None:
return super(self.__class__, self).flats(r)
flats = []
for rank in range(self.full_rank() + 1):
flats.extend(self.flats(rank))
# Return a SetSystem to be consistent with Sage's flats method.
return sage.matroids.set_system.SetSystem(list(self.groundset()), flats)
# Returns: The poset formed by the cyclic flats of the matroid
# and the inclusion operation.
def cyclic_flats_poset(self):
cyclic_flats = self.cyclic_flats()
return Poset((cyclic_flats, operator.le))
def cf_lattice(self):
cyclic_flats = self.cyclic_flats()
return LatticePoset(Poset((cyclic_flats, operator.le)))
def show_cf_lattice(self, label=True, **kwargs):
cyclic_flats = self.cyclic_flats()
lattice = LatticePoset(Poset((cyclic_flats, operator.le)))
def pretty_label(i):
if i >= 10:
return ',{}'.format(i)
return str(i)
labels_dict = {
cf: ''.join(map(pretty_label, sorted(cf))) or '{ }'
for cf in cyclic_flats
}
heights = {}
for cf in cyclic_flats:
try:
heights[self.rank(cf)].append(cf)
except KeyError:
heights[self.rank(cf)] = [cf]
if label:
element_labels = labels_dict
else:
element_labels = {_label: '' for _label in labels_dict}
if 'figsize' not in kwargs:
kwargs['figsize'] = 20 if label else 50
if 'vertex_color' not in kwargs:
kwargs['vertex_color'] = 'white'
if 'vertex_shape' not in kwargs:
kwargs['vertex_shape'] = 0
if 'vertex_size' not in kwargs:
kwargs['vertex_size'] = 500 if label else 10
lattice.show(
element_labels=element_labels,
heights=heights,
**kwargs
)
def cf_lattice_config(self):
from configuration import Configuration, Element
cyclic_flats = self.cyclic_flats()
labels = {cf: Element(len(cf), self.rank(cf), i)
for i, cf in enumerate(cyclic_flats)}
poset = Poset((cyclic_flats, operator.le), element_labels=labels)
return Configuration(labels.values(), poset.cover_relations())
def contract(self, subset):
return self.__class__(
super(self.__class__, self).contract(subset).representation())
def delete(self, subset):
return self.__class__(
super(self.__class__, self).delete(subset).representation())
def restrict(self, subset):
return self.delete(self.groundset().difference(subset))
# Returns: Number of atoms (in the lattice of cyclic flats) for each rank.
def atoms(self):
lattice = LatticePoset(self.cyclic_flats_poset())
return Counter(self.rank(atom) for atom in lattice.atoms())
def parallel_elements(self):
return frozenset(filter(lambda x: len(x) == 2, self.circuits()))
def minimum_distance(self):
groundset = self.groundset()
full_rank = self.full_rank()
for d in range(len(groundset) + 1):
for subset in itertools.combinations(groundset, d):
if self.rank(groundset - set(subset)) < full_rank:
return d
return None # not sure how/if d is defined when groundset has rank 0
def __repr__(self):
return "Binary ({}, {}, {})-matroid".format(
len(self), self.full_rank(), self.minimum_distance())
def Uniform(r, n):
return BinaryMatroid2.from_matroid(matroids.Uniform(r, n))