Issue with vertex cover for graphs with multiple edges

[dcoudert]

Several issues to fix for vertex_cover with multigraphs

sage: G = Graph([(0,1)]*5 + [(1,2)]*2, multiedges=True)
sage: G.vertex_cover(reduction_rules=False, algorithm='MILP')
[1]
sage: G.vertex_cover(reduction_rules=True, algorithm='MILP')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-47-3efdc00ac3e0> in <module>()
----> 1 G.vertex_cover(reduction_rules=True, algorithm='MILP')

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in vertex_cover(self, algorithm, value_only, reduction_rules, solver, verbosity)
   6622 
   6623                 elif du == 2:
-> 6624                     v,w  = g.neighbors(u)
   6625 
   6626                     if g.has_edge(v,w):

ValueError: need more than 1 value to unpack
sage: G.vertex_cover(reduction_rules=False)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-48-5167d984b139> in <module>()
----> 1 G.vertex_cover(reduction_rules=False)

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in vertex_cover(self, algorithm, value_only, reduction_rules, solver, verbosity)
   6674 
   6675         elif algorithm == "Cliquer" or algorithm == "mcqd":
-> 6676             independent = g.complement().clique_maximum(algorithm=algorithm)
   6677             if value_only:
   6678                 size_cover_g = g.order() - len(independent)

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in complement(self)
  17433 
  17434         """
> 17435         self._scream_if_not_simple()
  17436 
  17437         G = self.copy(data_structure='dense')

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in _scream_if_not_simple(self, allow_loops, allow_multiple_edges)
   1298                    "meantime if you want to use it please disallow "+name+" using "+
   1299                    functions+".")
-> 1300             raise ValueError(msg)
   1301 
   1302     def networkx_graph(self, copy=True):

ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges().

[dcoudert]

I have also cleaned some parts of the method.

---

New commits:

​af6a7d0

trac #24287: fix reported issue for vertex_cover with multiple edges

[jmantysalo]

Seems good, I'll check.

I noticed [v for v in g.vertex_iterator() . . .], which can be said shortly as [v for v in g . . .].

[dcoudert]

What I don't know is if for v in g creates a list of uses an iterator.

[jmantysalo]

Replying to dcoudert:

What I don't know is if for v in g creates a list of uses an iterator.

According to documentation of __iter_ it outputs an iteratort.

Feel free to mark this as positive review if you want. Or you can also correct the input section that says "It can be one of those two values." and then lists three values.

[git]

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

​ec1af84

trac #24287: implement reviewers comment

[git]

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

​7af3cdc

trac #24287: implement reviewers comment on doc

[dcoudert]

I have implemented all your comments. I let you conclude on the status.

[jmantysalo]

All good.