Struct OptimalLinearArrangement 

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

The Optimal Linear Arrangement problem.

Given an undirected graph G = (V, E) and a non-negative integer K, determine whether there exists a one-to-one function f: V -> {0, 1, …, |V|-1} such that sum_{{u,v} in E} |f(u) - f(v)| <= K.

This is the decision (satisfaction) version of the problem, following the Garey & Johnson formulation (GT42).

Representation

Each vertex is assigned a variable representing its position in the arrangement. Variable i takes a value in {0, 1, …, n-1}, and a valid configuration must be a permutation (all positions are distinct) with total edge length at most K.

Type Parameters

• G - The graph type (e.g., SimpleGraph)

Example

use problemreductions::models::graph::OptimalLinearArrangement;
use problemreductions::topology::SimpleGraph;
use problemreductions::{Problem, Solver, BruteForce};

// Path graph: 0-1-2-3 with bound 3
let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let problem = OptimalLinearArrangement::new(graph, 3);

let solver = BruteForce::new();
let solution = solver.find_satisfying(&problem);
assert!(solution.is_some());

Implementations

impl<G: Graph> OptimalLinearArrangement<G>

pub fn new(graph: G, bound: usize) -> Self

Create a new Optimal Linear Arrangement problem.

Arguments

• graph - The undirected graph G = (V, E)
• bound - The upper bound K on total edge length

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn bound(&self) -> usize

Get the bound K.

pub fn num_vertices(&self) -> usize

Get the number of vertices in the underlying graph.

pub fn num_edges(&self) -> usize

Get the number of edges in the underlying graph.

pub fn is_valid_solution(&self, config: &[usize]) -> bool

Check if a configuration is a valid permutation with total edge length at most K.

pub fn total_edge_length(&self, config: &[usize]) -> Option<usize>

Compute the total edge length for a given arrangement.

Returns None if the configuration is not a valid permutation.

Trait Implementations

impl<G: Clone> Clone for OptimalLinearArrangement<G>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<G: Debug> Debug for OptimalLinearArrangement<G>

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

Formats the value using the given formatter.

impl<'de, G> Deserialize<'de> for OptimalLinearArrangement<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 OptimalLinearArrangement<G>

where G: Graph + VariantParam,

const NAME: &'static str = "OptimalLinearArrangement"

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

type Metric = bool

The evaluation metric 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]) -> bool

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<G> Serialize for OptimalLinearArrangement<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 OptimalLinearArrangement<SimpleGraph>

impl<G: Graph + VariantParam> SatisfactionProblem for OptimalLinearArrangement<G>