[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] Diameter vs. longest shortest paths
From: |
Claudia Muller-Birn |
Subject: |
[igraph] Diameter vs. longest shortest paths |
Date: |
Tue, 8 Mar 2011 09:45:55 +0100 |
Dear all,
Another question but this time regarding calculating the diameter vs. the max
shortest.path in a graph.
The diameter of a graph is the length of the longest geodesic. I thought
therefore by applying both functions to the same graph, the results should not
differ*. Well, based on the following examples I derive the following insights:
a) The diameter takes the directness of a graph into account, the shortest.path
don't (see case 1 and 2 below)
b) The diameter and the shortest.path takes the weight of an edge into account
by adding the weights of each edge (see case 3 and 4).
Are both insights correct?
In order to make it easier to follow my thoughts, I prepared again some simple
examples:
#case 1: undirected and unweighted
> g <- graph( c(0,1 , 1,2 , 0,4 , 4,3 , 4,9 , 4,5 , 6,7 , 0,7 , 8,2 ),
> directed=FALSE )
> diameter(g)
[1] 5
> get.diameter(g)
[1] 3 4 0 1 2 8
> max(shortest.paths(g))
[1] 5
#case 2: directed and unweighted
> g0 <- graph( c(0,1 , 1,2 , 0,4 , 4,3 , 4,9 , 4,5 , 6,7 , 0,7 , 8,2 ),
> directed=TRUE )
> diameter(g0)
[1] 2
> get.diameter(g0)
[1] 0 1 2
> max(shortest.paths(g0))
[1] 5
#case 3: undirected and weighted
> g1 <- graph( c(0,1 , 1,2 , 0,4 , 4,3 , 4,9 , 4,5 , 6,7 , 0,7 , 8,2 ),
> directed=FALSE )
> E(g1)$weight <- c(5,10,1,3,6,1,1,5,1)
> diameter(g1)
[1] 23
> get.diameter(g1)
[1] 8 2 1 0 4 9
> max(shortest.paths(g1))
[1] 23
#case 4: directed and weighted
> g2 <- graph( c(0,1 , 1,2 , 0,4 , 4,3 , 4,9 , 4,5 , 6,7 , 0,7 , 8,2 ),
> directed=TRUE )
> E(g2)$weight <- c(5,10,1,3,6,1,1,5,1)
> diameter(g2)
[1] 15
> get.diameter(g2)
[1] 0 1 2
> max(shortest.paths(g2))
[1] 23
Thank you very much again for your help!
Best,
Claudia
* the reason for this email is that I had different results in igraph and gephi.
- [igraph] Diameter vs. longest shortest paths,
Claudia Muller-Birn <=