Opened 4 years ago
Closed 4 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, GitHub, GitLab) | 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 4 years ago by
- Branch set to u/dcoudert/22990
- Commit set to 8067526ad70b28d64219198a29adbdf82a97bbca
- Status changed from new to needs_review
comment:2 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
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 4 years ago by
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 4 years ago by
- 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 4 years ago by
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 4 years ago by
- Status changed from positive_review to needs_work
Reviewer name is missing
comment:9 Changed 4 years ago by
- Reviewers set to Mark Saaltink
- Status changed from needs_work to positive_review
comment:10 Changed 4 years ago by
- Branch changed from u/dcoudert/22990 to 8067526ad70b28d64219198a29adbdf82a97bbca
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
trac #22990: fix issues reported in ticket