Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Geodesic distance from an adjacency matrix

Subject: Geodesic distance from an adjacency matrix

From: Russ Branaghan

Date: 23 Feb, 2009 17:07:02

Message: 1 of 6

Hello,

I have the 27 x 27 adjacency matrix (below). Is there an easy way to derive the graph theoretic (geodesic) distance between each pari of nodes, and represent this as a 27 x 27 matrix as well?

Thanks in advance,

Russ

 Columns 1 through 16

     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
     0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0
     0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
     0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
     1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0
     1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
     0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0
     0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

  Columns 17 through 27

     0 0 0 0 0 0 0 1 1 0 0
     0 0 0 0 1 0 0 1 0 0 0
     0 0 0 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 0 0 0 1 0
     0 0 0 0 0 0 0 0 0 1 0
     0 0 0 1 0 0 0 0 0 0 0
     0 0 1 0 0 0 0 0 0 0 0
     0 1 0 0 0 0 0 0 0 0 0
     1 0 0 0 0 0 1 0 0 1 1
     0 0 1 0 0 0 0 0 0 0 0
     0 0 1 0 0 0 0 0 0 0 0
     0 0 1 0 0 0 0 0 0 0 0
     0 1 0 0 0 0 0 0 0 1 0
     0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 1 0 0 1 1 0 0
     0 0 0 1 0 0 0 0 0 0 0
     0 0 0 0 0 1 0 0 0 0 0
     0 0 0 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 1 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 1 0 0 0 0
     1 0 0 0 0 0 0 0 0 0 0
     0 0 1 0 1 0 0 0 0 0 0
     0 1 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0

Subject: Geodesic distance from an adjacency matrix

From: russell.fung@gmail.com

Date: 24 Feb, 2009 14:43:41

Message: 2 of 6

You may want to look at Floyd's algorithm.

Russell

Subject: Geodesic distance from an adjacency matrix

From: Russ Branaghan

Date: 25 Feb, 2009 14:05:05

Message: 3 of 6

"russell.fung@gmail.com" <russell.fung@gmail.com> wrote in message <1bf1f628-7ca5-4aa4-9a25-6c19cf80c7e2@h5g2000yqh.googlegroups.com>...
> You may want to look at Floyd's algorithm.
>
> Russell


Thank you Russell. Will do.

Subject: Geodesic distance from an adjacency matrix

From: Roger Stafford

Date: 13 Mar, 2009 02:28:02

Message: 4 of 6

"Russ Branaghan" <russ.branaghan.nospam@asu.edu> wrote in message <go3j6h$iq3$1@fred.mathworks.com>...
> "russell.fung@gmail.com" <russell.fung@gmail.com> wrote in message <1bf1f628-7ca5-4aa4-9a25-6c19cf80c7e2@h5g2000yqh.googlegroups.com>...
> > You may want to look at Floyd's algorithm.
> > Russell
> Thank you Russell. Will do.

  Russ, I laid your problem aside and am only now getting back to it. The following is another way of solving your problem. Let me know how well it measures up to Floyd's algorithm. This is also an order n^3 algorithm. Call the adjacency matrix 'a'.

 n = size(a,1);
 c = repmat(inf,n,n);
 for k = 1:n
   f = k;
   s = 0;
   while ~isempty(f)
     c(k,f) = s;
     s = s+1;
     f = find(any(a(f,:),1)&c(k,:)==inf);
   end
 end

The matrix c is then the desired distance matrix.

Roger Stafford

Subject: Geodesic distance from an adjacency matrix

From: M L

Date: 2 Dec, 2009 18:54:03

Message: 5 of 6

Roger,

I am working on a matrix of the order 8K x 8K.
I need to find the geodesic distances.
However, the matlab code below runs in an infinite loop for me.
Can you please help?

Thanks!

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gpcgbh$82b$1@fred.mathworks.com>...
> "Russ Branaghan" <russ.branaghan.nospam@asu.edu> wrote in message <go3j6h$iq3$1@fred.mathworks.com>...
> > "russell.fung@gmail.com" <russell.fung@gmail.com> wrote in message <1bf1f628-7ca5-4aa4-9a25-6c19cf80c7e2@h5g2000yqh.googlegroups.com>...
> > > You may want to look at Floyd's algorithm.
> > > Russell
> > Thank you Russell. Will do.
>
> Russ, I laid your problem aside and am only now getting back to it. The following is another way of solving your problem. Let me know how well it measures up to Floyd's algorithm. This is also an order n^3 algorithm. Call the adjacency matrix 'a'.
>
> n = size(a,1);
> c = repmat(inf,n,n);
> for k = 1:n
> f = k;
> s = 0;
> while ~isempty(f)
> c(k,f) = s;
> s = s+1;
> f = find(any(a(f,:),1)&c(k,:)==inf);
> end
> end
>
> The matrix c is then the desired distance matrix.
>
> Roger Stafford

Subject: Geodesic distance from an adjacency matrix

From: Jerin leno

Date: 30 Nov, 2010 05:09:05

Message: 6 of 6

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gpcgbh$82b$1@fred.mathworks.com>...
> "Russ Branaghan" <russ.branaghan.nospam@asu.edu> wrote in message <go3j6h$iq3$1@fred.mathworks.com>...
> > "russell.fung@gmail.com" <russell.fung@gmail.com> wrote in message <1bf1f628-7ca5-4aa4-9a25-6c19cf80c7e2@h5g2000yqh.googlegroups.com>...
> > > You may want to look at Floyd's algorithm.
> > > Russell
> > Thank you Russell. Will do.
>
> Russ, I laid your problem aside and am only now getting back to it. The following is another way of solving your problem. Let me know how well it measures up to Floyd's algorithm. This is also an order n^3 algorithm. Call the adjacency matrix 'a'.
>
> n = size(a,1);
> c = repmat(inf,n,n);
> for k = 1:n
> f = k;
> s = 0;
> while ~isempty(f)
> c(k,f) = s;
> s = s+1;
> f = find(any(a(f,:),1)&c(k,:)==inf);
> end
> end
>
> The matrix c is then the desired distance matrix.
>
> Roger Stafford

will this algo can be used for vertex weight greater one..how this could be modified

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us