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: 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:

Status badges

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 4 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/24287
  • Cc jmantysalo added
  • Commit set to af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2
  • Status changed from new to needs_review

I have also cleaned some parts of the method.


New commits:

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

comment:2 Changed 4 years ago by jmantysalo

  • 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 follow-up: Changed 4 years ago by dcoudert

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 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.

comment:5 Changed 4 years ago by git

  • Commit changed from af6a7d0c0b40205630f654aeb7e1c4e198f8d2b2 to ec1af848742cfdb12d83308dd3e5b29f7ca48df4

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

ec1af84trac #24287: implement reviewers comment

comment:6 Changed 4 years ago by git

  • Commit changed from ec1af848742cfdb12d83308dd3e5b29f7ca48df4 to 7af3cdc390b3bbaf98cb4a9332bd03be82754598

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

7af3cdctrac #24287: implement reviewers comment on doc

comment:7 Changed 4 years ago by dcoudert

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

comment:8 Changed 4 years ago by jmantysalo

  • Status changed from needs_review to positive_review

All good.

comment:9 Changed 4 years ago by vbraun

  • Branch changed from u/dcoudert/24287 to 7af3cdc390b3bbaf98cb4a9332bd03be82754598
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.