Description of renumber

Home > matgraph > @graph > renumber.m

renumber

PURPOSE

renumber the vertices of a graph

SYNOPSIS

function renumber(g,perm)

DESCRIPTION

 renumber the vertices of a graph
 renumber(g,perm) --- renumber the vertices of a graph accoring to a
 permutation
 renumber(p,part) --- renumber vertices according to a partition.

 perm should be a permutation of 1 through n
 the graph's vertices are permutated so that the old vertex 1 is now
 vertex perm(1), etc.
 Note: perm may be either an array containing the permutation or a
 permutation object. 

 part should be a partition of [n]. We renumber so vertices in the same
 block of the partition are consecutive.

CROSS-REFERENCE INFORMATION

This function calls:

• embed embed --- create an embedding for a graph
• 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
• is_labeled is_labeled(g) --- determine if there are labels on vertices.
• make_logical make_logical(g) --- ensure that the internal storage for g's matrix is a
• nv nv(g) --- number of vertices in g

This function is called by:

• interval_graph interval_graph(g,ilist) --- create an interval graph
• iso [yn,p] = iso(g,h,options) --- is g isomorphic to h?
• random_tree random_tree(t,n) --- overwrite t with a random tree on n vertices

SUBFUNCTIONS

• function list = partition2list(p)

SOURCE CODE

0001 function renumber(g,perm)
0002 % renumber the vertices of a graph
0003 % renumber(g,perm) --- renumber the vertices of a graph accoring to a
0004 % permutation
0005 % renumber(p,part) --- renumber vertices according to a partition.
0006 %
0007 % perm should be a permutation of 1 through n
0008 % the graph's vertices are permutated so that the old vertex 1 is now
0009 % vertex perm(1), etc.
0010 % Note: perm may be either an array containing the permutation or a
0011 % permutation object.
0012 %
0013 % part should be a partition of [n]. We renumber so vertices in the same
0014 % block of the partition are consecutive.
0015 
0016 
0017 global GRAPH_MAGIC
0018 
0019 n = nv(g);
0020 
0021 if isa(perm,'partition')
0022     perm = partition2list(perm);
0023 end
0024 
0025 if ~isa(perm,'permutation')
0026     perm = permutation(perm);
0027 end
0028 
0029 if length(perm) ~= n
0030     error('Length of permutation does not match size of graph')
0031 end
0032 
0033 perm = inv(perm);
0034 q = array(perm);
0035 
0036 GRAPH_MAGIC.graphs{g.idx}.array = ...
0037     GRAPH_MAGIC.graphs{g.idx}.array(q,q);
0038 
0039 make_logical(g);
0040 
0041 if hasxy(g)
0042     xy = getxy(g);
0043     xy = xy(q,:);
0044     embed(g,xy);
0045 end
0046 
0047 if is_labeled(g)
0048     tmp = cell(n,1);
0049     for k=1:n
0050         tmp{k} = GRAPH_MAGIC.graphs{g.idx}.labels{perm(k)};
0051     end
0052     GRAPH_MAGIC.graphs{g.idx}.labels = tmp;
0053 end
0054 
0055 
0056 function list = partition2list(p)
0057 pp = parts(p);
0058 list = [];
0059 for k=1:np(p)
0060     list = [list, pp{k}];
0061 end

---

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