digraph.diameter() returning +Infinity for some cases

digraph

asked 10 years ago

zrathustra
3 ●1

updated 10 years ago

FrédéricC

5426 ●4 ●44 ●121

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.

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 ( 10 years ago )

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 ( 10 years ago )

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 savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

digraph.diameter() returning +Infinity for some cases