Asked by Berk
on 28 Jan 2011

I am wondering whether there is a MATLAB package available to draw graphs (or networks) in a structured way. I would like the nodes and the links have a regular structure. For example, the link between the nodes can only be horizontal, vertical and diagonal, and the nodes can only be located at the corners of a rectangular structure.

I was looking at the graph packages, but unfortunately they seem to be producing the graphs in either allocating the nodes/links in the way that does not fit my purpose or uses a GUI and lets the user place the nodes/links.

Answer by Derek O'Connor
on 30 Jan 2011

Berk,

Graph layout is a very difficult problem and has been studied for many years. AT&T has a department or section dedicated to just that problem.

You can save yourself a lot of tedious programming by using AT&T's GraphViz software which is available here: http://www.graphviz.org/

This site is not the best organized, but go to the download section and choose one of the Executable Packages from AT&T (Windows for me graphviz-2.26.3.msi). Install this and start fiddling around with it, using GVedit by loading a graph file into it.

The GraphViz package and others use a very simple text format for representing a graph and is stored as e.g., Graph10.dot. A small example for a directed graph is shown in the Matlab function below.

In GVedit under the GraphViz menu is Run and Settings. Settings offers 5 or 6 layout programs: neato, dot, twopi, etc. Choose one of them and then RUN. This will produce a picture of the graph which can be saved, but only in bitmap form.

Go back to settings and choose Output Filename, and Type (gif, ps, etc). Now RUN again and the output is saved to a .ps (for me) file which has a proper bounding box and can be used as is in LaTeX.

Here are examples of the the output from the Matlab function GrVizp.m shown below.

http://www.scribd.com/doc/47228910/RPGLab-A-Matlab-package-for-Random-Permutation-Generation

See pages 7,8, and 9.

So you have a choice: (1) Write a Matlab function to lay out and print your graph G, or (2) write a Matlab function that generates a graph.dot text file for processing by one of GraphViz's layout programs.

Good luck,

Derek O'Connor

MATLAB code function GrStrDot = GrVizp(p); % Produce nice Postscript picture of a random permutation p. % USE: >> n=30; p = randperm(n); GrStrDot = GrVizp(p); % % WARNING: Do not use for n > 100, 200? % % 1. Determine the cycle structure of a permutation p % 2. Generate a <graph>.dot file for GraphViz/neato % 3. View the output in GhostView % % p: is a permutation of the integers (1,2,...,n). % ncyc : number of cycles found in p. % S(k) : is where in p(1..n) the kth cycle starts. % L(k) : is length of kth cycle in p. % % Note : if p(k) == k then L(k) = 1. % Hence the identity permutation has n cycles of length 1. % % Complexity : O(n + ncyc) ~ O(n + Hn) steps. % % Matlab version of a Pascal function written in mid 1980s. % Derek O'Connor 2nd Aug 2009, 20 Jan 2011. derekroconnor@eircom.net % n = numel(p); m = ceil(16*log(n)); % Max expected number of cycles. L = zeros(m,1); % Saves much space for large n. S = zeros(m,1); % 16 is a safety factor. visited = p<0; % Logical array visited(1:n) = false % which marks all p(k) not visited. % % ------------------- GraphViz Output ---------------------------- % Start of the construction of a <graph>.dot which will be the input for % GraphViz software below. Here is a <graph>.dot file example: % % digraph{node[<options>] % 1->6->1; % 2->4->8->10->7->9->2; % 3->3; % 5->5; % } % % -------- Start of <graph>.dot construction. -------- % GrStrDot = 'digraph{node [shape=circle,style=bold];' ; % ncyc = 0; for k = 1:n if ~visited(k) % k not visited, start of new cycle ncyc = ncyc+1; S(ncyc) = k; next = k; edge = '->'; arcstr = ''; while ~visited(next) % Traverse the current cycle k. arcstr = strcat(arcstr, edge, num2str(next)); L(ncyc) = L(ncyc)+1; visited(next) = true; next = p(next); end; arcstr = strcat(arcstr, edge, num2str(next)); arcstr = strcat(arcstr(3:end),';'); GrStrDot = strvcat(GrStrDot, arcstr); end; end; GrStrDot = strvcat(GrStrDot,'}'); % % ------ End of <graph>.dot construction. ------- % % AT&T's GraphViz software produces well laid out graphs which we use % below. % % ---- Write the graph GrStrDot to <graph>.dot text file % [nrows,ncols]=size(GrStrDot); fid = fopen('GrVizDX.dot', 'w'); for k = 1:nrows, fprintf(fid, '%s\n', GrStrDot(k,:)); end; fclose(fid); % % ---- Process the <graph>.dot text file with neato.exe --> <graph>.ps % ---- and display <graph>.ps in GhostView % !D:\Drawing\GraphViz2.36.3\bin\neato.exe -Tps GrVizDX.dot -o GrVizDX.ps !D:\GhostSandV\gsview\gsview64.exe GrVizDX.ps % return % GrVizp

Berk
on 31 Jan 2011

Dear Derek,

Thank you very much.

I've noticed Graphviz before, but hadn't thought of your approach to generate the graphs via Graphviz. And after thinking a while on the first option I realized the issues lying behind the problem. So, I think your way (2) seems to be more time saving.

Derek O'Connor
on 1 Feb 2011

Let us know how you progress and if you write nice Matlab programs that use GraphViz; My example above is fairly crude.

Derek.

Answer by Paulo Silva
on 30 Jan 2011

