public function getSortedNodeList()
    {
        $list = array();

        while ( $leave = array_pop( $this->leaves ) )
        {
            unset( $this->nodes[$leave] );
            $list[] = $leave;

            if ( !isset( $this->edges[$leave] ) )
            {
                continue;
            }

            foreach ( $this->edges[$leave] as $node )
            {
                $count = -1;
                // Count the incoming edges for each node which had an incoming
                // connection from the removed leave.
                foreach ( $this->edges as $src => $dsts )
                {
                    foreach ( $dsts as $nr => $dst )
                    {
                        $count += ( $dst === $node );

                        // Also remove all edges which point to the leave
                        if ( $dst === $leave )
                        {
                            unset( $this->edges[$src][$nr] );
                        }
                    }
                }

                // Add all new leaves to the leave array.
                if ( $count <= 0 )
                {
                    array_push( $this->leaves, $node );
                }
            }

            // Remove all outgoing edges from leave
            unset( $this->edges[$leave] );
        }

        if ( count( $this->edges ) )
        {
            var_dump( $this->edges );
            throw new Exception( 'Cycle found in graph. This should not happen.' );
        }

        return $list;
    }
public function getSortedNodeList()
    {
        $list = array();

        while ( $leave = array_pop( $this->leaves ) )
        {
            unset( $this->nodes[$leave] );
            $list[] = $leave;

            if ( !isset( $this->edges[$leave] ) )
            {
                continue;
            }

            foreach ( $this->edges[$leave] as $node )
            {
                $count = -1;
                // Count the incoming edges for each node which had an incoming
                // connection from the removed leave.
                foreach ( $this->edges as $src => $dsts )
                {
                    foreach ( $dsts as $nr => $dst )
                    {
                        $count += ( $dst === $node );

                        // Also remove all edges which point to the leave
                        if ( $dst === $leave )
                        {
                            unset( $this->edges[$src][$nr] );
                        }
                    }
                }

                // Add all new leaves to the leave array.
                if ( $count <= 0 )
                {
                    array_push( $this->leaves, $node );
                }
            }

            // Remove all outgoing edges from leave
            unset( $this->edges[$leave] );
        }

        if ( count( $this->edges ) )
        {
            var_dump( $this->edges );
            throw new Exception( 'Cycle found in graph. This should not happen.' );
        }

        return $list;
    }
public function getSortedNodeList ( ) { $ list = array ( ) ; while ( $ leave = array_pop ( $ this -> leaves ) ) { unset ( $ this -> nodes [ $ leave ] ) ; $ list [ ] = $ leave ; if ( ! isset ( $ this -> edges [ $ leave ] ) ) { continue ; } foreach ( $ this -> edges [ $ leave ] as $ node ) { $ count = - 1 ; // Count the incoming edges for each node which had an incoming // connection from the removed leave. foreach ( $ this -> edges as $ src => $ dsts ) { foreach ( $ dsts as $ nr => $ dst ) { $ count += ( $ dst === $ node ) ; // Also remove all edges which point to the leave if ( $ dst === $ leave ) { unset ( $ this -> edges [ $ src ] [ $ nr ] ) ; } } } // Add all new leaves to the leave array. if ( $ count <= 0 ) { array_push ( $ this -> leaves , $ node ) ; } } // Remove all outgoing edges from leave unset ( $ this -> edges [ $ leave ] ) ; } if ( count ( $ this -> edges ) ) { var_dump ( $ this -> edges ) ; throw new Exception ( 'Cycle found in graph. This should not happen.' ) ; } return $ list ; }
Remove cycles from the graph

This method uses an algorithm similar to the topological sort algorithm
to remove all cycles from the graph. It will not remove all node, which
are not in cycles, but leave nodes, which are linked from cycles will
stay in the graph.

@return void
Remove cycles from the graph