Got Questions? Get Answers.
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:
Converting an Adjacensy List to Adjacency Matrix

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Qusai A

Date: 11 Jun, 2010 21:12:04

Message: 1 of 24

Hi,

I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
AL= 0 2 3 1
       1 0 2
       2 0 1 2
       3 4 0
       4 3
which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
The Adjacency matrix shoul look like this:
AM= [
             0 1 1 1 0
             1 0 1 0 0
             1 1 1 0 0
             1 0 0 0 1
             0 0 0 1 0 ]


Many thanks in advance.

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Oleg Komarov

Date: 11 Jun, 2010 22:30:31

Message: 2 of 24

"Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> Hi,
>
> I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> AL= 0 2 3 1
> 1 0 2
> 2 0 1 2
> 3 4 0
> 4 3
> which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> The Adjacency matrix shoul look like this:
> AM= [
> 0 1 1 1 0
> 1 0 1 0 0
> 1 1 1 0 0
> 1 0 0 0 1
> 0 0 0 1 0 ]
>
>
> Many thanks in advance.

How did you store the AL??
Do you have NaNs to pad the array?

Oleg

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Oleg Komarov

Date: 11 Jun, 2010 22:30:31

Message: 3 of 24

"Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> Hi,
>
> I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> AL= 0 2 3 1
> 1 0 2
> 2 0 1 2
> 3 4 0
> 4 3
> which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> The Adjacency matrix shoul look like this:
> AM= [
> 0 1 1 1 0
> 1 0 1 0 0
> 1 1 1 0 0
> 1 0 0 0 1
> 0 0 0 1 0 ]
>
>
> Many thanks in advance.

How did you store the AL??
Do you have NaNs to pad the array?

Oleg

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Qusai A

Date: 11 Jun, 2010 22:59:05

Message: 4 of 24

"Oleg Komarov" <oleg.komarovRemove.this@hotmail.it> wrote in message <huude7$ho5$1@fred.mathworks.com>...
> "Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> > Hi,
> >
> > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > AL= 0 2 3 1
> > 1 0 2
> > 2 0 1 2
> > 3 4 0
> > 4 3
> > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > The Adjacency matrix shoul look like this:
> > AM= [
> > 0 1 1 1 0
> > 1 0 1 0 0
> > 1 1 1 0 0
> > 1 0 0 0 1
> > 0 0 0 1 0 ]
> >
> >
> > Many thanks in advance.
>
> How did you store the AL??
> Do you have NaNs to pad the array?
>
> Oleg

Hi Oleg,

I have AL in an outside *.txt file. When I import the file to the Matlab environment I get a matrix with NaN to fill in the empty spaces of the dat, i.e it looks like this:

             0 2 3 1
             1 0 2 NaN
             2 0 1 2
             3 4 0 NaN
             4 3 NaN NaN

Many Thanks.

Subject: Converting an Adjacensy List to Adjacency Matrix

From: us

Date: 12 Jun, 2010 14:11:05

Message: 5 of 24

"Qusai A" <gqusai@hotmail.com> wrote in message <huuf3p$2vg$1@fred.mathworks.com>...
> "Oleg Komarov" <oleg.komarovRemove.this@hotmail.it> wrote in message <huude7$ho5$1@fred.mathworks.com>...
> > "Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> > > Hi,
> > >
> > > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > > AL= 0 2 3 1
> > > 1 0 2
> > > 2 0 1 2
> > > 3 4 0
> > > 4 3
> > > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > > The Adjacency matrix shoul look like this:
> > > AM= [
> > > 0 1 1 1 0
> > > 1 0 1 0 0
> > > 1 1 1 0 0
> > > 1 0 0 0 1
> > > 0 0 0 1 0 ]
> > >
> > >
> > > Many thanks in advance.
> >
> > How did you store the AL??
> > Do you have NaNs to pad the array?
> >
> > Oleg
>
> Hi Oleg,
>
> I have AL in an outside *.txt file. When I import the file to the Matlab environment I get a matrix with NaN to fill in the empty spaces of the dat, i.e it looks like this:
>
> 0 2 3 1
> 1 0 2 NaN
> 2 0 1 2
> 3 4 0 NaN
> 4 3 NaN NaN
>
> Many Thanks.

