Struct Graph

Source
pub struct Graph { /* private fields */ }
Expand description

A bipartite regular graph.

A graph is a set of variables and constraints together with a set of edges. An edge is a (variable, constraint) pair.

A graph can be build manually or from a Sampler.

§Example

use bigs::graph::{Edge, Graph};

let mut graph = Graph::new();

graph.insert_edge(Edge::new(0, 0)); // Edge between variable 0 and constraint 0.
graph.insert_edge(Edge::new(0, 1)); // Edge between variable 0 and constraint 1.
graph.insert_edge(Edge::new(1, 2)); // Edge between variable 1 and constraint 2.
graph.insert_edge(Edge::new(1, 3)); // Edge between variable 1 and constraint 3.

assert_eq!(graph.number_of_variables(), 2);
assert_eq!(graph.number_of_constraints(), 4);
assert_eq!(graph.number_of_edges(), 4);

for variable in graph.variables() {
    assert_eq!(variable.degree(), 2);
}

for constraint in graph.constraints() {
    assert_eq!(constraint.degree(), 1);
}

§Performance tips

Don’t use unnecessary large labels for variable and constraint. The construction assume that you will use labels 0 to n - 1 if you want n variables and the same for constraints.

If for whatever reason you want to assign a node with a large label, notes that this will allocate the needed memory for all nodes up to that label.

use bigs::graph::{Edge, Graph};

let mut graph = Graph::new();
graph.insert_edge(Edge::new(0, 42));

assert_eq!(graph.number_of_variables(), 1);
assert_eq!(graph.number_of_constraints(), 43);

Implementations§

Source§

impl Graph

Source

pub fn new() -> Self

Creates a new empty graph.

Source

pub fn complete_graph( number_of_variables: usize, number_of_constraints: usize, ) -> Self

Creates a complete graph

§Example
use bigs::graph::{Edge, Graph};

let mut graph = Graph::complete_graph(3, 2);
assert_eq!(graph.number_of_variables(), 3);
assert_eq!(graph.number_of_constraints(), 2);
assert_eq!(graph.number_of_edges(), 6);

assert!(graph.contains_edge(Edge::new(0, 0)));
assert!(graph.contains_edge(Edge::new(1, 0)));
assert!(graph.contains_edge(Edge::new(2, 0)));
assert!(graph.contains_edge(Edge::new(0, 1)));
assert!(graph.contains_edge(Edge::new(1, 1)));
assert!(graph.contains_edge(Edge::new(2, 1)));
Source

pub fn contains_edge(&self, edge: Edge) -> bool

Checks if the given edge is in the graph.

Source

pub fn insert_edge(&mut self, edge: Edge) -> bool

Inserts the given edge in the graph and returns true if the edge was not already in the graph.

If the edge variable is greater or equal to the number of variables in the graph, the number of variables will be incremented by the difference. Same holds for constraints.

§Example
use bigs::graph::{Edge, Graph};

let mut graph = Graph::new();
assert_eq!(graph.number_of_variables(), 0);
assert_eq!(graph.number_of_constraints(), 0);
assert_eq!(graph.number_of_edges(), 0);

graph.insert_edge(Edge::new(0, 0));
assert_eq!(graph.number_of_variables(), 1);
assert_eq!(graph.number_of_constraints(), 1);
assert_eq!(graph.number_of_edges(), 1);

graph.insert_edge(Edge::new(5, 6));
assert_eq!(graph.number_of_variables(), 6);
assert_eq!(graph.number_of_constraints(), 7);
assert_eq!(graph.number_of_edges(), 2);

assert_eq!(graph.insert_edge(Edge::new(0, 0)), false);
Source

pub fn remove_edge(&mut self, edge: Edge) -> bool

Removes the given edge from the graph if it exists and returns true. Else, returns false.

However, this do not update the number of variables and constraints in the graph.

§Example
use bigs::graph::{Edge, Graph};

let mut graph = Graph::new();
assert_eq!(graph.number_of_variables(), 0);
assert_eq!(graph.number_of_constraints(), 0);
assert_eq!(graph.number_of_edges(), 0);

