Struct BiconnectivityAugmentation 

pub struct BiconnectivityAugmentation<G, W>
where
    W: WeightElement,
{ /* private fields */ }

The Biconnectivity Augmentation problem.

Given a graph G = (V, E), weighted potential edges, and a budget B, determine whether there exists a subset of potential edges E' such that:

• sum_{e in E'} w(e) <= B
• (V, E union E') is biconnected

Implementations

impl<G: Graph, W: WeightElement> BiconnectivityAugmentation<G, W>

pub fn new( graph: G, potential_weights: Vec<(usize, usize, W)>, budget: W::Sum, ) -> Self

Create a new biconnectivity augmentation instance.

Panics

Panics if any potential edge references a vertex index outside the graph, is a self-loop, duplicates another candidate edge, or already exists in the input graph.

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn potential_weights(&self) -> &[(usize, usize, W)]

Get the weighted potential edges.

pub fn budget(&self) -> &W::Sum

Get the budget.

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 num_potential_edges(&self) -> usize

Get the number of potential augmentation edges.

pub fn is_weighted(&self) -> bool

Check if the problem uses a non-unit weight type.

Trait Implementations

impl<G: Clone, W> Clone for BiconnectivityAugmentation<G, W>

where W: WeightElement + Clone, W::Sum: Clone,

fn clone(&self) -> BiconnectivityAugmentation<G, W>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<G: Debug, W> Debug for BiconnectivityAugmentation<G, W>

where W: WeightElement + Debug, W::Sum: Debug,

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

Formats the value using the given formatter.

impl<'de, G, W> Deserialize<'de> for BiconnectivityAugmentation<G, W>

where W: WeightElement + Deserialize<'de>, G: Deserialize<'de>, W::Sum: 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, W> Problem for BiconnectivityAugmentation<G, W>

where G: Graph + VariantParam, W: WeightElement + VariantParam,

const NAME: &'static str = "BiconnectivityAugmentation"

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, W> Serialize for BiconnectivityAugmentation<G, W>

where W: WeightElement + Serialize, G: Serialize, W::Sum: 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 BiconnectivityAugmentation<SimpleGraph, i32>

impl<G, W> SatisfactionProblem for BiconnectivityAugmentation<G, W>

where G: Graph + VariantParam, W: WeightElement + VariantParam,