Opened 4 years ago
Closed 4 years ago
#24287 closed defect (fixed)
Issue with vertex cover for graphs with multiple edges
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  graph theory  Keywords:  
Cc:  jmantysalo  Merged in:  
Authors:  David Coudert  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  7af3cdc (Commits, GitHub, GitLab)  Commit:  7af3cdc390b3bbaf98cb4a9332bd03be82754598 
Dependencies:  Stopgaps: 
Description
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) <ipythoninput473efdc00ac3e0> in <module>() > 1 G.vertex_cover(reduction_rules=True, algorithm='MILP') /Users/dcoudert/sage/local/lib/python2.7/sitepackages/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) <ipythoninput485167d984b139> in <module>() > 1 G.vertex_cover(reduction_rules=False) /Users/dcoudert/sage/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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().
Change History (9)
comment:1 Changed 4 years ago by
 Branch set to u/dcoudert/24287
 Cc jmantysalo added
 Commit set to af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Reviewers set to Jori Mäntysalo
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 . . .]
.
comment:3 followup: ↓ 4 Changed 4 years ago by
What I don't know is if for v in g
creates a list of uses an iterator.
comment:4 in reply to: ↑ 3 Changed 4 years ago by
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.
comment:5 Changed 4 years ago by
 Commit changed from af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2 to ec1af848742cfdb12d83308dd3e5b29f7ca48df4
Branch pushed to git repo; I updated commit sha1. New commits:
ec1af84  trac #24287: implement reviewers comment

comment:6 Changed 4 years ago by
 Commit changed from ec1af848742cfdb12d83308dd3e5b29f7ca48df4 to 7af3cdc390b3bbaf98cb4a9332bd03be82754598
Branch pushed to git repo; I updated commit sha1. New commits:
7af3cdc  trac #24287: implement reviewers comment on doc

comment:7 Changed 4 years ago by
I have implemented all your comments. I let you conclude on the status.
comment:9 Changed 4 years ago by
 Branch changed from u/dcoudert/24287 to 7af3cdc390b3bbaf98cb4a9332bd03be82754598
 Resolution set to fixed
 Status changed from positive_review to closed
I have also cleaned some parts of the method.
New commits:
trac #24287: fix reported issue for vertex_cover with multiple edges