# Ticket #7477: matroids-beezer-20110105.sage

File matroids-beezer-20110105.sage, 9.3 KB (added by , 10 years ago) |
---|

Line | |
---|---|

1 | from sage.categories.category import Category |

2 | |

3 | class 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 | ################################# |

84 | class 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 | ################################# |

138 | class 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 | ################################# |

160 | class 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 | ################################# |

190 | class 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 | ################################# |

234 | class 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 | ################################# |

254 | class 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 | |

297 | set_verbose(2) |

298 | a = Matroid() |

299 | |

300 | G = graphs.PetersenGraph() |

301 | |

302 | print "\n\nGF(3)^2 testing" |

303 | |

304 | V = FiniteField(3)^2 |

305 | m = VectorMatroid(V.list()) |

306 | print "ground", len(m.ground_set()) |

307 | print "indies", len(m.independent_sets()) |

308 | print m._incidence_graph() |

309 | |

310 | g = m.ground_set() |

311 | print "Ground:", m.ground_set() |

312 | |

313 | indep = [g[2],g[3]] |

314 | dep = [g[1],g[2]] |

315 | toobig = [g[2],g[4],g[6]] |

316 | print "Independent:", m.is_independent(indep) |

317 | print "Independent:", m.is_independent(dep) |

318 | print "Independent:", m.is_independent(toobig) |

319 | |

320 | #m.independent_sets() |

321 | #print m.indy_sets() |

322 | #g=graphs.CycleGraph(4) |

323 | g=graphs.Grid2dGraph(2,3) |

324 | cm = CycleMatroid(g) |

325 | print cm.ground_set() |

326 | print cm.independent_sets() |

327 | print len(cm.bases()) |

328 | |

329 | print "\n\n\nTesting Bicircular" |

330 | bm = BicircularMatroid(g) |

331 | print bm.ground_set() |

332 | print "Independents:", bm.independent_sets() |

333 | print "Bases:", bm.bases() |

334 | print "N inds, bases:", len(bm.independent_sets()), len(bm.bases()) |

335 | |

336 | print "\n\n\nBinary test" |

337 | |

338 | V=GF(2)^4 |

339 | x = V([1,1,0,0]) |

340 | y = V([0,0,1,1]) |

341 | z = V([1,1,1,1]) |

342 | vm = VectorMatroid([x,y,z]) |

343 | print "Independent:", vm.independent_sets() |

344 | print "Bases:",vm.bases() |

345 | |

346 | print "\n\n\nIsomorphism testing" |

347 | |

348 | print "Isomorphic:" |

349 | print cm.is_isomorphic(bm) |

350 | print cm.is_isomorphic(cm) |

351 | |

352 | g = graphs.CycleGraph(4) |

353 | cm = CycleMatroid(g) |

354 | im = g.incidence_matrix().change_ring(QQ) |

355 | vm = VectorMatroid(im.columns()) |

356 | print vm.is_isomorphic(cm) |

357 | |

358 | print "\n\n\nTransversal testing" |

359 | base = [1,2,3,4] |

360 | sets = [[1,2], [3,4]] |

361 | tm = TransversalMatroid(base, sets) |

362 | print tm.ground_set() |

363 | print "Independents:", tm.independent_sets() |

364 | print "Bases:", tm.bases() |

365 | print "N inds, bases:", len(tm.independent_sets()), len(tm.bases()) |

366 | |

367 | print "\n\n\nTransversal isomorphism testing" |

368 | base1 = [1,2,3,4,5,6,7,8] |

369 | sets1 = [[1,2,3,4,5,7,8], [1,2,6,7,8], [3,4,5,6,7,8]] |

370 | tm1 = TransversalMatroid(base1, sets1) |

371 | base2 = [1,2,3,4,5,6,7,8] |

372 | sets2 = [[1,2,3,4,5,6,7], [1,3,4,5,6,7], [1,2,6,7,8]] |

373 | tm2 = TransversalMatroid(base2, sets2) |

374 | print "Transversal iso:", tm1.is_isomorphic(tm2) |

375 | |

376 | print "\n\n\nDual of uniform testing" |

377 | m62 = UniformMatroid(6,2) |

378 | dual = DualMatroid(m62) |

379 | m64 = UniformMatroid(6,4) |

380 | print m64.is_isomorphic(dual) |

381 | |

382 |