maximum-cardinality-order ( graph -- order )

Vocabulary

compiler.cfg.register-allocation.chordal

Inputs

graph

an object

Outputs

order

an object

Definition

USING: arrays assocs compiler.utilities heaps kernel math
sequences ;

IN: compiler.cfg.register-allocation.chordal

:: maximum-cardinality-order ( graph -- order )
    H{ } clone :> weights
    H{ } clone :> selected <max-heap> :> pending
    V{ } clone :> order graph keys
    [| vertex | vertex 0 vertex neg 2array pending heap-push ]
    each
    [ order length graph assoc-size < ] [
        pending heap-pop drop :> best best selected key?
        [ ] [
            best selected conjoin best order push best graph at 
            [| neighbor |
                neighbor selected key?
                [ ] [
                    neighbor weights inc-at
                    neighbor neighbor weights at
                    neighbor neg 2array pending heap-push
                ] if
            ] each
        ] if
    ] while order ;