Gammoids

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

Implement gammoids using digraphs for data. These will use transversal matroids for taking minors or duals.

CC: @sagetrac-zgershkoff @sagetrac-Stefan @tscrim

Component: matroid theory

Author: Zachary Gershkoff

Branch/Commit: u/zgershkoff/gammoids @ 0d916eb

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

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

Branch: u/zgershkoff/gammoids

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

Commit: a861249

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

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

a861249

fix to rank function

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

Author: Zachary Gershkoff

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

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+Implement gammoids using digraphs for data. These will use transversal matroids for taking minors or duals.

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

comment:3

It has a working rank function. I think the hard part will be minors from contraction.

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

Changed commit from a861249 to 66ffb54

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

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

95c1201	more methods and documentation
66ffb54	Uploading changes, even though there's a bug in _prune_vertices()

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

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

c5cd584

found the bug

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

Changed commit from 66ffb54 to c5cd584

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

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

57f10a4	gammoid_extension + tests
b6521d3	fixing style of input and output blocks

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

Changed commit from c5cd584 to b6521d3

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

Changed commit from b6521d3 to 686f016

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

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

158c5dc	adding test suite
e866e35	gammoid_extensions
61052cf	module documentation
686f016	added under "Concrete implementations" in doc index

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

comment:8

That should be everything it needs right now.

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

Changed commit from 686f016 to 0d916eb

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

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

0d916eb

Reinstalled sage; documentation builds correctly now

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

comment:10

This looks fairly good, but I noticed a few issues:

• this is not merging cleanly with the latest development version, so you'll have to merge and resolve the conflict.

• The class documentation might explain "linked into", or point to a reference.

• the import of newlabel does not appear to be needed.

• the imports from copy import copy, deepcopy are not needed either.

• The constructor should perhaps check that input D is in fact a digraph, or can be coerced to one. For example, I might be surprised by

sage: G = graphs.CompleteGraph(3)
sage: g = Gammoid(G, roots=[1]); g
Gammoid of rank 1 on 3 elements
sage: g.digraph().edges()
[(0, 1, None), (0, 2, None), (1, 2, None)]
sage: list(g.bases())
[frozenset({0}), frozenset({1})]

I might have expected the Gammoid derived from graph G to have bases {2} as well. The edge list seems to have arbitrarily directed the edges of G. For another example Gammoid(ZZ, roots=[]) raises a messy attribute error.

• Why doesn't _prune_vertices_ remove all irrelevant vertices? And why is it not faster on bad examples? Consider these timings with the existing code:

sage: d = digraphs.Circulant(201, [1, 59, 100])
sage: %timeit Gammoid(d+digraphs.Path(1000), roots=[1,50,100,153], groundset=d.vertices())
1 loop, best of 3: 580 ms per loop
sage: %timeit Gammoid(d+digraphs.Path(2000), roots=[1,50,100,153], groundset=d.vertices())
1 loop, best of 3: 1.96 s per loop
sage: %timeit Gammoid(d+digraphs.Path(3000), roots=[1,50,100,153], groundset=d.vertices())
1 loop, best of 3: 4.17 s per loop

Here's one way to be more thorough, and faster in these cases

        V = set(self._D.vertices()).difference(self._groundset)
        if len(V) == 0:
            return
        v = self._D.add_vertex()
        self._D.add_edges( (v,u) for u in self._groundset)
        self._D.add_edges( (u,v) for u in self._roots)
        c = self._D.strongly_connected_component_containing_vertex(v)
        self._D.delete_vertices(V.difference(c))
        self._D.delete_vertex(v)

New timings:

sage: %timeit Gammoid(d+digraphs.Path(1000), roots=[1,50,100,153], groundset=d.vertices())
10 loops, best of 3: 19.3 ms per loop
sage: 
sage: %timeit Gammoid(d+digraphs.Path(2000), roots=[1,50,100,153], groundset=d.vertices())
10 loops, best of 3: 39.7 ms per loop
sage: %timeit Gammoid(d+digraphs.Path(3000), roots=[1,50,100,153], groundset=d.vertices())
10 loops, best of 3: 72.4 ms per loop

And here's a case that, while slightly slower, the new code is more accurate in pruning. First, with the original code:

%timeit Gammoid(d+digraphs.Circuit(3000), roots=[1,50,100,153], groundset=d.vertices())
10 loops, best of 3: 49.1 ms per loop

sage: g = Gammoid(d+digraphs.Circuit(3000), roots=[1,50,100,153], groundset=d.vertices())
sage: g.digraph()
Digraph on 3201 vertices

and with the new code

%timeit Gammoid(d+digraphs.Circuit(3000), roots=[1,50,100,153], groundset=d.vertices())
10 loops, best of 3: 70 ms per loop

sage: g = Gammoid(d+digraphs.Circuit(3000), roots=[1,50,100,153], groundset=d.vertices())
sage: g.digraph()
Digraph on 201 vertices

The new code could be better, for example, also deleting roots if they are unreachable from the groundset, and there are of course other ways to code up the pruning.

• the "red" colour #D55E00 looks more orange than red, to me.

• every minor of a gammoid is a gammoid. Why not have _minor_ recognize that?

• _minor_ should have a few more test cases; there are 4 paths through the code and they could all be tested.

• In the documentation for gammoid_extension you refer to the "starting set" and a "source vertex". These are new terms not appearing the documentation of the class or constructor. The documentation for the parameters does better.

• The documentation for gammoid extension could be clearer on what it accomplishes. Is every matroid extension of a gammoid that results in another gammoid obtained in this way?