Re: [igraph] Higher order distance matrix

[Moses Boudourides]

Thank you, Minh,

Best,

--Moses


On Wed, Jun 1, 2011 at 11:43 AM, Minh Nguyen <address@hidden> wrote:
> 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
>