Opened 4 years ago

Last modified 4 years ago

#23601 needs_work enhancement

Gammoids

Reported by: zgershkoff Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by zgershkoff)

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 zgershkoff

  • Branch set to u/zgershkoff/gammoids

comment:2 Changed 4 years ago by git

  • Commit set to a861249caed8200d2c7771ceddfff816720758b5

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

a861249fix to rank function

comment:3 Changed 4 years ago by zgershkoff

  • Authors set to Zachary Gershkoff
  • 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 git

  • Commit changed from a861249caed8200d2c7771ceddfff816720758b5 to 66ffb54fd76032983d0f6c4c4215ae0798e70a64

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

95c1201more methods and documentation
66ffb54Uploading changes, even though there's a bug in _prune_vertices()

comment:5 Changed 4 years ago by git

  • Commit changed from 66ffb54fd76032983d0f6c4c4215ae0798e70a64 to c5cd5845d5dc978c4c2e364a2272ab14282e664b

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

c5cd584found the bug

comment:6 Changed 4 years ago by git

  • Commit changed from c5cd5845d5dc978c4c2e364a2272ab14282e664b to b6521d33c9b44f139bec38c4d357970000dee274

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

57f10a4gammoid_extension + tests
b6521d3fixing style of input and output blocks

comment:7 Changed 4 years ago by git

  • Commit changed from b6521d33c9b44f139bec38c4d357970000dee274 to 686f016a56eb188defe7c52bf61fda95e72793ed

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

158c5dcadding test suite
e866e35gammoid_extensions
61052cfmodule documentation
686f016added under "Concrete implementations" in doc index

comment:8 Changed 4 years ago by zgershkoff

  • Status changed from new to needs_review

That should be everything it needs right now.

comment:9 Changed 4 years ago by git

  • Commit changed from 686f016a56eb188defe7c52bf61fda95e72793ed to 0d916eb7e5f14c19ebba052d2450a46cb3d1700c

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

0d916ebReinstalled sage; documentation builds correctly now

comment:10 Changed 4 years ago by msaaltink

  • 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 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?
Note: See TracTickets for help on using tickets.