Topological sort

Hi,

I am looking for an implementation of a MATLAB function that performs a topological sort of an directed acyclic graph based on a sparse adjacency matrix ( http://en.wikipedia.org/wiki/Topological_sorting ). I know that this function is available with the Bioinformatics Toolbox ( http://www.mathworks.de/help/toolbox/bioinfo/ref/graphtopoorder.html ), which I don't have, however. Can anyone please help me with a link to a fast implementation (preferably in m-code and not mex-file).

Best regards, Anon

Answer 1

[Jaynik]

Hi @Anon,

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!