public static Weighted<Arborescence<Node>> getMaxArborescence(WeightedGraph graph) {
        final PartialSolution partialSolution =
                PartialSolution.initialize(graph.filterEdges(not(DirectedEdge.isAutoCycle())));
        // In the beginning, subgraph has no edges, so no SCC has in-edges.
        final Deque<Node> componentsWithNoInEdges = new ArrayDeque<>(partialSolution.getNodes());

        // Work our way through all componentsWithNoInEdges, in no particular order
        while (!componentsWithNoInEdges.isEmpty()) {
            final Node component = componentsWithNoInEdges.poll();
            // find maximum edge entering 'component' from outside 'component'.
            final Optional<ExclusiveEdge> oMaxInEdge = partialSolution.popBestEdge(component);
            if (!oMaxInEdge.isPresent()) continue; // No in-edges left to consider for this component. Done with it!
            final ExclusiveEdge maxInEdge = oMaxInEdge.get();
            // add the new edge to subgraph, merging SCCs if necessary
            final Optional<Node> newComponent = partialSolution.addEdge(maxInEdge);
            if (newComponent.isPresent()) {
                // addEdge created a cycle/component, which means the new component doesn't have any incoming edges
                componentsWithNoInEdges.add(newComponent.get());
            }
        }
        // Once no component has incoming edges left to consider, it's time to recover the optimal branching.
        return partialSolution.recoverBestArborescence();
    }
public static Weighted < Arborescence < Node > > getMaxArborescence ( WeightedGraph graph ) { final PartialSolution partialSolution = PartialSolution . initialize ( graph . filterEdges ( not ( DirectedEdge . isAutoCycle ( ) ) ) ) ; final Deque < Node > componentsWithNoInEdges = new ArrayDeque < > ( partialSolution . getNodes ( ) ) ; while ( ! componentsWithNoInEdges . isEmpty ( ) ) { final Node component = componentsWithNoInEdges . poll ( ) ; final Optional < ExclusiveEdge > oMaxInEdge = partialSolution . popBestEdge ( component ) ; if ( ! oMaxInEdge . isPresent ( ) ) continue ; final ExclusiveEdge maxInEdge = oMaxInEdge . get ( ) ; final Optional < Node > newComponent = partialSolution . addEdge ( maxInEdge ) ; if ( newComponent . isPresent ( ) ) { componentsWithNoInEdges . add ( newComponent . get ( ) ) ; } } return partialSolution . recoverBestArborescence ( ) ; }
Find an optimal arborescence of the given graph.