Struct UnitDiskGraph 

pub struct UnitDiskGraph { /* private fields */ }

A unit disk graph with vertices at 2D positions.

Two vertices are connected by an edge if their Euclidean distance is at most the specified radius.

Example

use problemreductions::topology::UnitDiskGraph;

// Create a UDG with 3 vertices at positions (0,0), (1,0), (3,0)
// with unit radius (distance <= 1.0 creates an edge)
let udg = UnitDiskGraph::new(
    vec![(0.0, 0.0), (1.0, 0.0), (3.0, 0.0)],
    1.0,
);

// Vertices 0 and 1 are connected (distance = 1.0)
// Vertex 2 is isolated (distance > 1.0 from both)
assert!(udg.has_edge(0, 1));
assert!(!udg.has_edge(0, 2));
assert!(!udg.has_edge(1, 2));

Implementations

impl UnitDiskGraph

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

Create a new unit disk graph.

Arguments

• positions - 2D coordinates for each vertex
• radius - Maximum distance for an edge to exist

pub fn unit(positions: Vec<(f64, f64)>) -> Self

Create a unit disk graph with radius 1.0.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_edges(&self) -> usize

Get the number of edges.

pub fn radius(&self) -> f64

Get the radius threshold.

pub fn position(&self, v: usize) -> Option<(f64, f64)>

Get the position of a vertex.

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

Get all positions.

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

Get all edges.

pub fn has_edge(&self, u: usize, v: usize) -> bool

Check if an edge exists between two vertices.

pub fn vertex_distance(&self, u: usize, v: usize) -> Option<f64>

Get the distance between two vertices.

pub fn neighbors(&self, v: usize) -> Vec<usize>

Get all neighbors of a vertex.

pub fn degree(&self, v: usize) -> usize

Get the degree of a vertex.

pub fn bounding_box(&self) -> Option<((f64, f64), (f64, f64))>

Get the bounding box of all positions.

pub fn grid(rows: usize, cols: usize, spacing: f64, radius: f64) -> Self

Create a unit disk graph on a regular grid.

Arguments

• rows - Number of rows
• cols - Number of columns
• spacing - Distance between adjacent grid points
• radius - Edge creation threshold

Trait Implementations

impl Clone for UnitDiskGraph

fn clone(&self) -> UnitDiskGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for UnitDiskGraph

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for UnitDiskGraph

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Graph for UnitDiskGraph

fn num_vertices(&self) -> usize

Returns the number of vertices in the graph.

fn num_edges(&self) -> usize

Returns the number of edges in the graph.

fn edges(&self) -> Vec<(usize, usize)>

Returns all edges as a list of (u, v) pairs.

fn has_edge(&self, u: usize, v: usize) -> bool

Checks if an edge exists between vertices u and v.

fn neighbors(&self, v: usize) -> Vec<usize>

Returns all neighbors of vertex v.

fn degree(&self, v: usize) -> usize

Returns the degree of vertex v (number of neighbors).

fn is_empty(&self) -> bool

Returns true if the graph has no vertices.

fn for_each_edge<F>(&self, f: F)

where F: FnMut(usize, usize),

Iterates over all edges, calling a closure for each.

impl PartialEq for UnitDiskGraph

fn eq(&self, other: &UnitDiskGraph) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for UnitDiskGraph

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for UnitDiskGraph