Home > matgraph > @graph > sgf.m

sgf

PURPOSE ^

sgf --- simple graph format: a 2-column matrix representation

SYNOPSIS ^

function A = sgf(g,M)

DESCRIPTION ^

 sgf --- simple graph format: a 2-column matrix representation
 A = sgf(g) --- make the simple graph format matrix of g
 sgf(g,M)   --- overwrite g with the graph specified in M

 The simple graph format is a 2-column matrix representation of a graph.
 This format optionally includes embedding information.
 If A is the SGF of a graph, the rows of A are as follows:

 * First row is [n m] where n is the number of vertices and m is the number
   of edges.
 * Rows 2 through m+1 specify the edges of the graph.
 * Optionally, rows (m+1)+1 through (m+1)+n give the x,y-coordinates of
   the vertices.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function A = sgf(g,M)
0002 % sgf --- simple graph format: a 2-column matrix representation
0003 % A = sgf(g) --- make the simple graph format matrix of g
0004 % sgf(g,M)   --- overwrite g with the graph specified in M
0005 %
0006 % The simple graph format is a 2-column matrix representation of a graph.
0007 % This format optionally includes embedding information.
0008 % If A is the SGF of a graph, the rows of A are as follows:
0009 %
0010 % * First row is [n m] where n is the number of vertices and m is the number
0011 %   of edges.
0012 % * Rows 2 through m+1 specify the edges of the graph.
0013 % * Optionally, rows (m+1)+1 through (m+1)+n give the x,y-coordinates of
0014 %   the vertices.
0015 
0016 if nargin==1
0017     A = sgf_make(g);
0018     return
0019 end
0020     
0021 if ~sgf_check(M)
0022     error('Matrix is not a properly formed sgf matrix');
0023 end
0024  
0025 
0026 n = M(1,1);
0027 m = M(1,2);
0028 
0029 resize(g,0);
0030 
0031 if n>set_large
0032     sparse(g);
0033 else
0034     full(g);
0035 end
0036 
0037 resize(g,n);
0038 
0039 edges = M(2:m+1,:);
0040 add(g,edges);
0041 
0042 % see if there's an embedding
0043 [r,c] = size(M);
0044 if (r>m+1)
0045     xy = M(m+2:end,:);
0046     embed(g,xy);
0047 end
0048 
0049 
0050 
0051 function A = sgf_make(g)
0052 % helper function to convert a graph to a sgf matrix
0053 n = nv(g);
0054 m = ne(g);
0055 if hasxy(g)
0056     A = zeros(n+m+1,2);
0057 else
0058     A = zeros(m+1,2);
0059 end
0060 
0061 A(1,:) = [n,m];
0062 A(2:m+1,:) = edges(g);
0063 if hasxy(g)
0064     A(m+2:end,:) = getxy(g);
0065 end
0066 
0067 function ok = sgf_check(M)
0068 % check a matrix to be sure it's a valid sgf
0069 
0070 ok = false;
0071 
0072 [r,c] = size(M);
0073 if (c ~= 2) | (r==0)
0074     return
0075 end
0076 
0077 row1 = M(1,:);
0078 n = row1(1);
0079 m = row1(2);
0080 
0081 if (n < 0) | (m < 0)
0082     return
0083 end
0084 
0085 if ~((r==m+1) | (r==m+n+1))
0086     return
0087 end
0088 
0089 edges = M(2:m+1,:);
0090 % make sure they are all integers
0091 if any(any(edges ~= round(edges)))
0092     return
0093 end
0094 % make sure they are all in {1,2,...,n}
0095 if any(any(edges < 1)) | any(any(edges>n))
0096     return
0097 end
0098 % make sure there are no loops
0099 if any(edges(:,1)==edges(:,2))
0100     return
0101 end
0102 
0103 % all tests passed
0104     
0105 ok = true;

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003