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: | sage-8.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) <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().
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 follow-up: 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