how can your adjacency mat AM be the result of your input(?)...
please, clarify...

us

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 12 Jun, 2010 14:30:25

Message: 6 of 24

"Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> Hi,
>
> I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> AL= 0 2 3 1
> 1 0 2
> 2 0 1 2
> 3 4 0
> 4 3
> which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> The Adjacency matrix shoul look like this:
> AM= [
> 0 1 1 1 0
> 1 0 1 0 0
> 1 1 1 0 0
> 1 0 0 0 1
> 0 0 0 1 0 ]
>

AL=[0 2 3 1;
    1 0 2 NaN;
    2 0 1 2;
    3 4 0 NaN;
    4 3 NaN NaN]

I = repmat(AL(:,1)+1,1,size(AL,2)-1);
J = AL(:,2:end)+1;
b = ~isnan(J);
AM = accumarray([I(b) J(b)],1)>0

% Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 12 Jun, 2010 14:44:07

Message: 7 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv05m0$2cv$1@fred.mathworks.com>...
> "Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> > Hi,
> >
> > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > AL= 0 2 3 1
> > 1 0 2
> > 2 0 1 2
> > 3 4 0
> > 4 3
> > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > The Adjacency matrix shoul look like this:
> > AM= [
> > 0 1 1 1 0
> > 1 0 1 0 0
> > 1 1 1 0 0
> > 1 0 0 0 1
> > 0 0 0 1 0 ]
> >
>
> AL=[0 2 3 1;
> 1 0 2 NaN;
> 2 0 1 2;
> 3 4 0 NaN;
> 4 3 NaN NaN]
>
> I = repmat(AL(:,1)+1,1,size(AL,2)-1);
> J = AL(:,2:end)+1;
> b = ~isnan(J);
> AM = accumarray([I(b) J(b)],1)>0
>

It's simpler to replace the last line like with this:
AM = accumarray([I(b) J(b)],true)

Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: us

Date: 12 Jun, 2010 14:55:09

Message: 8 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv06fn$l7m$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv05m0$2cv$1@fred.mathworks.com>...
> > "Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> > > Hi,
> > >
> > > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > > AL= 0 2 3 1
> > > 1 0 2
> > > 2 0 1 2
> > > 3 4 0
> > > 4 3
> > > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > > The Adjacency matrix shoul look like this:
> > > AM= [
> > > 0 1 1 1 0
> > > 1 0 1 0 0
> > > 1 1 1 0 0
> > > 1 0 0 0 1
> > > 0 0 0 1 0 ]
> > >
> >
> > AL=[0 2 3 1;
> > 1 0 2 NaN;
> > 2 0 1 2;
> > 3 4 0 NaN;
> > 4 3 NaN NaN]
> >
> > I = repmat(AL(:,1)+1,1,size(AL,2)-1);
> > J = AL(:,2:end)+1;
> > b = ~isnan(J);
> > AM = accumarray([I(b) J(b)],1)>0
> >
>
> It's simpler to replace the last line like with this:
> AM = accumarray([I(b) J(b)],true)
>
> Bruno

yes, what i thought as well - and it does reproduce the suggested solution...
however: is this the correct adjacency mat given the OP's data(?)...

us

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 12 Jun, 2010 15:02:05

Message: 9 of 24

"us " <us@neurol.unizh.ch> wrote in message <hv074d$1a5$1@fred.mathworks.com>...

> > > > Hi,
> > > >
> > > > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > > > AL= 0 2 3 1
> > > > 1 0 2
> > > > 2 0 1 2
> > > > 3 4 0
> > > > 4 3
> > > > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > > > The Adjacency matrix shoul look like this:
> > > > AM= [
> > > > 0 1 1 1 0
> > > > 1 0 1 0 0
> > > > 1 1 1 0 0
> > > > 1 0 0 0 1
> > > > 0 0 0 1 0 ]

>
> yes, what i thought as well - and it does reproduce the suggested solution...
> however: is this the correct adjacency mat given the OP's data(?)...
>

