Re: [igraph] Higher order distance matrix

[Minh Nguyen]

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