a=[0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0];

%a=randi([0 1],4,4) %tests with random values

hold on drawlines=1 %1 to connect points where a equals 1 markpoints=1 %1 to mark points where a equals 1 drawvertical=1 %1 only connect vertical points drawdiagonal=1 %1 only connect diagonal points drawonlycorner=1 %1 only connect points at corners drawhorizontal=1 %1 only connect horizontal points

if (markpoints==1) [r,c]=find(a~=0); y=numel(a(:,1))-r+1;x=c; plot(x,y,'o') end

if (drawhorizontal==1) for aa=1:numel(a(:,1)) c=find(a(aa,:)~=0); y=numel(a(:,1))-aa+1; if (numel(c)>1) for d=1:numel(c)-1 corner=0; if ((y==1) | (y==numel(a(:,1))) | (c(d)==1) | (c(d)==numel(a(1,:)))) corner=1; end

if ((y==1) | (y==numel(a(:,1))) | (c(d+1)==1) | (c(d+1)==numel(a(1,:)))) corner=1; end if (2>sqrt((c(d+1)-c(d))^2)) if ((corner==1) & (drawonlycorner==1)) line([c(d) c(d+1)],[y y]) elseif (drawonlycorner==0) line([c(d) c(d+1)],[y y]) end end

end end end end

for r=1:1:numel(a(:,1))-1 l=find(a(r,:)==1); u=find(a(r+1,:)==1); if (isempty(u) | isempty(l)) continue end for b=1:numel(l) for c=1:numel(u) y=numel(a(:,1))-r+1;x=l(b);x1=u(c); if (drawlines==1) vertical=0;diagonal=0; if (x==x1) vertical=1; else diagonal=1; end corner=0; if ((y==1) | (y==numel(a(:,1))) | (x==1) | (x==numel(a(1,:)))) corner=1; end if ((y==1) | (y==numel(a(:,1))) | (x1==1) | (x1==numel(a(1,:)))) corner=1; end if (((y-1)==1) | ((y-1)==numel(a(:,1))) | (x1==1) | (x1==numel(a(1,:)))) corner=1; end

if (2>sqrt((-1)^2+(x1-x)^2)) if ((corner==1) & (drawonlycorner==1)) if ((drawvertical==1) & (vertical==1)) line([x x1],[y y-1]) end if ((drawdiagonal==1) & (diagonal==1)) line([x x1],[y y-1]) end elseif (drawonlycorner==0) if ((drawvertical==1) & (vertical==1)) line([x x1],[y y-1]) end if ((drawdiagonal==1) & (diagonal==1)) line([x x1],[y y-1]) end

end end

end end end l=u; end

axis([0 numel(a(1,:))+1 0 numel(a(:,1))+1])

Berk
on 30 Jan 2011

Thank you very much Paulo,

This is close to what I am looking for, and the difference is related with the rules that apply to the graphs.

That is, the graph that I want to create is based on these rules:

1. There are three kind of edges (horizontal, diagonal and vertical) and their length is 1. For example in the graph on the right there can not be an edge between the node at [r, t-1] and [p, t+2], because the length of that edge will be 3.

2. The edges between the nodes are defined previously and they don't apply to all of the nodes. For example, if there are three nodes at [r, t-1], [r,t] and [p,t], there can be three scenarios each of which is acceptable:

1. Edge between [r, t-1] and [r,t] + edge between [r,t] and [p,t].

2. Edge between [r, t-1] and [r,t] + edge between [r,t-1] and [p,t].

3. Edge between [r, t-1] and [r,t] + edge between [r,t] and [p,t] + edge between [r,t-1] and [p,t].

Paulo Silva
on 30 Jan 2011

Answer by Baran Aydogan
on 18 Feb 2011

Have you checked the MATLAB-GraphViz interface:

MATLAB - GraphViz interface

http://www.mathworks.com/matlabcentral/fileexchange/4518

It can nicely draw adjacency matrices. It gets a bit messy if you have too many nodes though.

Good luck!

-Baran

Opportunities for recent engineering grads.

## 5 Comments

## bym (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/546#comment_760

can you post a sketch of what you want?

## Berk (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/546#comment_816

Please kindly find two graph examples at the link below:

http://yunus.hacettepe.edu.tr/~banbar/exGraphs.jpg

## Walter Roberson (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/546#comment_826

There are a number of nodes in those diagrams that are not placed at the corners of a rectangular structure. Perhaps you meant at the lattice points of a rectangular or square lattice?

## Berk (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/546#comment_834

Yes Walter, I meant lattice points. Sorry, for the misunderstanding.

Do you have any ideas about producing such a graph structure programmatically?

## Paulo Silva (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/546#comment_839

I'm trying to make something like that but I don't know all the rules, can you be more specific, see my code and comment

hold on

drawlines=1; %1 to connect points where a equals 1

markpoints=1; %1 to marks points where a equals 1

if (markpoints==1)

[r,c]=find(a~=0);

y=numel(a(:,1))-r+1;x=c;

plot(x,y,'o')

end

for r=1:1:numel(a(:,1))-1

l=find(a(r,:)==1);

u=find(a(r+1,:)==1);

if (isempty(u) | isempty(l))

continue

end

for b=1:numel(l)

for c=1:numel(u)

y=numel(a(:,1))-r+1;x=l(b);x1=u(c);

if (drawlines==1)

line([x x1],[y y-1])

end

end

end

l=u;

end