Struct ReductionGraph 

pub struct ReductionGraph { /* private fields */ }

Runtime graph of all registered reductions.

Uses variant-level nodes: each node is a unique (problem_name, variant) pair. All edges come from inventory::iter::<ReductionEntry> registrations.

The graph supports:

• Auto-discovery of reductions from inventory::iter::<ReductionEntry>
• Dijkstra with custom cost functions
• Path finding by problem type or by name

Implementations

impl ReductionGraph

pub fn new() -> Self

Create a new reduction graph with all registered reductions from inventory.

pub fn variant_to_map(variant: &[(&str, &str)]) -> BTreeMap<String, String>

Convert a variant slice to a BTreeMap. Normalizes empty “graph” values to “SimpleGraph” for consistency.

pub fn find_cheapest_path<C: PathCostFn>( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, input_size: &ProblemSize, cost_fn: &C, ) -> Option<ReductionPath>

Find the cheapest path between two specific problem variants.

Uses Dijkstra’s algorithm on the variant-level graph from the exact source variant node to the exact target variant node.

pub fn find_cheapest_path_mode<C: PathCostFn>( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, mode: ReductionMode, input_size: &ProblemSize, cost_fn: &C, ) -> Option<ReductionPath>

Find the cheapest path between two specific problem variants while requiring a specific edge capability.

pub fn find_all_paths( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, ) -> Vec<ReductionPath>

Find all simple paths between two specific problem variants.

Uses all_simple_paths on the variant-level graph from the exact source variant node to the exact target variant node.

pub fn find_all_paths_mode( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, mode: ReductionMode, ) -> Vec<ReductionPath>

Find all simple paths between two specific problem variants while requiring a specific edge capability.

pub fn find_paths_up_to( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, limit: usize, ) -> Vec<ReductionPath>

Find up to limit simple paths between two specific problem variants.

Like find_all_paths but stops enumeration after collecting limit paths. This avoids combinatorial explosion on dense graphs.

pub fn find_paths_up_to_mode( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, mode: ReductionMode, limit: usize, ) -> Vec<ReductionPath>

Like find_all_paths_mode but stops enumeration after collecting limit paths.

pub fn find_paths_up_to_mode_bounded( &self, source: &str, source_variant: &BTreeMap<String, String>, target: &str, target_variant: &BTreeMap<String, String>, mode: ReductionMode, limit: usize, max_intermediate_nodes: Option<usize>, ) -> Vec<ReductionPath>

Like find_paths_up_to_mode but also bounds the number of intermediate nodes in each enumerated path.

pub fn has_direct_reduction<S: Problem, T: Problem>(&self) -> bool

Check if a direct reduction exists from S to T.

pub fn has_direct_reduction_by_name(&self, src: &str, dst: &str) -> bool

Check if a direct reduction exists by name.

pub fn has_direct_reduction_by_name_mode( &self, src: &str, dst: &str, mode: ReductionMode, ) -> bool

Check if a direct reduction exists by name in a specific mode.

pub fn has_direct_reduction_mode<S: Problem, T: Problem>( &self, mode: ReductionMode, ) -> bool

Check if a direct reduction exists from S to T in a specific mode.

pub fn problem_types(&self) -> Vec<&'static str>

Get all registered problem type names (base names).

pub fn num_types(&self) -> usize

Get the number of registered problem types (unique base names).

pub fn num_reductions(&self) -> usize

Get the number of registered reductions (edges).

pub fn num_variant_nodes(&self) -> usize

Get the number of variant-level nodes.

pub fn path_overheads(&self, path: &ReductionPath) -> Vec<ReductionOverhead>

Get the per-edge overhead expressions along a reduction path.

Returns one ReductionOverhead per edge (i.e., path.steps.len() - 1 items).

Panics if any step in the path does not correspond to an edge in the graph.

pub fn compose_path_overhead(&self, path: &ReductionPath) -> ReductionOverhead

Compose overheads along a path symbolically.

Returns a single ReductionOverhead whose expressions map from the source problem’s size variables directly to the final target’s size variables.

pub fn variants_for(&self, name: &str) -> Vec<BTreeMap<String, String>>

Get all variant maps registered for a problem name.