I do get this with the code, they do look identical no?

AM =

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

Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: us

Date: 12 Jun, 2010 15:06:05

Message: 10 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv07hd$pjf$1@fred.mathworks.com>...
> "us " <us@neurol.unizh.ch> wrote in message <hv074d$1a5$1@fred.mathworks.com>...
>
> > > > > Hi,
> > > > >
> > > > > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > > > > AL= 0 2 3 1
> > > > > 1 0 2
> > > > > 2 0 1 2
> > > > > 3 4 0
> > > > > 4 3
> > > > > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > > > > The Adjacency matrix shoul look like this:
> > > > > AM= [
> > > > > 0 1 1 1 0
> > > > > 1 0 1 0 0
> > > > > 1 1 1 0 0
> > > > > 1 0 0 0 1
> > > > > 0 0 0 1 0 ]
>
> >
> > yes, what i thought as well - and it does reproduce the suggested solution...
> > however: is this the correct adjacency mat given the OP's data(?)...
> >
>
> I do get this with the code, they do look identical no?
>
> AM =
>
> 0 1 1 1 0
> 1 0 1 0 0
> 1 1 1 0 0
> 1 0 0 0 1
> 0 0 0 1 0
>
> Bruno

yes, that's why i said: ...and it does reproduce the suggested solution...
however, again: is this the correct adjacency mat given the OP's data(?)...

just a thought...
us

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 12 Jun, 2010 15:13:05

Message: 11 of 24

"us " <us@neurol.unizh.ch> wrote in message <hv07ot$adu$1@fred.mathworks.com>...
>
>
> yes, that's why i said: ...and it does reproduce the suggested solution...
> however, again: is this the correct adjacency mat given the OP's data(?)...
>
> just a thought...
> us

It's surely "undirected graph" with knots # 0, 4 ordered in 1st - 5th position. I was not in doubt five minutes ago.

Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: us

Date: 12 Jun, 2010 15:26:05

Message: 12 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv0861$5kc$1@fred.mathworks.com>...
> "us " <us@neurol.unizh.ch> wrote in message <hv07ot$adu$1@fred.mathworks.com>...
> >
> >
> > yes, that's why i said: ...and it does reproduce the suggested solution...
> > however, again: is this the correct adjacency mat given the OP's data(?)...
> >
> > just a thought...
> > us
>
> It's surely "undirected graph" with knots # 0, 4 ordered in 1st - 5th position. I was not in doubt five minutes ago.
>
> Bruno

