digraph.diameter() returning +Infinity for some cases

digraph

asked 2015-01-11 23:14:19 +0100

zrathustra
3 ●1

updated 2015-01-14 11:28:01 +0100

FrédéricC

5311 ●4 ●44 ●118

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

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 ( 2015-01-12 02:23:39 +0100 )edit

add a comment

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 ( 2015-01-12 02:37:36 +0100 )edit

add a comment

Your Answer

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

digraph.diameter() returning +Infinity for some cases

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

digraph.diameter() returning +Infinity for some cases edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

digraph.diameter() returning +Infinity for some cases