# digraph.diameter() returning +Infinity for some cases I'm running Sage 6.4.1 on OS X (Yosemite). Creating a directed graph with n vertices (for any n that I tried) returned +Infinity. EG:

sage: digraphs.Path(10).diameter()
+Infinity


or even

sage: digraphs.ButterflyGraph(5).diameter()
+Infinity


However, both of these Path and Butterfly graphs are finite, connected, directed acyclic graphs so their diameter should always be finite.

edit retag close merge delete

1

The underlying graph is connected. But if you type: digraphs.Path(10).show() you'll see a path from 1 to 2 to 3 and so on. So there is no directed path, for example, from 2 to 1. The distance from 2 to 1 is infinite but the distance from 1 to 2 is one. The diameter is just the maximum of the distances so it has to be infinite.

Sort by » oldest newest most voted

The result is correct. The directed path on 10 vertices contains no path from 9 to 0.

In order to have a finite diameter, a directed graph must be strongly connected. In particular, the diameter of a directed acyclic graph is always infinite.

more

You're right, I was confusing some definitions about connectivity - though it didn't help that G.is_connected() returns True. I can implement my intended functionality using something along the lines of max(filter(lambda x: x != Infinity, G.eccentricity())).