Can MATLAB draw graphs or networks with a regular structure?

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.

[bym]

can you post a sketch of what you want?

[Berk]

Please kindly find two graph examples at the link below:

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

[Walter Roberson]

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]

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

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

[Paulo Silva]

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

Answer 1

[Derek O'Connor]

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. [e-mail]
%
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]

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]

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

Derek.

Answer 2

[Paulo Silva]

    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]

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]

I updated the code for the length problem, now about 2. I have no idea how to implement that, the prefered scenario is chosen by the user?

[Berk]

Thank you very much Paulo.

I think I did not state clearly by saying the "regular structure", because it is not really regular.

Anyway, your idea gave me some insight on how to solve the problem. I think the solution lies to draw each edge seperately.

Thanks again.

Answer 3

[Baran Aydogan]

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