good...
i thought along this line...

     al=[
          0 2 3 1
          1 0 2 NaN
          2 0 1 2
          3 4 0 NaN
          4 3 NaN NaN
     ];
     al=reshape(al.',[],1);
     al=al(~isnan(al))+1; % <- offset for node #0
     am=accumarray([al(1:end-1),al(2:end)],1)
%{
% am =
     0 1 2 0 1
     1 1 1 0 0
     1 0 1 2 0
     0 1 0 0 1
     1 0 0 1 0
%}

but, most likely, i'm missing something...
us

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Qusai A

Date: 12 Jun, 2010 18:38:05

Message: 13 of 24

"us " <us@neurol.unizh.ch> wrote in message <hv04hp$mtd$1@fred.mathworks.com>...
> "Qusai A" <gqusai@hotmail.com> wrote in message <huuf3p$2vg$1@fred.mathworks.com>...
> > "Oleg Komarov" <oleg.komarovRemove.this@hotmail.it> wrote in message <huude7$ho5$1@fred.mathworks.com>...
> > > "Qusai A" <gqusai@hotmail.com> wrote in message <huu8r4$ir2$1@fred.mathworks.com>...
> > > > Hi,
> > > >
> > > > I am trying to convert a an adjacency list into an adjacency matrix, so i have the following adjacency list:
> > > > AL= 0 2 3 1
> > > > 1 0 2
> > > > 2 0 1 2
> > > > 3 4 0
> > > > 4 3
> > > > which represents an undirected graph for which the nodes 0,2,3,and 1 are connected. And nodes 1,0, and 2 are connected and so on.....
> > > > The Adjacency matrix shoul look like this:
> > > > AM= [
> > > > 0 1 1 1 0
> > > > 1 0 1 0 0
> > > > 1 1 1 0 0
> > > > 1 0 0 0 1
> > > > 0 0 0 1 0 ]
> > > >
> > > >
> > > > Many thanks in advance.
> > >
> > > How did you store the AL??
> > > Do you have NaNs to pad the array?
> > >
> > > Oleg
> >
> > Hi Oleg,
> >
> > I have AL in an outside *.txt file. When I import the file to the Matlab environment I get a matrix with NaN to fill in the empty spaces of the dat, i.e it looks like this:
> >
> > 0 2 3 1
> > 1 0 2 NaN
> > 2 0 1 2
> > 3 4 0 NaN
> > 4 3 NaN NaN
> >
> > Many Thanks.
>
> how can your adjacency mat AM be the result of your input(?)...
> please, clarify...
>
> us

Dear US, Oleg, and Bruno,

Sorry for the confusion but may be if you imagine a hidden column to the left of the AM consists of the numbers 0 to 4 ( this represents the nodes at the start of each line in the graph) and another hidden row above the first row of the AM consists of the numbers 0 to 4 ( this represents the nodes at the end of each line). i.e the AM should look like this:
AM= [ 0 1 2 3 4

 0 0 1 1 1 0
 1 1 0 1 0 0
 2 1 1 1 0 0
 3 1 0 0 0 1
 4 0 0 0 1 0 ]

So for the first row 0 is connected to 1,2,and 3. This is shown in the first row of the AL.



More DETAILED explanation ,sorry for being so detailed :)

The Matrix
0 2 3 1
1 0 2 NaN
2 0 1 2
3 4 0 NaN
4 3 NaN NaN

means that :
For the first row: node 0 is connected to 2,3, and 1. i,e there is a line in the graph that goes from 0 towards 2, another line from 0 to 3, and a third line from 0 to 1.

For the second row: node 1 is connected to 0 and 2. i.e there is a line in the graph that goes from 1 to 0 and another line that goes from 1 to 2.

For the third row: node 3 is connected to nodes 4 and 0. i.e there is a line in the graph that goes from node 3 to node 4 and another line from 3 to 0.

And finally for the last row: node 4 is only connected to node 3.

You can notice a symmetry in the representation where if there is a line from node 3 to node 4 then you will find this information in two rows; one that starts with number 3 and the other which starts with number 4.

More Clarification: the first column represents the starting point for all lines. For each row, the first element is the starting point of the line in the graph it goes seperately to the rest of the elements in the row.

Now to the AM:
To represent the first row: 0 2 3 1
This means node 0 is connected to 2, 0 is connected to 3, 0 is connected to 1. So in AM the first row would represent the lines in the graph that starts with 0 and goes to the other nodes ( 0 to 4 ) so there is no line from 0 to 0 and from 0 to 4 so I fill the first and last entries with 0's and the rest with ones as follows: 0 1 1 1 0

I hope this is useful.

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Qusai A

Date: 12 Jun, 2010 22:32:04

Message: 14 of 24

"us " <us@neurol.unizh.ch> wrote in message <hv08ud$lve$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv0861$5kc$1@fred.mathworks.com>...
> > "us " <us@neurol.unizh.ch> wrote in message <hv07ot$adu$1@fred.mathworks.com>...
> > >
> > >
> > > yes, that's why i said: ...and it does reproduce the suggested solution...
> > > however, again: is this the correct adjacency mat given the OP's data(?)...
> > >
> > > just a thought...
> > > us
> >
> > It's surely "undirected graph" with knots # 0, 4 ordered in 1st - 5th position. I was not in doubt five minutes ago.
> >
> > Bruno
>
> good...
> i thought along this line...
>
> al=[
> 0 2 3 1
> 1 0 2 NaN
> 2 0 1 2
> 3 4 0 NaN
> 4 3 NaN NaN
> ];
> al=reshape(al.',[],1);
> al=al(~isnan(al))+1; % <- offset for node #0
> am=accumarray([al(1:end-1),al(2:end)],1)
> %{
> % am =
> 0 1 2 0 1
> 1 1 1 0 0
> 1 0 1 2 0
> 0 1 0 0 1
> 1 0 0 1 0
> %}
>
> but, most likely, i'm missing something...
> us

Thanks all for your input; I beleive the code given by Bruno worked well for me. I tried it to my 64-node AL and worked well. It is highly appreciated :)

