Method topological_ordering

numpy_ml/utils/graphs.py:200–259

Returns a (non-unique) topological sort / linearization of the nodes IFF the graph is acyclic, otherwise returns None. Notes ----- A topological sort is an ordering on the nodes in `G` such that for every directed edge :math:`u \\rightarrow v` in the

(self)

        return DiGraph(self.vertices, [e.reverse() for e in self.edges])

    def topological_ordering(self):
        """
        Returns a (non-unique) topological sort / linearization of the nodes
        IFF the graph is acyclic, otherwise returns None.

        Notes
        -----
        A topological sort is an ordering on the nodes in `G` such that for every
        directed edge :math:`u \\rightarrow v` in the graph, `u` appears before
        `v` in the ordering.  The topological ordering is produced by ordering
        the nodes in `G` by their DFS "last visit time," from greatest to
        smallest.

        This implementation follows a recursive, DFS-based approach [1]_ which
        may break if the graph is very large. For an iterative version, see
        Khan's algorithm [2]_ .

        References
        ----------
        .. [1] Tarjan, R. (1976), Edge-disjoint spanning trees and depth-first
           search, *Acta Informatica, 6 (2)*: 171–185.
        .. [2] Kahn, A. (1962), Topological sorting of large networks,
           *Communications of the ACM, 5 (11)*: 558–562.

        Returns
        -------
        ordering : list or None
            A topoligical ordering of the vertex indices if the graph is a DAG,
            otherwise None.
        """
        ordering = []
        visited = set()

        def dfs(v_i, path=None):
            """A simple DFS helper routine"""
            path = set([v_i]) if path is None else path
            for nbr_i in self.get_neighbors(v_i):
                if nbr_i in path:
                    return True  # cycle detected!
                elif nbr_i not in visited:
                    visited.add(nbr_i)
                    path.add(nbr_i)
                    is_cyclic = dfs(nbr_i, path)
                    if is_cyclic:
                        return True

            # insert to the beginning of the ordering
            ordering.insert(0, v_i)
            path -= set([v_i])
            return False

        for s_i in self.indices:
            if s_i not in visited:
                visited.add(s_i)
                is_cyclic = dfs(s_i)

                if is_cyclic:
                    return None