Struct LengthBoundedDisjointPaths 

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

Length-Bounded Disjoint Paths on an undirected graph.

A configuration uses max_paths * |V| binary choices. For each path slot j and vertex v, x_{j,v} = 1 means that v belongs to slot j’s path. Each non-empty slot must induce 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: 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<'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 Value = Max<usize>

The evaluation value type.

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

Returns variant attributes derived from type parameters.

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

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Max<usize>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for LengthBoundedDisjointPaths<SimpleGraph>

type Result = ReductionLBDPToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

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.

impl DeclaredVariant for LengthBoundedDisjointPaths<SimpleGraph>