I = repmat(AL(:,1)+1,1,size(AL,2)-1);
J = AL(:,2:end)+1;
b = ~isnan(J);
AM = accumarray([I(b) J(b)],1)>0

Subject: Converting an Adjacensy List to Adjacency Matrix

From: us

Date: 12 Jun, 2010 23:27:05

Message: 15 of 24

"Qusai A"
> Thanks all for your input; I beleive the code given by Bruno worked well for me. I tried it to my 64-node AL and worked well. It is highly appreciated :)
>
> I = repmat(AL(:,1)+1,1,size(AL,2)-1);
> J = AL(:,2:end)+1;
> b = ~isnan(J);
> AM = accumarray([I(b) J(b)],1)>0

yes, and again: this is not really an ...adjacency matrix... problem...
and the fact that bruno uses ACCUMARRAY does not change this fact...
rather, the problem is simply setting values in a mat according to a list of rows/cols (subscripts)...
therefore,

one of the many other solutions
- here we use conversion from subscripts to linear indices...

% the data
     al=[
          0 2 3 1
          1 0 2 NaN
          2 0 1 2
          3 4 0 NaN
          4 3 NaN NaN
     ];
% the engine
% - simplified assumptions
     al=al+1;
     alm=max(al(:));
     ixl=bsxfun(@(x,y) sub2ind([alm,alm],x,y),al(:,2:end),al(:,1));
     r=zeros(alm);
     r(ixl(~isnan(ixl)))=1
% the result;
     disp(r);
%{
     0 1 1 1 0
     1 0 1 0 0
     1 1 1 0 0
     1 0 0 0 1
     0 0 0 1 0
%}

us

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 15 Jun, 2010 20:21:06

Message: 16 of 24

"us " <us@neurol.unizh.ch> wrote in message <hv1549$a5a$1@fred.mathworks.com>...
> "Qusai A"
> > Thanks all for your input; I beleive the code given by Bruno worked well for me. I tried it to my 64-node AL and worked well. It is highly appreciated :)
> >
> > I = repmat(AL(:,1)+1,1,size(AL,2)-1);
> > J = AL(:,2:end)+1;
> > b = ~isnan(J);
> > AM = accumarray([I(b) J(b)],1)>0
>
> yes, and again: this is not really an ...adjacency matrix... problem...
> and the fact that bruno uses ACCUMARRAY does not change this fact...
> rather, the problem is simply setting values in a mat according to a list of rows/cols (subscripts)...
> therefore,
>
> one of the many other solutions
> - here we use conversion from subscripts to linear indices...
>
> % the data
> al=[
> 0 2 3 1
> 1 0 2 NaN
> 2 0 1 2
> 3 4 0 NaN
> 4 3 NaN NaN
> ];
> % the engine
> % - simplified assumptions
> al=al+1;
> alm=max(al(:));
> ixl=bsxfun(@(x,y) sub2ind([alm,alm],x,y),al(:,2:end),al(:,1));
> r=zeros(alm);
> r(ixl(~isnan(ixl)))=1
> % the result;
> disp(r);
> %{
> 0 1 1 1 0
> 1 0 1 0 0
> 1 1 1 0 0
> 1 0 0 0 1
> 0 0 0 1 0
> %}
>
> us

Hi all,

I am trying to do something similar here:
I have a group of undirected graphs each consists of 64 nodes ( 0-63). Each graph is in the form of adjacency list and comes in *.txt format. I want to find how many times each possible turn is repeated in all possible short paths. For example in the below adjacency list the shortest path from node 0 to 63 is 0 60 32 11 63 so I want to know how many times the turns (0 60 32), (60 32 11), and (32 11 63) are repeated in all different shortest paths of the graph, and so one for all involved turns.

