Transversal Matroids

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

A TransversalMatroid class that is a child of BasisExchangeMatroid, using a bipartite graph for data.

Depends on #23139 Depends on #25065

CC: @sagetrac-Stefan @sagetrac-Rudi @sagetrac-yomcat @sagetrac-zgershkoff

Component: matroid theory

Author: Zachary Gershkoff

Branch/Commit: public/matroids/transversal_matroids-23536 @ c228986

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/23536

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+A TransversalMatroid class that is a child of BasisExchangeMatroid, using a bipartite graph for data.

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:1

The way I have it currently set up, it builds a digraph from the data after taking a matching and orienting it opposite of everything else, and this is used for finding alternating paths and enabling the basis exchange. I'll upload it as soon as I get git-trac working again.

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

New commits:

1cd8653

Starting a transversal matroid class

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

Branch: u/zgershkoff/transversal_matroids

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

Commit: 1cd8653

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1cd8653 to 0ca5ecd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

edd440e	Just some intermediate changes
0ca5ecd	basis exchange works now

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

cac3e05

writing out internal bipartite graph; added _minor override

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0ca5ecd to cac3e05

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

449aca8	not mature code, but committing before I change everything again
e3492fc	Progress, but it doesn't handle loops correctly

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cac3e05 to e3492fc

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:6

This is behaving in ways I don't understand. If I add an isolated vertex to the ground set side of the bipartite graph, that should be a loop, but right now it will think that the element is in parallel with something, even though __is_exchange_pair() is always False no matter what you check it with.

In exploring this, I discovered a more serious error.

sage: G = Graph([('a', 'b'), ('b', 'c')])
sage: G.add_vertex('d')
sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: M = TransversalMatroid(G, groundset = ['a', 'c', 'd'])
sage: M.loops()

After a long traceback, we get this error:

ValueError: vertex '1' is not in the (di)graph

Why would it be looking for a vertex '1'?

[90e8124e-743e-4424-88b0-22f5ae41372b]

comment:7

The BasisExchangeMatroid class does an extra round of translation: elements get changed into integers through pack and unpack. This ensures elements correspond directly to bits in a bitset.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

faba993

We now know what loops are

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e3492fc to faba993

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:9

I found a hint in the BasisMatroid class that x refers to the element e = self._E[x]. I guess my previous examples worked because my ground set was in a natural bijection with range(n). Maybe I should rewrite it later using bitset commands, but for now I'm just glad it works.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from faba993 to 9649227

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9649227

Documentation, tests, other fixes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

85bae1f	Merge branch 'develop' into t/23536/transversal_matroids
7443576	various improvements

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9649227 to 7443576

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:12

I think it's complete enough to be reviewed now. It lacks a method to give a minimal or maximal presentation, but I think getting a set system to work as input through the constructor is a priority, and that belongs in another ticket.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7443576 to 0230a23

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

121fb7f	saving and loading
0230a23	documentation now builds

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

Dependencies: #23139

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:14

Looks like it timed out as I was pushing an update. It's all there now.

Also, this will almost certainly conflict with #23139 in a couple of places like unpickling.pyx.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0230a23 to 955bc16

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

955bc16

forgot author stuff

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 955bc16 to a7f6d06

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b25938f	Fixed bugs in reduce_presentation()
a7f6d06	added relevant test

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

Author: Zachary Gershkoff

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:18

Actually, let me think about this a little more before it's reviewed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a7f6d06 to 5430f4a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

ece0ccd	internal graph is now networkx
5430f4a	__init__ now ignores empty sets

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:20

I can't find a clean algorithmic way to get a minimal presentation, but with reduce_presentation(), we at least get a presentation where the number of sets equals the rank.

It should be a little faster now that the basis exchange computations are done in NetworkX.

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:21

Also, the reason I let it assume that the larger side of a BipartiteGraph is the ground set is that there's no method to switch the sides, so it would be inefficient to have the constructor take a bipartite graph as input, build a new one, and sent it to __init__(). I could rewrite __init__() to take a set system instead of a graph, but that should be done in a ticket where these are added to the constructor.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5430f4a to 1ae7e8a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

1ae7e8a

added note in documentation about ground set

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ae7e8a to e7f9c00

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

91114d0	cleaning import statements
4460cd2	transitioning to set system as input, and translated elt labels internally
e7f9c00	progress

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

8ef4fe3	adding methods back to work with new input
9721658	saving and loading
78920d7	graph method
0c596b9	minors

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e7f9c00 to 0c596b9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0c596b9 to 035852f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

3f209a9	reduce_presentation
035852f	attempting to add back transversal_extension but there are errors

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 035852f to d3247f8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5fdb8c3	transversal_extension
0dbfa77	forgot to save
d3247f8	documentation and tests

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:28

I think it's ready now.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d3247f8 to 433ed4b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

cd7c7f2	fixing style (and contents) of documentation
433ed4b	I suppose this is a class, not a module

[c703ac91-1c31-4f3a-abb2-47af3ac2705d]

comment:30

I can't fix it now because I'm upgrading sage so maybe the documentation will build, but patchbot says there are a couple of problems. I don't know what "coverage" is (maybe I just need to rebase) but it looks like there's a python3 compatibility problem because iteritems() is deprecated for dictionaries, which should mean it won't work for the Counter either.

[1adc0eef-8957-46d9-975b-2dd71dfbd9ba]

comment:31

"Coverage" is checking to see if the code has sufficient doctests. I'm not seeing any methods that are missing examples/tests, but maybe since you're defining a class you need to run some sort of testsuite to make sure it's done right?

For python3 compatibility, I think you just need to change d.iteritems() -> iter(d.items()).