Description of sgf

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:

• add add --- add edge(s) to the graph
• edges edges(g) --- list the edges in g as a 2-column matrix
• embed embed --- create an embedding for a graph
• full full(g) --- convert internal storage for g to full
• getxy getxy(g) --- give g's embedding (or [] if g doesn't have one)
• hasxy hasxy(g) --- determine if an embedding has been created for g
• ne ne(g) --- number of edges in g or ne(g,h) --- check for inequality
• nv nv(g) --- number of vertices in g
• resize resize(g,n) --- change the number of vertices in g to n
• size size(g) --- returns [nv,ne] for the graph
• sparse sparse(g) --- convert internal storage for g to sparse

This function is called by:

SUBFUNCTIONS

• function A = sgf_make(g)
• function ok = sgf_check(M)

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