Opened 5 years ago
Closed 5 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 5 years ago by
Authors:  → David Coudert 

Branch:  → u/dcoudert/24287 
Cc:  jmantysalo added 
Commit:  → af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2 
Status:  new → needs_review 
comment:2 Changed 5 years ago by
Reviewers:  → 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 5 years ago by
What I don't know is if for v in g
creates a list of uses an iterator.
comment:4 Changed 5 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 5 years ago by
Commit:  af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2 → ec1af848742cfdb12d83308dd3e5b29f7ca48df4 

Branch pushed to git repo; I updated commit sha1. New commits:
ec1af84  trac #24287: implement reviewers comment

comment:6 Changed 5 years ago by
Commit:  ec1af848742cfdb12d83308dd3e5b29f7ca48df4 → 7af3cdc390b3bbaf98cb4a9332bd03be82754598 

Branch pushed to git repo; I updated commit sha1. New commits:
7af3cdc  trac #24287: implement reviewers comment on doc

comment:7 Changed 5 years ago by
I have implemented all your comments. I let you conclude on the status.
comment:9 Changed 5 years ago by
Branch:  u/dcoudert/24287 → 7af3cdc390b3bbaf98cb4a9332bd03be82754598 

Resolution:  → fixed 
Status:  positive_review → closed 
I have also cleaned some parts of the method.
New commits:
trac #24287: fix reported issue for vertex_cover with multiple edges