[acfe4f]: inst / toposort.m  Maximize  Restore  History

Download this file

120 lines (108 with data), 3.1 kB

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
function nodelist=toposort(C);
%function nodelist=toposort(C)
%This is a function which carries out a topological sort of a graph. See
%http://en.wikipedia.org/wiki/Topological_sorting.
%Given an input graph C, it outputs an ordered list of nodes
%nodelist which is topologically sorted.
%
% A demo is available by running toposort('demo').
% The input is a vector cell array C which holds the graph. For each
% node i, C{i} is a vector of nodes which node i depends on. A cell may
% be empty.
%
%the input is a linear cell array. each cell should be a vector
%containing the indices it depends on.
%
%The output is a column vector of indices in C, sorted in
%topological order.
%
%Author Paul Dreik 20101008
%License: GPL v2 or later, at your option.
if 0==nargin
error('please supply one input argument');
end
if isequal(C,'demo')
%this is the example on wikipedia as per 20100908
C=cell(11,1);
C{11}=[7 5];
C{8}=[7 3];
C{2}=11;
C{9}=[8 11];
C{10}=[3 11];
end
debug=false;
%go through the list and make sure it is sorted
%L - Empty list that will contain the sorted elements
L=[];
%S - Set of all nodes with no incoming edges
S=[];
for i=1:length(C)
if isempty(C{i})
S(end+1)=i;
else
%while we are at it, make sure the incoming graph is sorted
%properly
p=unique(C{i});
C{i}=p;
%check that the indices are in a valid range 1
%to length(C). This check checks for nan as well.
if ~all(p>=1 & p<=length(C))
error('parent list for node %d contains nodes outside valid range.',i);
end
end
end
if debug
disp(S)
end
%S is sorted from lowest node id to highest. This way nodes with
%low indices will be output prior to higher indices.
%while S is non-empty do
while ~isempty(S)
% remove a node n from S
n=S(1);
S=S(2:end);
if debug
printf('removing node %d from S. S is now\n',n);
disp(S);
end
% insert n into L
L(end+1)=n;
if debug
printf('inserting node %d into L. L is now\n',n);
disp(L);
end
% for each node m with an edge e from n to m do
% remove edge e from the graph
for i=1:length(C)
m=i;
children=C{m};
if any(children==n)
children(find(children==n))=[];
C{m}=children;
if debug
printf('removing link %d to %d\n',n,m);
disp(C);
end
% if m has no other incoming edges then
% insert m into S
if isempty(C{m})
S(end+1)=m;
S=sort(S);
if debug
printf('node %d now has no incoming edges. S is now\n',m);
disp(S);
end
end
end
end
end
%if graph has edges then
% output error message (graph has at least one cycle)
for i=1:length(C)
if ~isempty(C{i})
error('the graph has at least one cycle');
end
end
%else
% output message (proposed topologically sorted order: L)
nodelist=L(:);