non_dominated_sort.bend checks

raw source on the hub · import 0x527a2a4fa91b05a0250d7be0e11d232a/non_dominated_sort.bend as Non_dominated_sort

NonDominatedSort — C# Unsga3.Core.NonDominatedSort. Fast non-dominated sorting by peeling (Deb et al.). v0: Pareto on objectives only (no constraint-domination until constraints exist).

Layout (Bend guide: Arrays cannot ride a fork tree; List.get is a cons walk): one sequential pass materializes Row{index, objectives} so the peel never List.gets a fat Individual. Per-candidate split still mid-splits a b = f(lo) f(hi) (same front/leftover order as the tail-first walk). Inner is_dominated stays a sequential OR so a first hit skips the rest. Same dominance definition; same ranks and index order for the same population.

3 imports

import Base
import ./individual.bend as Ind
import ./util.bend as Util

Types

type Row source · line 19 · raw

Data

One sort-row: population index plus the objective vector. Built once per sort; leftover peels reuse the same rows (no re-index).

Row
```
@i:Nat -> @f:List<&2, F32> -> Row
```

type Split source · line 134 · raw

Data

Split

@ff:List<&2, Nat> -> @ot:List<&2, Row> -> Split

Definitions

def row_idx source · line 25 · raw

@r:Row -> Nat

def row_f source · line 30 · raw

@r:Row -> List<&2, F32>

def rows_of.go source · line 35 · raw

@pop:List<&2, 0x527a2a4fa91b05a0250d7be0e11d232a/individual.Individual> -> @+i:Nat -> List<&2, Row>

def rows_of source · line 42 · raw

@+pop:List<&2, 0x527a2a4fa91b05a0250d7be0e11d232a/individual.Individual> -> List<&2, Row>

def row_idxs source · line 45 · raw

@rs:List<&2, Row> -> List<&2, Nat>

def verdict.a source · line 52 · raw

@bb:Bool -> Nat

def verdict.b source · line 59 · raw

@bb:Bool -> Nat

def verdict source · line 67 · raw

@ab:Bool -> @bb:Bool -> Nat

Minimization: 0n = mutual non-domination, 1n = a dominates b, 2n = b dominates a.

def compare_pareto.go source · line 74 · raw

@a:List<&2, F32> -> @b:List<&2, F32> -> @ab:Bool -> @bb:Bool -> Nat

def compare_pareto source · line 88 · raw

@a:List<&2, F32> -> @b:List<&2, F32> -> Nat

def dominates.is1 source · line 91 · raw

@p:Nat -> Bool

def dominates.fin source · line 98 · raw

@c:Nat -> Bool

def dominates source · line 105 · raw

@a:0x527a2a4fa91b05a0250d7be0e11d232a/individual.Individual -> @b:0x527a2a4fa91b05a0250d7be0e11d232a/individual.Individual -> Bool

def dominates_ff source · line 108 · raw

@+fa:List<&2, F32> -> @+fb:List<&2, F32> -> Bool

def is_dominated source · line 114 · raw

@+all:List<&2, Row> -> @+i:Nat -> @+fi:List<&2, F32> -> Bool

Sequential OR so a first hit can skip the rest. Candidate-level parallelism lives in split_walk (coarse mid-split). Walks all rows directly — no List.get into the population.

def row_dom source · line 126 · raw

@+all:List<&2, Row> -> @+r:Row -> Bool

def split_put source · line 140 · raw

@+r:Row -> @s:Split -> @dominated:Bool -> Split

def split_cat source · line 149 · raw

@a:Split -> @b:Split -> Split

def split_walk.go source · line 156 · raw

@+all:List<&2, Row> -> @+fuel:Nat -> @cand:List<&2, Row> -> Split

Per-candidate split is independent given all. Mid-split then concatenate fronts / leftovers so order matches the tail-first walk.

def split_walk source · line 172 · raw

@+all:List<&2, Row> -> @+cand:List<&2, Row> -> Split

def split_ne source · line 177 · raw

@+r:Row -> @+rest:List<&2, Row> -> @s:Split -> Split

Empty first front (unreachable on a finite Pareto set) keeps the head so peel stays a partition.

def split_front source · line 186 · raw

@remaining:List<&2, Row> -> Split

def split_fst source · line 193 · raw

@s:Split -> List<&2, Nat>

def split_snd source · line 198 · raw

@s:Split -> List<&2, Row>

def peel source · line 203 · raw

@fuel:Nat -> @remaining:List<&2, Row> -> List<&2, List<&2, Nat>>

def sort source · line 215 · raw

@population:List<&2, 0x527a2a4fa91b05a0250d7be0e11d232a/individual.Individual> -> List<&2, List<&2, Nat>>

def front_index_count source · line 223 · raw

@fronts:List<&2, List<&2, Nat>> -> Nat