Opened 4 years ago
Last modified 4 years ago
#23601 needs_work enhancement
Gammoids
Reported by:  zgershkoff  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  matroid theory  Keywords:  
Cc:  zgershkoff, Stefan, tscrim  Merged in:  
Authors:  Zachary Gershkoff  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/zgershkoff/gammoids (Commits, GitHub, GitLab)  Commit:  0d916eb7e5f14c19ebba052d2450a46cb3d1700c 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement gammoids using digraphs for data. These will use transversal matroids for taking minors or duals.
Change History (10)
comment:1 Changed 4 years ago by
 Branch set to u/zgershkoff/gammoids
comment:2 Changed 4 years ago by
 Commit set to a861249caed8200d2c7771ceddfff816720758b5
comment:3 Changed 4 years ago by
 Cc zgershkoff Stefan tscrim added
 Component changed from PLEASE CHANGE to matroid theory
 Description modified (diff)
 Type changed from PLEASE CHANGE to enhancement
It has a working rank function. I think the hard part will be minors from contraction.
comment:4 Changed 4 years ago by
 Commit changed from a861249caed8200d2c7771ceddfff816720758b5 to 66ffb54fd76032983d0f6c4c4215ae0798e70a64
comment:5 Changed 4 years ago by
 Commit changed from 66ffb54fd76032983d0f6c4c4215ae0798e70a64 to c5cd5845d5dc978c4c2e364a2272ab14282e664b
Branch pushed to git repo; I updated commit sha1. New commits:
c5cd584  found the bug

comment:6 Changed 4 years ago by
 Commit changed from c5cd5845d5dc978c4c2e364a2272ab14282e664b to b6521d33c9b44f139bec38c4d357970000dee274
comment:7 Changed 4 years ago by
 Commit changed from b6521d33c9b44f139bec38c4d357970000dee274 to 686f016a56eb188defe7c52bf61fda95e72793ed
comment:8 Changed 4 years ago by
 Status changed from new to needs_review
That should be everything it needs right now.
comment:9 Changed 4 years ago by
 Commit changed from 686f016a56eb188defe7c52bf61fda95e72793ed to 0d916eb7e5f14c19ebba052d2450a46cb3d1700c
Branch pushed to git repo; I updated commit sha1. New commits:
0d916eb  Reinstalled sage; documentation builds correctly now

comment:10 Changed 4 years ago by
 Status changed from needs_review to needs_work
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 bysage: 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?
Branch pushed to git repo; I updated commit sha1. New commits:
fix to rank function