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:
Forming an adjacency matrix

Subject: Forming an adjacency matrix

From: H

Date: 4 Jan, 2010 12:59:05

Message: 1 of 9

I'm trying to form an adjacency matrix of a three-dimensional evenly spaced network(graph) where one can move to every neighboring node except the ones directly above, beneath and behind the node in question. I.e. movement in forward,sideways and diagonally up and down is accepted. My graph would be quite large (about 100,000 nodes representing a space of 100x100x10) so what I really need some kind of algorithm to build the adjacency matrix. Is there any ready solutions for this problem?

I can of course consider a different approach if there is any.

My ultimate goal is to solve a routing problem with some weight matrix, but I cant get to it without a representation of the space.

I searched the forum but I couldn't find an answer so any help would be greatly appreciated.

Subject: Forming an adjacency matrix

From: us

Date: 4 Jan, 2010 13:59:05

Message: 2 of 9

"H " <mesta2000@hotmail.com> wrote in message <hhsomp$1nj$1@fred.mathworks.com>...
> I'm trying to form an adjacency matrix of a three-dimensional evenly spaced network(graph) where one can move to every neighboring node except the ones directly above, beneath and behind the node in question. I.e. movement in forward,sideways and diagonally up and down is accepted. My graph would be quite large (about 100,000 nodes representing a space of 100x100x10) so what I really need some kind of algorithm to build the adjacency matrix. Is there any ready solutions for this problem?
>
> I can of course consider a different approach if there is any.
>
> My ultimate goal is to solve a routing problem with some weight matrix, but I cant get to it without a representation of the space.
>
> I searched the forum but I couldn't find an answer so any help would be greatly appreciated.

one of the very preliminary possible solutions is outlined below

% the data
% - note: X/Y/Z are vertices...
     x=[1;2;3;5;1;2];
     y=[1;1;2;1;1;1];
     z=[1;1;1;2;1;1];
% the engine
     v=[x,y,z];
     [vu,vx,vx]=unique(v,'rows'); % <- enumerate unique vertex indices in VX
     r=accumarray([vx(1:end-1),vx(2:end)],1);
% the result
     disp(v);
     disp(r);
% - on display
     vl=cellfun(@(x) sprintf('%d/%d/%d',x),num2cell(vu,2),'uni',false);
     imagesc(r);
     axis image;
     colormap(jet(1+max(r(:))));
     colorbar;
     nl=numel(vl);
     set(gca,'xtick',1:nl,'xticklabel',vl,'ytick',1:nl,'yticklabel',vl);

us

Subject: Forming an adjacency matrix

From: Steven Lord

Date: 4 Jan, 2010 14:17:24

Message: 3 of 9


"H " <mesta2000@hotmail.com> wrote in message
news:hhsomp$1nj$1@fred.mathworks.com...
> I'm trying to form an adjacency matrix of a three-dimensional evenly
> spaced network(graph) where one can move to every neighboring node except
> the ones directly above, beneath and behind the node in question. I.e.
> movement in forward,sideways and diagonally up and down is accepted. My
> graph would be quite large (about 100,000 nodes representing a space of
> 100x100x10) so what I really need some kind of algorithm to build the
> adjacency matrix. Is there any ready solutions for this problem?

