Ask Your Question

digraph.diameter() returning +Infinity for some cases

asked 2015-01-11 16:14:19 -0600

zrathustra gravatar image

updated 2015-01-14 04:28:01 -0600

FrédéricC gravatar image

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

or even

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

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

edit retag flag offensive close merge delete



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.

dazedANDconfused gravatar imagedazedANDconfused ( 2015-01-11 19:23:39 -0600 )edit

1 answer

Sort by » oldest newest most voted

answered 2015-01-11 19:20:54 -0600

Nathann gravatar image

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.

edit flag offensive delete link 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())).

zrathustra gravatar imagezrathustra ( 2015-01-11 19:37:36 -0600 )edit

Your Answer

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

Add Answer

Question Tools


Asked: 2015-01-11 16:14:19 -0600

Seen: 53 times

Last updated: Jan 11 '15