Struct LengthBoundedDisjointPaths 

pub struct LengthBoundedDisjointPaths<G> { /* private fields */ }

Length-Bounded Disjoint Paths on an undirected graph.

A configuration uses max_paths * |E| binary choices. For each path slot j and edge e in graph.edges() order, x_{j,e} = 1 means that the path uses that edge. Each non-empty slot must form a simple s-t path, and the internal vertices of different slots must be disjoint. Empty slots (all zeros) are unused and do not count toward the objective. The objective is to maximize the number of non-empty valid path slots.

Implementations

impl<G: Graph> LengthBoundedDisjointPaths<G>

pub fn new(graph: G, source: usize, sink: usize, max_length: usize) -> Self

Create a new Length-Bounded Disjoint Paths instance.

The max_paths upper bound is computed automatically as min(deg(source), deg(sink)).

Panics

Panics if source or sink is not a valid graph vertex, if source == sink, or if max_length == 0.

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn source(&self) -> usize

Get the shared source vertex.

pub fn sink(&self) -> usize

Get the shared sink vertex.

pub fn max_paths(&self) -> usize

Get the upper bound on the number of path slots.

pub fn max_length(&self) -> usize

Get the maximum permitted path length in edges.

pub fn num_vertices(&self) -> usize

Get the number of vertices in the graph.

pub fn num_edges(&self) -> usize

Get the number of edges in the graph.

Trait Implementations

impl<G> BruteForceProblem for LengthBoundedDisjointPaths<G>

where G: Graph + VariantParam,

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl<G: Clone> Clone for LengthBoundedDisjointPaths<G>

fn clone(&self) -> LengthBoundedDisjointPaths<G>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G: Debug> Debug for LengthBoundedDisjointPaths<G>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for LengthBoundedDisjointPaths<SimpleGraph>

impl<'de, G> Deserialize<'de> for LengthBoundedDisjointPaths<G>

where G: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<G> Problem for LengthBoundedDisjointPaths<G>

where G: Graph + VariantParam,

const NAME: &'static str = "LengthBoundedDisjointPaths"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<Vec<bool>>

Mathematical witness type for this problem.

type Value = Max<i64>

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn evaluate( &self, solution: &Self::Solution, ) -> Result<Max<i64>, EvaluationError>

Evaluate the problem on a solution.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl RandomGenerate for LengthBoundedDisjointPaths<SimpleGraph>

fn inputs() -> Vec<CreateInputInfo>

Inputs accepted by this model’s random generator.

fn generate(data: Value) -> Result<Self, ConstructionError>

Generate a concrete problem from normalized random inputs.

impl ReduceTo<ILP> for LengthBoundedDisjointPaths<SimpleGraph>

type Result = ReductionLBDPToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl<G> Serialize for LengthBoundedDisjointPaths<G>

where G: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.