I also have another issue and that is when I import the txt file to the matlab environment the imported matrix will consist of a number of columns equivalent to the number of elements in the first row!!! the matlab makes a shift for all other rows consisting of more elements; like the row starting with node 11 below.

This is one of the graphs that I have in txt format:
  0 57 7 6 55 60 53
  1 35 54 49 50 8
  2 35 54 8 12 13
  3 24 25 5 9
  4 32 31 30
  5 24 3 23 26
  6 35 54 0 20 61
  7 0 33
  8 39 2 27 1 22
  9 24 3 30 31
 10 36 13 18
 11 63 21 47 28 32 29 27
 12 39 2 49 58 60
 13 39 2 27 10 17
 14 40 38 30 62 48
 15 29 37 48
 16 48 37 29
 17 36 13 34
 18 41 10 62
 19 33 20
 20 19 57 6 51 48 37
 21 11 46
 22 40 38 30 8 29
 23 43 5 42 45
 24 43 9 5 3
 25 3 32 36
 26 43 5 53 55
 27 40 38 11 13 8
 28 11 46 33
 29 16 15 11 22 58
 30 4 9 22 14
 31 4 9 51 52
 32 4 25 11 60
 33 19 7 28 55 58 42
 34 41 17 50
 35 6 2 1
 36 46 25 17 10
 37 16 15 20 50 41
 38 14 22 27
 39 13 12 8
 40 27 22 14
 41 37 34 18
 42 46 23 33 45
 43 46 26 24 23
 44 52 51 45
 45 44 23 52 42
 46 21 47 28 43 42 36
 47 46 11
 48 16 15 20 14 60
 49 59 12 56 1 62
 50 37 34 1
 51 44 31 56 20
 52 44 31 53 45
 53 61 26 0 52
 54 1 2 6
 55 61 26 0 33
 56 61 51 58 49
 57 0 20
 58 59 12 56 29 33
 59 60 58 49
 60 59 12 32 48 0
 61 6 56 55 53
 62 49 18 14
 63 11
 so for the first row, node 0 is connected seperately to the rest of the nodes 57 7 6 55 60 53.

I hope that you can give me some help in this.

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 15 Jun, 2010 21:03:06

Message: 17 of 24

"Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8nbh$9vf$1@fred.mathworks.com>...

>
> Hi all,
>
> I am trying to do something similar here:
> I have a group of undirected graphs each consists of 64 nodes ( 0-63). Each graph is in the form of adjacency list and comes in *.txt format. I want to find how many times each possible turn is repeated in all possible short paths. For example in the below adjacency list the shortest path from node 0 to 63 is 0 60 32 11 63 so I want to know how many times the turns (0 60 32), (60 32 11), and (32 11 63) are repeated in all different shortest paths of the graph, and so one for all involved turns.

What are "turns"? Are they all consecutive triplets of the paths?

In this case, just build the list of all triplets in an (n x 3) matrix, then count them with UNIQUE command and 'ROWS' option.

Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 15 Jun, 2010 22:37:04

Message: 18 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv8pqa$fk9$1@fred.mathworks.com>...
> "Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8nbh$9vf$1@fred.mathworks.com>...
>
> >
> > Hi all,
> >
> > I am trying to do something similar here:
> > I have a group of undirected graphs each consists of 64 nodes ( 0-63). Each graph is in the form of adjacency list and comes in *.txt format. I want to find how many times each possible turn is repeated in all possible short paths. For example in the below adjacency list the shortest path from node 0 to 63 is 0 60 32 11 63 so I want to know how many times the turns (0 60 32), (60 32 11), and (32 11 63) are repeated in all different shortest paths of the graph, and so one for all involved turns.
>
> What are "turns"? Are they all consecutive triplets of the paths?
>
> In this case, just build the list of all triplets in an (n x 3) matrix, then count them with UNIQUE command and 'ROWS' option.
>
> Bruno

Hi Bruno,

Yes; turns are all consecutive triplets of the paths.
but the thing is that I have problem building the matrix of these triplets!!