graph.insert_edge(Edge::new(0, 0));
assert_eq!(graph.number_of_variables(), 1);
assert_eq!(graph.number_of_constraints(), 1);
assert_eq!(graph.number_of_edges(), 1);

graph.remove_edge(Edge::new(0, 0));
assert_eq!(graph.number_of_variables(), 1);
assert_eq!(graph.number_of_constraints(), 1);
assert_eq!(graph.number_of_edges(), 0);
Source

pub fn edges(&self) -> impl Iterator<Item = Edge> + '_

Returns an iterator over all edges in the graph in some possibly random order.

Source

pub fn number_of_variables(&self) -> usize

Returns the number of variables in the graph.

That is, the one more than the highest variable label inserted in the graph.

Source

pub fn number_of_constraints(&self) -> usize

Returns the number of constraints in the graph.

That is, the one more than the highest constraint label inserted in the graph.

Source

pub fn number_of_edges(&self) -> usize

Returns the number of edges in the graph.

Source

pub fn variables(&self) -> Nodes<'_>

Returns an iterator over all variables in the graph in increasing label order.

§Example
use bigs::graph::{Edge, Graph};
use indexmap::indexset;

let mut graph = Graph::new();

graph.insert_edge(Edge::new(0, 0)); // Edge between variable 0 and constraint 0.
graph.insert_edge(Edge::new(0, 1)); // Edge between variable 0 and constraint 1.
graph.insert_edge(Edge::new(1, 2)); // Edge between variable 1 and constraint 2.
graph.insert_edge(Edge::new(1, 3)); // Edge between variable 1 and constraint 3.

let mut iter = graph.variables();

let first_variable = iter.next().unwrap();
assert_eq!(first_variable.label(), 0);
assert_eq!(first_variable.degree(), 2);
assert_eq!(first_variable.neighbors(), &indexset! { 0, 1 });

let second_variable = iter.next().unwrap();
assert_eq!(second_variable.label(), 1);
assert_eq!(second_variable.degree(), 2);
assert_eq!(second_variable.neighbors(), &indexset! { 2, 3 });

assert!(iter.next().is_none());
Source

pub fn constraints(&self) -> Nodes<'_>

Returns an iterator over all constraints in the graph in increasing label order.

§Example
use bigs::graph::{Edge, Graph};
use indexmap::indexset;

let mut graph = Graph::new();

graph.insert_edge(Edge::new(0, 0)); // Edge between variable 0 and constraint 0.
graph.insert_edge(Edge::new(0, 1)); // Edge between variable 0 and constraint 1.
graph.insert_edge(Edge::new(1, 2)); // Edge between variable 1 and constraint 2.
graph.insert_edge(Edge::new(1, 3)); // Edge between variable 1 and constraint 3.

let mut iter = graph.constraints();

let first_constraint = iter.next().unwrap();
assert_eq!(first_constraint.label(), 0);
assert_eq!(first_constraint.degree(), 1);
assert_eq!(first_constraint.neighbors(), &indexset! { 0 });

let second_constraint = iter.next().unwrap();
assert_eq!(second_constraint.label(), 1);
assert_eq!(second_constraint.degree(), 1);
assert_eq!(second_constraint.neighbors(), &indexset! { 0 });

assert!(iter.next().is_some());
assert!(iter.next().is_some());
assert!(iter.next().is_none());

Trait Implementations§

Source§

impl Clone for Graph

Source§

fn clone(&self) -> Graph

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for Graph

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<'de> Deserialize<'de> for Graph

Source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
Source§

impl PartialEq for Graph

Source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

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

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

impl Serialize for Graph

Source§

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

Serialize this value into the given Serde serializer. Read more
Source§

impl Eq for Graph

Source§

impl StructuralPartialEq for Graph

Auto Trait Implementations§

§

impl Freeze for Graph

§

impl RefUnwindSafe for Graph

§

impl Send for Graph

§

impl Sync for Graph

§

impl Unpin for Graph

§

impl UnwindSafe for Graph

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

Source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V

Source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,