Opened 3 years ago

Closed 3 years ago

#22990 closed defect (fixed)

Infinite loop in vertex_disjoint_paths

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.0
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Mark Saaltink
Report Upstream: N/A Work issues:
Branch: 8067526 (Commits) Commit: 8067526ad70b28d64219198a29adbdf82a97bbca
Dependencies: Stopgaps:

Description

The following example loops forever

sage: D = digraphs.Path(2)
sage: D.vertex_disjoint_paths(0,1)

and this one raises an error

sage: D = digraphs.Path(2)
sage: D.vertex_disjoint_paths(1,0)
---------------------------------------------------------------------------
LookupError                               Traceback (most recent call last)
...
LookupError: Vertex (1) is not a vertex of the graph.

Change History (10)

comment:1 Changed 3 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/22990
  • Commit set to 8067526ad70b28d64219198a29adbdf82a97bbca
  • Status changed from new to needs_review

New commits:

8067526trac #22990: fix issues reported in ticket

comment:2 Changed 3 years ago by msaaltink

This looks good, but there is one inconsistency with other path functions in the corner case where the source and destination are the same. 'all_paths' allows for a length-0 path while 'vertex_disjoint_paths' does not.

sage: D = DiGraph([(0,1,'a'), (1,2,'b')])
sage: D.all_paths(0,0)
[[0]]
sage: D.vertex_disjoint_paths(0,0)
[]

Of course Menger's theorem does not apply here because a vertex cut has to be between two distinct vertices, but since [0] is a path it would make some sense to allow it as a vertex-disjoint path here.

comment:3 Changed 3 years ago by dcoudert

Actually I would do the opposite and avoid returning 0-length path in all_paths.

For me this is not consistent.

sage: G = graphs.CompleteGraph(4)
sage: G.all_paths(0,1)
[[0, 1], [0, 2, 1], [0, 2, 3, 1], [0, 3, 1], [0, 3, 2, 1]]
sage: G.all_paths(0,0)
[[0]]

comment:4 Changed 3 years ago by msaaltink

I don't see the inconsistency there.

There are other places in Sage where 0-length paths are more consistent with the documentation. For example, for G.distance we have "Returns the (directed) distance from u to v in the (di)graph, i.e. the length of the shortest path from u to v.", and G.distance(0,0) returns 0. Similarly, G.shortest_path(0,0) returns 0 and the documentation says it will return a path from u to v. And G.shortest_paths(0) includes the length-0 path from 0 to itself.

It is certainly true that not all authors (of Graph Theory books) allow 0-length paths, but if you want to ban them there are several functions that need to be changed.

That all said, this small inconsistency is not a show-stopper if you do not want to change it, but I always like to see the edge cases handled properly.

comment:5 Changed 3 years ago by dcoudert

Other path functions are clearly inconsistent and must be quickly patched:

sage: G = Graph()
sage: G.add_edge(10,11)
sage: G.has_edge(10,11)
True
sage: 0 in G
False
sage: G.shortest_path(0,0)
[0]
sage: G.shortest_path_length(0,0)
0
sage: G.distance(0,0)
0
sage: G.all_paths(0,0)
[[0]]

So I believe the behavior I propose for this method is the correct one.

comment:6 Changed 3 years ago by msaaltink

  • Status changed from needs_review to positive_review

Well, I agree that these other functions ought to be fixed; it seems clear that the vertices in a path need to be actual vertices of the graph! Perhaps I will open a ticket for that.

I still think it would be slightly better for you to allow for 0-length paths, but don't see it as worth fighting over. Everything else in the commit looks fine, so I'll give it a positive review.

comment:7 Changed 3 years ago by dcoudert

Thank you.

For the record, I'm not aware of any book/paper using or computing edge/vertex disjoint paths that considers 0-length path.

comment:8 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name is missing

comment:9 Changed 3 years ago by msaaltink

  • Reviewers set to Mark Saaltink
  • Status changed from needs_work to positive_review

comment:10 Changed 3 years ago by vbraun

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