Do you have any particular idea please?

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Bruno Luong

Date: 16 Jun, 2010 05:37:03

Message: 19 of 24

"Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8vag$spi$1@fred.mathworks.com>...

> Hi Bruno,
>
> Yes; turns are all consecutive triplets of the paths.
> but the thing is that I have problem building the matrix of these triplets!!

One way to build the triplets is

% Data
A = ceil(10*rand(4,5))

% Engine
[S R C] = ndgrid(0:2,1:size(A,1),1:size(A,2)-2);
I = R+(C+S-1)*size(A,1);
triplet =reshape(A(I),3,[])'

You could optimize the above code with BSXFUN instead of using NDGRID and arithmetics for linear indices.

Bruno

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 16 Jun, 2010 16:20:21

Message: 20 of 24

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv9ntv$gf6$1@fred.mathworks.com>...
> "Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8vag$spi$1@fred.mathworks.com>...
>
> > Hi Bruno,
> >
> > Yes; turns are all consecutive triplets of the paths.
> > but the thing is that I have problem building the matrix of these triplets!!
>
> One way to build the triplets is
>
> % Data
> A = ceil(10*rand(4,5))
>
> % Engine
> [S R C] = ndgrid(0:2,1:size(A,1),1:size(A,2)-2);
> I = R+(C+S-1)*size(A,1);
> triplet =reshape(A(I),3,[])'
>
> You could optimize the above code with BSXFUN instead of using NDGRID and arithmetics for linear indices.
>
> Bruno

Dear Bruno,
this was brilliant !!!

thanks a million, I am gonna try my whole program now....

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Qusai A

Date: 16 Jun, 2010 17:56:19

Message: 21 of 24

"Jack " <jack_sama_1981@yahoo.com> wrote in message <hvatk5$gm8$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv9ntv$gf6$1@fred.mathworks.com>...
> > "Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8vag$spi$1@fred.mathworks.com>...
> >
> > > Hi Bruno,
> > >
> > > Yes; turns are all consecutive triplets of the paths.
> > > but the thing is that I have problem building the matrix of these triplets!!
> >
> > One way to build the triplets is
> >
> > % Data
> > A = ceil(10*rand(4,5))
> >
> > % Engine
> > [S R C] = ndgrid(0:2,1:size(A,1),1:size(A,2)-2);
> > I = R+(C+S-1)*size(A,1);
> > triplet =reshape(A(I),3,[])'
> >
> > You could optimize the above code with BSXFUN instead of using NDGRID and arithmetics for linear indices.
> >
> > Bruno
>
> Dear Bruno,
> this was brilliant !!!
>
> thanks a million, I am gonna try my whole program now....

hi,

what matlab function did you use to find the set of "turns"?
would you mind sending me the data you have in txt format.
thanks

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 16 Jun, 2010 18:47:04

Message: 22 of 24

"Qusai A" <gqusai@hotmail.com> wrote in message <hvb383$djb$1@fred.mathworks.com>...
> "Jack " <jack_sama_1981@yahoo.com> wrote in message <hvatk5$gm8$1@fred.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv9ntv$gf6$1@fred.mathworks.com>...
> > > "Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8vag$spi$1@fred.mathworks.com>...
> > >
> > > > Hi Bruno,
> > > >
> > > > Yes; turns are all consecutive triplets of the paths.
> > > > but the thing is that I have problem building the matrix of these triplets!!
> > >
> > > One way to build the triplets is
> > >
> > > % Data
> > > A = ceil(10*rand(4,5))
> > >
> > > % Engine
> > > [S R C] = ndgrid(0:2,1:size(A,1),1:size(A,2)-2);
> > > I = R+(C+S-1)*size(A,1);
> > > triplet =reshape(A(I),3,[])'
> > >
> > > You could optimize the above code with BSXFUN instead of using NDGRID and arithmetics for linear indices.
> > >
> > > Bruno
> >
> > Dear Bruno,
> > this was brilliant !!!
> >
> > thanks a million, I am gonna try my whole program now....
>
> hi,
>
> what matlab function did you use to find the set of "turns"?
> would you mind sending me the data you have in txt format.
> thanks

