As mentioned in the wikipedia page for topological sort, the Kahn's algorithm can be used to find the topological sort of a graph. Following function generates the topological sort order of the nodes of a graph given the adjacency matrix as input parameter.
function topoOrder = topologicalSort(adjMatrix)
% Validate input
if ~issparse(adjMatrix)
error('Input must be a sparse adjacency matrix.');
end
numNodes = size(adjMatrix, 1);
% Initialize in-degree of each node
inDegree = sum(adjMatrix, 1);
% Initialize queue for nodes with zero in-degree
zeroInDegreeQueue = find(inDegree == 0);
topoOrder = zeros(1, numNodes);
index = 1;
while ~isempty(zeroInDegreeQueue)
% Dequeue a node from the queue
currentNode = zeroInDegreeQueue(1);
zeroInDegreeQueue(1) = [];
% Add current node to topological order
topoOrder(index) = currentNode;
index = index + 1;
% For each node that currentNode points to
neighbors = find(adjMatrix(currentNode, :));
for i = neighbors
% Decrease the in-degree of the neighbor
inDegree(i) = inDegree(i) - 1;
% If in-degree becomes zero, add it to the queue
if inDegree(i) == 0
zeroInDegreeQueue = [zeroInDegreeQueue, i];
end
end
end
if index <= numNodes
error('The graph contains a cycle.');
end
topoOrder = topoOrder(1:index-1);
end
Please refer to the following documentation to read more about the issparse function: https://www.mathworks.com/help/matlab/ref/issparse.html
Hope this helps!
