Struct MinimumGeometricConnectedDominatingSet 

pub struct MinimumGeometricConnectedDominatingSet { /* private fields */ }

Minimum Geometric Connected Dominating Set.

Given points P in the plane and distance threshold B > 0, find a minimum subset P’ ⊆ P such that every point in P \ P’ is within distance B of some point in P’, and the subgraph induced on P’ (edges between points within distance B) is connected.

Example

use problemreductions::models::graph::MinimumGeometricConnectedDominatingSet;
use problemreductions::{Problem, Solver, BruteForce};

// Four collinear points with spacing 3 and radius 3.5:
// each point reaches its immediate neighbor but not two steps away.
let points = vec![(0.0, 0.0), (3.0, 0.0), (6.0, 0.0), (9.0, 0.0)];
let problem = MinimumGeometricConnectedDominatingSet::new(points, 3.5);

let solver = BruteForce::new();
let witness = solver.find_witness(&problem).unwrap();
let value = problem.evaluate(&witness).unwrap();
assert_eq!(value, 2); // Two interior points dominate all and form a connected pair

Implementations

impl MinimumGeometricConnectedDominatingSet

pub fn new(points: Vec<(f64, f64)>, radius: f64) -> Self

Create a new instance.

Panics

Panics if radius <= 0.0 or if points is empty.

pub fn try_new(points: Vec<(f64, f64)>, radius: f64) -> Result<Self, String>

Fallible constructor used by CLI validation and deserialization.

pub fn num_points(&self) -> usize

Get the number of points.

pub fn radius(&self) -> f64

Get the distance threshold.

pub fn points(&self) -> &[(f64, f64)]

Get a reference to the points.

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

Check if a configuration is a valid connected dominating set.

Trait Implementations

impl Clone for MinimumGeometricConnectedDominatingSet

fn clone(&self) -> MinimumGeometricConnectedDominatingSet

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MinimumGeometricConnectedDominatingSet

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumGeometricConnectedDominatingSet

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumGeometricConnectedDominatingSet

const NAME: &'static str = "MinimumGeometricConnectedDominatingSet"

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

type Value = Min<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]) -> Min<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 Serialize for MinimumGeometricConnectedDominatingSet

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 MinimumGeometricConnectedDominatingSet