Ask Your Question
0

digraph.diameter() returning +Infinity for some cases

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

zrathustra gravatar image

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

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()
+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 flag offensive 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.

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

1 answer

Sort by » oldest newest most voted
1

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

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

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

zrathustra gravatar imagezrathustra ( 2015-01-11 19:37:36 -0500 )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

Stats

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

Seen: 61 times

Last updated: Jan 11 '15