We should ask Bruno here ;
I am using:
[dist, path, pred] = graphshortestpath(UG, S)
Which determines the single-source shortest paths from node S to all other nodes in the graph represented by sparse matrix UG. You have to fill in S all nodes from 1 to 64.
I am not getting correct answers to use with Bruno's code!! any help here Bruno?
I want to to put the set of all shortest path for the previous data in a single matrix.
thanks

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 17 Jun, 2010 17:59:06

Message: 23 of 24

"Jack " <jack_sama_1981@yahoo.com> wrote in message <hvb678$n8m$1@fred.mathworks.com>...
> "Qusai A" <gqusai@hotmail.com> wrote in message <hvb383$djb$1@fred.mathworks.com>...
> > "Jack " <jack_sama_1981@yahoo.com> wrote in message <hvatk5$gm8$1@fred.mathworks.com>...
> > > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hv9ntv$gf6$1@fred.mathworks.com>...
> > > > "Jack " <jack_sama_1981@yahoo.com> wrote in message <hv8vag$spi$1@fred.mathworks.com>...
> > > >
> > > > > Hi Bruno,
> > > > >
> > > > > Yes; turns are all consecutive triplets of the paths.
> > > > > but the thing is that I have problem building the matrix of these triplets!!
> > > >
> > > > One way to build the triplets is
> > > >
> > > > % Data
> > > > A = ceil(10*rand(4,5))
> > > >
> > > > % Engine
> > > > [S R C] = ndgrid(0:2,1:size(A,1),1:size(A,2)-2);
> > > > I = R+(C+S-1)*size(A,1);
> > > > triplet =reshape(A(I),3,[])'
> > > >
> > > > You could optimize the above code with BSXFUN instead of using NDGRID and arithmetics for linear indices.
> > > >
> > > > Bruno
> > >
> > > Dear Bruno,
> > > this was brilliant !!!
> > >
> > > thanks a million, I am gonna try my whole program now....
> >
> > hi,
> >
> > what matlab function did you use to find the set of "turns"?
> > would you mind sending me the data you have in txt format.
> > thanks
>
> We should ask Bruno here ;
> I am using:
> [dist, path, pred] = graphshortestpath(UG, S)
> Which determines the single-source shortest paths from node S to all other nodes in the graph represented by sparse matrix UG. You have to fill in S all nodes from 1 to 64.
> I am not getting correct answers to use with Bruno's code!! any help here Bruno?
> I want to to put the set of all shortest path for the previous data in a single matrix.
> thanks

Any comments or help here guys :) I would really appreciate it.
I have the following function which can find me the shortest path between all combination 64 nodes, but i do not want to repeat any two nodes beacuse it is undirected graph. So the path from node 1 to 64 is the same as from 64 to 1. So a code like:
for i=1:64
       for j=1:64
          [dist,path,pred] = graphshortestpath(UG,i,j,'directed',false);
          path
       end
   end
will duplicate the shortest paths.
Also I want to store all these paths in a single array !!! how can i do this?

thanks

Subject: Converting an Adjacensy List to Adjacency Matrix

From: Jack

Date: 17 Jun, 2010 18:41:20

Message: 24 of 24


> Any comments or help here guys :) I would really appreciate it.
> I have the following function which can find me the shortest path between all combination 64 nodes, but i do not want to repeat any two nodes beacuse it is undirected graph. So the path from node 1 to 64 is the same as from 64 to 1. So a code like:
> for i=1:64
> for j=1:64
> [dist,path,pred] = graphshortestpath(UG,i,j,'directed',false);
> path
> end
> end
> will duplicate the shortest paths.
> Also I want to store all these paths in a single array !!! how can i do this?
>
> thanks

One more issue here; the function graphshortestpath gives only one shortest path while there may be many. For example in the data I gave before:

[dist,path,pred] = graphshortestpath(UG,1,3,'directed',false);
 path
path = 1 7 55 3

and

[dist,path,pred] = graphshortestpath(UG,3,1,'directed',false);
path
path = 3 13 61 1

both are correct !!! I'm stuck here

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