improvement of the feedback_edge_set method

[dcoudert]

As for #23984, we speed up the resolution of the constraint generation formulation adding more constraints per round, i.e., as many constraints as edge disjoint circuits.

Before

sage: D = DiGraph('q??D@O_A_AO?O???a_?a_o??G???CO?_?N_???C?o?aGCc_??O???@?G@??@??_@???@?I?C??G?G@@HC?_?GCAG_??_???????GPo_??????C?Go@??@O?@???GB?@_QA_OAC??W?OOG__OC?C????????cA??G?WGA??_???P???C@A?_??@_IBSD??A?_?Q??o@O????O?C?@_A?O@?G???OS@??G?GAOO??????T??A@A????A???@AO?O??IQ?@L?_?_?C?CG?A??A?DC??AO@@????WOG????`??A???_E_G????S?K?????@?AO?????G?C?A_?G??g?@???O???G?G??A???G_@???D??OA?_OAG??MA?_?A??@?A??C?????OO??????C????O@CG???A??_O')
sage: %timeit D.feedback_edge_set()
1 loop, best of 3: 3.85 s per loop

After

sage: D = DiGraph('q??D@O_A_AO?O???a_?a_o??G???CO?_?N_???C?o?aGCc_??O???@?G@??@??_@???@?I?C??G?G@@HC?_?GCAG_??_???????GPo_??????C?Go@??@O?@???GB?@_QA_OAC??W?OOG__OC?C????????cA??G?WGA??_???P???C@A?_??@_IBSD??A?_?Q??o@O????O?C?@_A?O@?G???OS@??G?GAOO??????T??A@A????A???@AO?O??IQ?@L?_?_?C?CG?A??A?DC??AO@@????WOG????`??A???_E_G????S?K?????@?AO?????G?C?A_?G??g?@???O???G?G??A???G_@???D??OA?_OAG??MA?_?A??@?A??C?????OO??????C????O@CG???A??_O')
sage: %timeit D.feedback_edge_set()
1 loop, best of 3: 1.62 s per loop

This patch also fix an issue for digraphs with loops (see [#23989 comment:5])

Component: graph theory

Author: David Coudert

Branch/Commit: 972edd0

Reviewer: Travis Scrimshaw

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

[dcoudert]

Branch: u/dcoudert/23989

[dcoudert]

comment:1

I have also added a pre-processing to solve the problem on each strongly connected component.
In addition, we ensure that loops and multiple edges are well handled.

---

New commits:

8a45f87	trac #23989: cleaning original code
7037730	trac #23989: add more constraints
ea4d4c9	trac #23989: deal with loops
53e701d	trac #23989: doctest for checking that multiedges are properly taken into account
ff893cc	trac #23989: decomposition into strongly connected components

[dcoudert]

Commit: ff893cc

[sagetrac-git]

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

6a319fc

trac #23989: remove labels of loops

[sagetrac-git]

Changed commit from ff893cc to 6a319fc

[dcoudert]

comment:3

This method has never returned labeled edges, so I have removed labels of loops.

[sagetrac-git]

Changed commit from 6a319fc to 972edd0

[sagetrac-git]

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

972edd0

trac #23989: precision for multigraphs

[dcoudert]

comment:5

I added some comments for graphs with multiple edges (mostly to convince myself that it's correct).

This patch also fix the following issue for graphs with loops.

sage: D = DiGraph(loops=True)
sage: D.add_edge(0,0)
sage: D.feedback_edge_set()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-81-9e5a629c6d7c> in <module>()
----> 1 D.feedback_edge_set()

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/digraph.pyc in feedback_edge_set(self, constraint_generation, value_only, solver, verbose)
   1573                 for u,v in self.edges(labels = False):
   1574                     if p.get_values(b[u,v]) < .5:
-> 1575                         h.add_edge(u,v)
   1576 
   1577                 # Is the digraph acyclic ?

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in add_edge(self, u, v, label)
  10416                     pass
  10417 
> 10418         self._backend.add_edge(u, v, label, self._directed)
  10419 
  10420     def add_edges(self, edges, loops=True):

/Users/dcoudert/sage/src/sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17249)()
   1488 
   1489         if u_int == v_int and not self._loops:
-> 1490             raise ValueError(f"cannot add edge from {u!r} to {v!r} in graph without loops")
   1491 
   1492         if not self.multiple_edges(None):

ValueError: cannot add edge from 0 to 0 in graph without loops

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

LGTM.

[dcoudert]

comment:7

Thank you very much.

[vbraun]

Changed branch from u/dcoudert/23989 to 972edd0