Opened 4 years ago

Closed 4 years ago

# Infinite loop in vertex_disjoint_paths

Reported by: Owned by: dcoudert major sage-8.0 graph theory David Coudert Mark Saaltink N/A 8067526 8067526ad70b28d64219198a29adbdf82a97bbca

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

### comment:1 Changed 4 years ago by dcoudert

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

New commits:

 ​8067526 `trac #22990: fix issues reported in ticket`

### comment:2 Changed 4 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 4 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 4 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 4 years ago by dcoudert

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

```sage: G = Graph()
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 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 4 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 4 years ago by vbraun

• Status changed from positive_review to needs_work

Reviewer name is missing

### comment:9 Changed 4 years ago by msaaltink

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