Matchings in Bipartite Graphs

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

The Hopcroft-Karp and Eppstein algorithms as implemented in NetworkX compute matchings for bipartite graphs faster than the algorithms for general graphs. I've included an override of the matching method in the bipartite graph class, with parameters that allow for using the old algorithms if desired.

Component: graph theory

Author: Zach Gershkoff

Branch: 5924a34

Reviewer: Julian Rüth, Travis Scrimshaw, David Coudert

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

[vbraun]

comment:35

[sagelib-8.0.beta5] byte-compiling /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/graphs/bipartite_graph.py to bipartite_graph.pyc
[sagelib-8.0.beta5]   File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/graphs/bipartite_graph.py", line 1369
[sagelib-8.0.beta5]     raise ValueError("use_edge_labels can not be used with
[sagelib-8.0.beta5]                                                          ^
[sagelib-8.0.beta5] SyntaxError: EOL while scanning string literal

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

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

12e0d1a	Merge branch 'develop' into t/22559/matchings_in_bipartite_graphs
8ce21f2	Fixed compile errors

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

Changed commit from 0d0bbbc to 8ce21f2

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

comment:37

Looks like I wasn't careful enough while following the PEP8 guidelines. All doctests pass so it should be fine now.

Replying to @dcoudert:

Why don't you use G.networkx_graph() to get the networkx version of the graph ?

I adapted the code from the matching method of graph.py. Perhaps that would have been cleaner.

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

Changed commit from 8ce21f2 to d7d5e4d

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

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

d7d5e4d

Used networkx_graph()

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

comment:39

I adopted dcoudert's suggestion and saved a line of code.

[dcoudert]

Changed reviewer from Julian Rüth, Travis Scrimshaw to Julian Rüth, Travis Scrimshaw, David Coudert

[dcoudert]

comment:40

Passes all tests, so looks good to me.

[vbraun]

comment:41

Documentation doesn't build

[dcoudert]

comment:42

it's the bullet - when set to ``True``, computes .... You must add 2 spaces on the next lines. Then the doc builds.

          - when set to ``True``, computes a weighted matching where each edge
            is weighted by its label (if an edge has no label, `1` is assumed);
            only if ``algorithm`` is ``"Edmonds"``, ``"LP"``

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

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

60cfb32

Whitespace for documentation building

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

Changed commit from d7d5e4d to 60cfb32

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

comment:44

Thanks for catching that. It's curious that the doctest didn't notice.

I'll set it to needs review again. Third time's a charm...

[dcoudert]

comment:45

Well... actually, there is a another issue with the wikipedia link. Sorry.

This

        For more information, see the `Wikipedia article on matchings
        :wikipedia:`Matching_(graph_theory)`

produces something like For more information, see the Wikipediaarticleonmatchings:wikipedia:‘Matching(graphtheory). Check the html.

So you should write

        For more information, see :wikipedia:`Matching_(graph_theory)`

or even better

    .. SEEALSO::

        - :wikipedia:`Matching_(graph_theory)`
        - :meth:`~Graph.matching`

no need for blank line between bullets here.

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

Changed commit from 60cfb32 to 9e76673

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

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

9e76673

Cleaned "SEEALSO"

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

Description changed:

--- 
+++ 
@@ -1 +1 @@
-The Hopcroft-Karp and Eppstein algorithms as implemented in NetworkX compute matchings for bipartite graphs faster than the algorithms for general graphs. I've included an override of the matching method in the bipartite graph class, with parameters that allow for using the old algorithms if desired.
+Is there a way I can build the documentation myself to check for errors? './sage -t src/sage/graphs/bipartite_graph.py' doesn't seem to do it, and I don't see anything in the documentation.

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

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
-Is there a way I can build the documentation myself to check for errors? './sage -t src/sage/graphs/bipartite_graph.py' doesn't seem to do it, and I don't see anything in the documentation.
+The Hopcroft-Karp and Eppstein algorithms as implemented in NetworkX
+compute matchings for bipartite graphs faster than the algorithms for
+general graphs. I've included an override of the matching method in the
+bipartite graph class, with parameters that allow for using the old
+algorithms if desired.

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

comment:48

Is there a way I can build the documentation myself to check for errors? ./sage -t src/sage/graphs/bipartite_graph.py doesn't seem to do it, and I don't see anything in the documentation.

[dcoudert]

comment:49

./sage -docbuild reference html and ./sage -docbuild reference/graphs html to rebuild only the graphs part.

Note that from time to time I have to do make doc-clean && make to rebuild the documentation from scratch. For this patch you should not have to do it.

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

Changed commit from 9e76673 to 4e622a8

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

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

4e622a8

Documentation!

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

comment:51

Thanks. It took some effort but the documentation seems to render correctly now.

[tscrim]

comment:52

Back to positive review.

[vbraun]

comment:53

Various doctest failures, e.g.

sage -t --long --warn-long 71.2 src/sage/combinat/permutation.py
**********************************************************************
File "src/sage/combinat/permutation.py", line 6926, in sage.combinat.permutation.bistochastic_as_sum_of_permutations
Failed example:
    decomp = bistochastic_as_sum_of_permutations(M)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 509, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 872, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.permutation.bistochastic_as_sum_of_permutations[7]>", line 1, in <module>
        decomp = bistochastic_as_sum_of_permutations(M)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/combinat/permutation.py", line 6973, in bistochastic_as_sum_of_permutations
        matching = G.matching(use_edge_labels=True)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/graphs/bipartite_graph.py", line 1365, in matching
        "Hopcroft-Karp or Eppstein")
    ValueError: use_edge_labels can not be used with Hopcroft-Karp or Eppstein
**********************************************************************

[dcoudert]

comment:54

Sorry I did not pass tests on the full library when reviewing this ticket.

One solution is to set the algorithm to None

    def matching(self, value_only=False, algorithm=None,
                 use_edge_labels=False, solver=None, verbose=0):

and then to add after self._scream_if_not_simple():

        if algorithm is None:
            if use_edge_labels:
                algorithm = "Edmonds"
            else:
                algorithm = "Hopcroft-Karp"

You will have to update the documentation accordingly, for instance like

        - ``algorithm`` -- string (default: ``"Hopcroft-Karp"`` if
          ``use_edge_labels==False``, otherwise ``"Edmonds"``)

and add a tests on a weighted graph like:

sage: G = graphs.CycleGraph(4)
sage: B = BipartiteGraph([(u,v,2) for u,v in G.edges(labels=0)])
sage: B.matching(use_edge_labels=True)
[(0, 3, 2), (1, 2, 2)]
sage: B.matching(use_edge_labels=True, value_only=True)
4
sage: B.matching(use_edge_labels=True, value_only=True, algorithm='Edmonds')
4
sage: B.matching(use_edge_labels=True, value_only=True, algorithm='LP')
4.0
sage: B.matching(use_edge_labels=True, value_only=True, algorithm='Eppstein')
Traceback (most recent call last):
...
ValueError: use_edge_labels can not be used with Hopcroft-Karp or Eppstein
sage: B.matching(use_edge_labels=True, value_only=True, algorithm='Hopcroft-Karp')
Traceback (most recent call last):
...
ValueError: use_edge_labels can not be used with Hopcroft-Karp or Eppstein
sage: B.matching(use_edge_labels=False, value_only=True, algorithm='Hopcroft-Karp')
2
sage: B.matching(use_edge_labels=False, value_only=True, algorithm='Eppstein')
2
sage: B.matching(use_edge_labels=False, value_only=True, algorithm='Edmonds')
2
sage: B.matching(use_edge_labels=False, value_only=True, algorithm='LP')
2

[tscrim]

comment:55

+1 Can you make the appropriate changes David?

[dcoudert]

comment:56

I had to create a new branch since I cannot push in branch u/zgershkoff/matchings_in_bipartite_graphs. The new branch is in public/, so you can push commits as well.

Bipartite graphs are used in the following modules. The new branch passes all tests (on my computer), but it's better to double check (as well as docbuild, etc.).

src/sage/combinat/
src/sage/game_theory/
src/sage/graphs/
src/sage/groups/
src/sage/matrix/
src/sage/matroids/

Let's hope this ticket will soon be finalized ;)

---

New commits:

5924a34

trac #22559: gathering all ticket comments up to 55

[dcoudert]

Changed commit from 4e622a8 to 5924a34

[dcoudert]

Changed branch from u/zgershkoff/matchings_in_bipartite_graphs to public/22559

[tscrim]

comment:57

Replying to @dcoudert:

I had to create a new branch since I cannot push in branch u/zgershkoff/matchings_in_bipartite_graphs. The new branch is in public/, so you can push commits as well.

That is the correct behavior and the correct thing to do.

Bipartite graphs are used in the following modules. The new branch passes all tests (on my computer), but it's better to double check (as well as docbuild, etc.).

LGTM too. Thanks.

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

comment:58

I agree with this solution-- better than the options I was considering. Thanks for taking care of it.

[vbraun]

Changed branch from public/22559 to 5924a34

[jdemeyer]

Changed commit from 5924a34 to none

[jdemeyer]

Changed author from Zachary Gershkoff to Zach Gershkoff