[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [igraph] Higher order distance matrix

**From**: |
Minh Nguyen |

**Subject**: |
Re: [igraph] Higher order distance matrix |

**Date**: |
Wed, 1 Jun 2011 19:43:30 +1000 |

Hi Moses,
On Wed, Jun 1, 2011 at 5:25 AM, Moses Boudourides
<address@hidden> wrote:
>* Given a simple undirected graph, I call "higher order distance matrix"*
>* the following modification of the distance matrix (the entries of*
>* which are giving the geodesic distance between nodes):*
>
>* If the (i, j)-entry of the distance matrix is > or = 2, then the same*
>* value is the (i, j)-entry of the higher order distance matrix.*
>* If the (i, j)-entry of the distance matrix = 1, then remove the*
>* connection from i to j, compute the geodesic distance from i to j and*
>* set the latter as the (i, j)-entry of the higher order distance*
>* matrix. (As usual, the distance between two non-connected nodes should*
>* be infinity.)*
>
>* Thus all entries in the higher order distance matrix should be at least 2.*
>
>* Can this be done by igraph? How and with which packages?*
>*From hereon, I'll assume you want to use the igraph C library. What*
you described above can be done using the C library as follows; this
is just a quick and dirty procedure. Let G = (V, E) be a simple
undirected graph where n = |V| and k = |E|. Denote the distance
between vertices u and v by d(u,v). Use the C library function
igraph_shortest_paths() to obtain a matrix M of distances between each
pair of distinct vertices in G. This should take roughly O(n^2 + nk)
time. Now M[i,j] = 1 if and only if (i,j) is an edge of G. Thus you
iterate over each edge in E, instead of testing for a matrix entry
being one. In particular:
for each (u,v) in E
delete (u,v) from G
use igraph_shortest_paths() to compute d(u,v)
set M[u,v] and M[v,u] to d(u,v)
restore (u,v) to G
The above loop should take time roughly O(nk + k^2) so that the whole
algorithm has runtime O(n^2 + 2nk + k^2).
--
Regards
Minh Van Nguyen

**Re: [igraph] Higher order distance matrix**,
*Minh Nguyen* **<=**