Returns variants sorted deterministically: the “default” variant (SimpleGraph, i32, etc.) comes first, then remaining variants in lexicographic order.

pub fn default_variant_for( &self, name: &str, ) -> Option<BTreeMap<String, String>>

Get the declared default variant for a problem type.

Returns the variant that was marked default in declare_variants!. If no entry was explicitly marked default, the first registered variant for the problem is used as the implicit default. Returns None if the problem type is not registered.

pub fn variant_complexity( &self, name: &str, variant: &BTreeMap<String, String>, ) -> Option<&'static str>

Get the complexity expression for a specific variant.

pub fn outgoing_reductions(&self, name: &str) -> Vec<ReductionEdgeInfo>

Get all outgoing reductions from a problem (across all its variants).

pub fn size_field_names(&self, name: &str) -> Vec<&'static str>

Get the problem size field names for a problem type.

Derives size fields from the overhead expressions of reduction entries where this problem appears as source or target. When the problem is a source, its size fields are the input variables referenced in the overhead expressions. When it’s a target, its size fields are the output field names.

pub fn evaluate_path_overhead( &self, path: &ReductionPath, input_size: &ProblemSize, ) -> Option<ProblemSize>

Evaluate the cumulative output size along a reduction path.

Walks the path from start to end, applying each edge’s overhead expressions to transform the problem size at each step. Returns None if any edge in the path cannot be found.

pub fn compute_source_size(name: &str, instance: &dyn Any) -> ProblemSize

Compute the source problem’s size from a type-erased instance.

Iterates over all registered reduction entries with a matching source name and merges their source_size_fn results to capture all size fields. Different entries may reference different getter methods (e.g., one uses num_vertices while another also uses num_edges).

pub fn incoming_reductions(&self, name: &str) -> Vec<ReductionEdgeInfo>

Get all incoming reductions to a problem (across all its variants).

pub fn k_neighbors( &self, name: &str, variant: &BTreeMap<String, String>, max_hops: usize, direction: TraversalFlow, ) -> Vec<NeighborInfo>

Find all problems reachable within max_hops edges from a starting node.

Returns neighbors sorted by (hops, name). The starting node itself is excluded. If a node is reachable at multiple distances, it appears at the shortest distance only.

pub fn k_neighbor_tree( &self, name: &str, variant: &BTreeMap<String, String>, max_hops: usize, direction: TraversalFlow, ) -> Vec<NeighborTree>

Build a tree of neighbors via BFS with parent tracking.

Returns the children of the starting node as a forest of NeighborTree nodes. Each node appears at most once (shortest-path tree). Children are sorted by name.

impl ReductionGraph

pub fn to_json_string(&self) -> Result<String, Error>

Export the reduction graph as a JSON string.

pub fn to_json_file(&self, path: &Path) -> Result<()>

Export the reduction graph to a JSON file.

pub fn find_best_entry( &self, source_name: &str, source_variant: &BTreeMap<String, String>, target_name: &str, target_variant: &BTreeMap<String, String>, ) -> Option<MatchedEntry>

Find the matching ReductionEntry for a (source_name, target_name) pair given exact source and target variants.

Returns Some(MatchedEntry) only when both the source and target variants match exactly. No fallback is attempted — callers that need fuzzy matching should resolve variants before calling this method.

impl ReductionGraph

pub fn reduce_along_path( &self, path: &ReductionPath, source: &dyn Any, ) -> Option<ReductionChain>

Execute a reduction path on a source problem instance.

Looks up each edge’s reduce_fn, chains them, and returns the resulting ReductionChain. The source must be passed as &dyn Any (use &problem as &dyn Any or pass a concrete reference directly).

Example

let chain = graph.reduce_along_path(&path, &source_problem)?;
let target: &QUBO<f64> = chain.target_problem();
let source_solution = chain.extract_solution(&target_solution);

pub fn reduce_aggregate_along_path( &self, path: &ReductionPath, source: &dyn Any, ) -> Option<AggregateReductionChain>

Execute an aggregate-value reduction path on a source problem instance.

Trait Implementations

impl Default for ReductionGraph

fn default() -> Self

Returns the “default value” for a type.