If I interpret your description correctly, this adjacency matrix would be a
100000-by-100000 full matrix (most of the entries are nonzero, so storing it
as a sparse matrix won't help) requiring a block of about 74 GB of
contiguous memory, right? Unless your computer is a large supercomputer, it
doesn't have that much memory, and even if it did you'd need another block
of the same size to actually do anything to the adjacency matrix.

> I can of course consider a different approach if there is any.
>
> My ultimate goal is to solve a routing problem with some weight matrix,
> but I cant get to it without a representation of the space.

Does the algorithm you're using require the whole adjacency matrix or can it
work with a function that accepts a start node and and end node and returns
true if the transition is allowed?

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

Subject: Forming an adjacency matrix

From: H

Date: 4 Jan, 2010 14:35:19

Message: 4 of 9

"Steven Lord" <slord@mathworks.com> wrote in message <hhst9e$mkk$1@fred.mathworks.com>...
>
> "H " <mesta2000@hotmail.com> wrote in message
> news:hhsomp$1nj$1@fred.mathworks.com...
> > I'm trying to form an adjacency matrix of a three-dimensional evenly
> > spaced network(graph) where one can move to every neighboring node except
> > the ones directly above, beneath and behind the node in question. I.e.
> > movement in forward,sideways and diagonally up and down is accepted. My
> > graph would be quite large (about 100,000 nodes representing a space of
> > 100x100x10) so what I really need some kind of algorithm to build the
> > adjacency matrix. Is there any ready solutions for this problem?
>
> If I interpret your description correctly, this adjacency matrix would be a
> 100000-by-100000 full matrix (most of the entries are nonzero, so storing it
> as a sparse matrix won't help) requiring a block of about 74 GB of
> contiguous memory, right? Unless your computer is a large supercomputer, it
> doesn't have that much memory, and even if it did you'd need another block
> of the same size to actually do anything to the adjacency matrix.
>
> > I can of course consider a different approach if there is any.
> >
> > My ultimate goal is to solve a routing problem with some weight matrix,
> > but I cant get to it without a representation of the space.
>
> Does the algorithm you're using require the whole adjacency matrix or can it
> work with a function that accepts a start node and and end node and returns
> true if the transition is allowed?
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
>

Actually the nodes in the matrix should have 24 arcs each because they are connected only to the neighbor nodes (excluding nodes right above and below) so the adjacency matrix should have only 24 nonzero values on each row/column. Of course the nodes in the edge of the space have less arcs. This would imply that using a sparse matrix structure, it would have appr. 100,000x24 ~2.4M elements.

I've seen at least one study ( http://faculty.nps.edu/mcarlyle/docs/CarlyleRoysetWoodAircraftRouting.pdf ) p. 23-24 which Implies that a network this size is doable. It is also implied that this network is constructed before applying the algorithm.

Subject: Forming an adjacency matrix

From: H

Date: 8 Jan, 2010 13:20:21

Message: 5 of 9

Ok, I managed to do build the adjacency matrix of the network that I was trying to make. I used a sparse-matrix and with the nodes connected to every neighbor node in sideways and forward includin diagonal nodes, the whole 100x200x16 vertex network took only about 56 Megabytes of memory.

If anyone is interested, I can post my rather inelegant solution. In short I produced column of the network as a nxn matrix and copied it the needed number of times...

Subject: Forming an adjacency matrix

From: us

Date: 8 Jan, 2010 13:27:03

Message: 6 of 9

"H " <mesta2000@hotmail.com> wrote in message <hi7bel$dqn$1@fred.mathworks.com>...
> Ok, I managed to do build the adjacency matrix of the network that I was trying to make. I used a sparse-matrix and with the nodes connected to every neighbor node in sideways and forward includin diagonal nodes, the whole 100x200x16 vertex network took only about 56 Megabytes of memory.
>
> If anyone is interested, I can post my rather inelegant solution. In short I produced column of the network as a nxn matrix and copied it the needed number of times...

indeed, it would be great to be able to have a look at the code...

us

Subject: Forming an adjacency matrix

From: Derek O'Connor

Date: 8 Jan, 2010 15:15:04

Message: 7 of 9

"H " <mesta2000@hotmail.com> wrote in message <hhsomp$1nj$1@fred.mathworks.com>...
> I'm trying to form an adjacency matrix of a three-dimensional evenly spaced network(graph) where one can move to every neighboring node except the ones directly above, beneath and behind the node in question. I.e. movement in forward,sideways and diagonally up and down is accepted. My graph would be quite large (about 100,000 nodes representing a space of 100x100x10) so what I really need some kind of algorithm to build the adjacency matrix. Is there any ready solutions for this problem?
>
> I can of course consider a different approach if there is any.
>
> My ultimate goal is to solve a routing problem with some weight matrix, but I cant get to it without a representation of the space.
>
> I searched the forum but I couldn't find an answer so any help would be greatly appreciated.
------------------------------------------------------------

You can store a graph(network,adjacency matrix) which has n nodes
and m arcs in about 2m+n words(boxes). With n = 10^5 and m = 24*10^5,
this gives a total of about 5 M boxes = 40 MB if there are 8 bytes/box.

Alternatively, a simple list of arcs, where each arc is represented by
a triple (i,j,val), requires about 3m boxes.

Here is Richard Varga (Matrix Iterative Analysis, Prentice-Hall, 1962,
pages 1 and 2.) talking about sparse matrices and iterative methods
in 1960:

"As an example of the magnitude of problems that have been
successfully solved on digital computers by cyclic iterative
methods, the Bettis Atomic Power Laboratory of the Westinghouse
Electric Corporation had in daily use in 1960 a two-dimensional
program that could treat as a special case, Laplacian-type matrix
equations of order 20,000."

He adds this footnote:

"This program, called PDQ-4, was specifically written for the
Philco-2000 computer with 32,000 words of core storage. Even more
staggering is Bettis' use of a three-dimensional program,
TNT-1, which treats coupled matrix equations of order 108,000. "


Varga's comments show that large sparse problems were being solved
routinely on small computers (128 KB core) over 50 years ago.
Hence, sparse matrix techniques have been around for a long time,
even though it took linear programmers and Matlab-ers until
the 1980s and 90s to discover this.

Derek O'Connor

Subject: Forming an adjacency matrix

From: H

Date: 11 Jan, 2010 07:52:04

Message: 8 of 9

I started by just writing the adjacency matrix for a smaller (4x4 nodes network). In order to keep track of the geometry, I numbered my nodes as:

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

which now represents a 2-d grid. I quickly realized that the matrix has only diagonals representing the movements. for the first 4 nodes the sideways edges are:

B=
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0

The forward movements are exactly the same. so all movements from nodes 1-4 can be written as [B C] where C represents the edges to nodes 5-8. Of course movement from e.g. 4 to 5 is prohibited so those have to be taken care of. It now looks like:
0 1 0 0 1 1 0 0
1 0 1 0 1 1 1 0
0 1 0 1 0 1 1 1
0 0 1 0 0 0 0 1

Now this can be copied in the following way:
A=
B C 0 0 0 0 0 ...
0 B C 0 0 0 0
0 0 B C 0 0 0
0 0 0 B C 0 0
.
.
.

As long as we come to the last column (there are no edges forward from the nodes 13-16 because the "map" ends. This is it for 2-D. For 3-D the movements to upper and lower layers have to be taken care of as well. Because there are 5 nodes in all the layers where edges go from a node, the "symmetry" is the same. So for the first 4 nodes in the 1st layer the adjacency matrix looks like:
[B C B C [zeros]]
and for the 2nd layer:
[B C B C [zeros] B C B C [zeros]]
the zeros between are determined by the area of the grid.
for the 3rd layer:
[[zeros] B C B C [zeros] B C B C [zeros]]
And so on until the last layer where there are no upward movements.

If I now use find for the adjacency matrix, I get a nice list of the edges. Coupled with a simple loop for the nodes, I can get coordinates for the nodes as well.

I tried this for 100x200x16 network (320000 nodes!) and the whole ordeal took my laptop about 2,5 seconds.

I'm not very good at matlab so my code mos likely is not very efficient:
function A=gen_net(w,d,h)
% w=width
% d=length
% h=hights

N=w*d*h;%number of nodes

%Matrix that represents edges to nodes on the side and forward
B =spdiags(ones(w*d,5),[-1 1 w-1 w w+1],w*d,w*d);
%corners and edges have to be set to zero because movement from other side
%to the other is ofcourse impossible
B(1,w)=0;
for i=1:(d-2)
B(i*w,i*w+1)=0;
B(i*w,(i+1)*w+1)=0;
B(i*w+1,i*w)=0;
B(i*w+1,(i+1)*w)=0;
end
B((d-1)*w,(d-1)*w+1)=0;
B((d-1)*w+1,(d-1)*w)=0;
B((d-1)*w+1,d*w)=0;

%1st layer:
A=[B B sparse(w*d,N-2*w*d)];

%middle layers
for k=2:h-1
A=[A; sparse(w*d,(k-2)*(w*d)) B B B sparse(w*d,N-3*w*d-(k-2)*(w*d))];
end

%last layer
A=[A; sparse(w*d,N-2*w*d) B B];

Subject: Forming an adjacency matrix

From: H

Date: 11 Jan, 2010 08:28:02

Message: 9 of 9

I made typo explaining the middle layers. No there's only edges to lower and the same level... There should be a third set of B C of course.

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