Skip to content

Router

Some questions a product might ask on the way to a decision are too hard to answer exactly (splitting a graph into two groups with the most links between them) or have no algorithm at all (finding every rational root of an arbitrary polynomial). The router takes such a question, tagged with how hard it is, and either runs a bounded approximation or refuses (always for undec, exptime_trap and fpras). Module.decide never calls it; you call it yourself.

Public here: Subgoal, dispatch (top level); RouterResult, RouterRefuse, available_subgoals, max_cut_spectral, vertex_cover_matching, refine and WLRejected from the submodules. How to use it: Use the hardness router; why it refuses: Questions the library refuses.

dispatch

Hardness-aware solver router.

A subgoal is tagged with an Envelope. The dispatcher never falls upward into a harder class.

RouterRefuse

Bases: ValueError

The envelope forbids the requested procedure.

dispatch 

dispatch(
    sg: Subgoal, *, limits: Limits = DEFAULT_LIMITS
) -> RouterResult

Route one subgoal to its handler, or refuse it.

Parameters:

Name Type Description Default
sg Subgoal

The subgoal: a registered name, its envelope, and its payload.

 required
limits Limits

Size caps to enforce. Pass the same Limits the calling module uses so a tenant's caps (for example max_wl_k) apply here too.

 DEFAULT_LIMITS

Returns:

Type Description
RouterResult

The handler's result, or a refusal (ok=False) for UNDEC,
RouterResult

EXPTIME_TRAP and FPRAS. No FPRAS handler is implemented,
RouterResult

so an FPRAS subgoal is refused rather than silently answered
RouterResult

by a handler with a different envelope.

Raises:

Type Description
RouterRefuse

The subgoal name is not registered.
Source code in src/grounded_decision/router/dispatch.py 
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
def dispatch(sg: Subgoal, *, limits: Limits = DEFAULT_LIMITS) -> RouterResult:
    """Route one subgoal to its handler, or refuse it.

    Args:
        sg: The subgoal: a registered name, its envelope, and its payload.
        limits: Size caps to enforce. Pass the same ``Limits`` the calling
            module uses so a tenant's caps (for example ``max_wl_k``) apply
            here too.

    Returns:
        The handler's result, or a refusal (``ok=False``) for ``UNDEC``,
        ``EXPTIME_TRAP`` and ``FPRAS``. No FPRAS handler is implemented,
        so an ``FPRAS`` subgoal is refused rather than silently answered
        by a handler with a different envelope.

    Raises:
        RouterRefuse: The subgoal name is not registered.
    """

    if sg.envelope is Envelope.UNDEC:
        return RouterResult(sg.name, sg.envelope, False, "envelope UNDEC: refuse", None)
    if sg.envelope is Envelope.EXPTIME_TRAP:
        return RouterResult(
            sg.name, sg.envelope, False, "envelope EXPTIME_TRAP: refuse", None
        )
    if sg.envelope is Envelope.FPRAS:
        return RouterResult(
            sg.name,
            sg.envelope,
            False,
            "no FPRAS handler is implemented; send the subgoal with its own envelope",
            None,
        )
    fn = _HANDLERS.get(sg.name)
    if fn is None:
        raise RouterRefuse(f"unknown subgoal {sg.name!r}")
    return fn(sg, limits)

ugc

Approximations the router is allowed to run (family 102).

Max-Cut: split by the sign of the top Laplacian eigenvector, then local search; always cuts at least half the edges. It is a stand-in for the Goemans–Williamson SDP, whose ratio (about 0.878) is the best any polynomial algorithm can promise if the Unique Games Conjecture holds. Vertex Cover: maximal-matching 2-approximation (factor 2 is optimal for general graphs under the same conjecture). The router records these targets and never searches for a better worst-case factor.

ApproxResultDict

Bases: TypedDict

Serialized form of :class:ApproxResult.

vertex_cover_matching 

vertex_cover_matching(
    adj: dict[int, set[int]],
) -> ApproxResult

2-approx: take both endpoints of a maximal matching.

Source code in src/grounded_decision/router/ugc.py 
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
def vertex_cover_matching(adj: dict[int, set[int]]) -> ApproxResult:
    """2-approx: take both endpoints of a maximal matching."""

    remaining = {u: set(nbrs) for u, nbrs in adj.items()}
    cover: set[int] = set()
    verts = list(remaining)
    for u in verts:
        if u in cover:
            continue
        for v in list(remaining.get(u, ())):
            if v in cover:
                continue
            cover.add(u)
            cover.add(v)
            break
    return ApproxResult(
        name="vertex_cover",
        value=float(len(cover)),
        factor_claimed=2.0,
        catalog_optimal=True,
        detail=(
            f"maximal-matching cover size {len(cover)} (at most 2x optimal); "
            "factor 2 is optimal for general graphs only if the Unique Games "
            "Conjecture holds, and bipartite graphs can be solved exactly"
        ),
    )

wl

Color refinement (1-WL) and a 2-WL pairwise variant.

Family 133 (Lean): variable-k identification is EXPTIME-complete and k-WL is n^{Ω(k)}. The router refuses k > 2.

color_refinement 

color_refinement(
    graph: Graph, rounds: int | None = None
) -> tuple[int, ...]

1-WL. Returns a stable color of each vertex in sorted vertex order.

Source code in src/grounded_decision/router/wl.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def color_refinement(graph: Graph, rounds: int | None = None) -> tuple[int, ...]:
    """1-WL. Returns a stable color of each vertex in sorted vertex order."""

    verts = sorted(graph)
    color = {v: 0 for v in verts}
    limit = rounds if rounds is not None else len(verts)
    for _ in range(limit):
        buckets: defaultdict[_VertexSignature, list[int]] = defaultdict(list)
        for v in verts:
            neigh = tuple(sorted(color[u] for u in graph.get(v, ())))
            buckets[(color[v], neigh)].append(v)
        palette = {key: i for i, key in enumerate(sorted(buckets))}
        nxt: dict[int, int] = {}
        for key, vs in buckets.items():
            c = palette[key]
            for v in vs:
                nxt[v] = c
        if nxt == color:
            break
        color = nxt
    return tuple(color[v] for v in verts)

wl2_hash 

wl2_hash(
    graph: Graph, rounds: int | None = None
) -> tuple[int, ...]

Pair colors: a practical 2-WL stand-in on ordered pairs.

Source code in src/grounded_decision/router/wl.py 
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
def wl2_hash(graph: Graph, rounds: int | None = None) -> tuple[int, ...]:
    """Pair colors: a practical 2-WL stand-in on ordered pairs."""

    verts = sorted(graph)
    pairs = [(i, j) for i in verts for j in verts]
    adj = graph
    color = {
        (i, j): (0 if i == j else (1 if j in adj.get(i, ()) else 2)) for i, j in pairs
    }
    limit = rounds if rounds is not None else max(1, len(verts))
    for _ in range(limit):
        buckets: defaultdict[_PairSignature, list[tuple[int, int]]] = defaultdict(list)
        for i, j in pairs:
            sig = (
                color[(i, j)],
                tuple(sorted(color[(i, k)] for k in verts)),
                tuple(sorted(color[(k, j)] for k in verts)),
            )
            buckets[sig].append((i, j))
        palette = {key: idx for idx, key in enumerate(sorted(buckets))}
        nxt: dict[tuple[int, int], int] = {}
        for key, ps in buckets.items():
            c = palette[key]
            for p in ps:
                nxt[p] = c
        if nxt == color:
            break
        color = nxt
    return tuple(color[p] for p in pairs)