Ask Your Question

# 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

## Comments

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.

( 2015-01-12 02:23:39 +0200 )edit

## 1 Answer

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

## Comments

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

( 2015-01-12 02:37:36 +0200 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2015-01-11 23:14:19 +0200

Seen: 119 times

Last updated: Jan 12 '15