[−][src]Struct bigs::graph::Graph
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
impl Graph
[src]
pub fn new() -> Self
[src]
Creates a new empty graph.
pub fn contains_edge(&self, edge: Edge) -> bool
[src]
Checks if the given edge is in the graph.
pub fn insert_edge(&mut self, edge: Edge) -> bool
[src]
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);
pub fn remove_edge(&mut self, edge: Edge) -> bool
[src]
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);
pub fn edges(&self) -> impl Iterator<Item = Edge> + '_
[src]
Returns an iterator over all edges in the graph in some possibly random order.
pub fn number_of_variables(&self) -> usize
[src]
Returns the number of variables in the graph.
That is, the one more than the highest variable label inserted in the graph.
pub fn number_of_constraints(&self) -> usize
[src]
Returns the number of constraints in the graph.
That is, the one more than the highest constraint label inserted in the graph.
pub fn number_of_edges(&self) -> usize
[src]
Returns the number of edges in the graph.
pub fn variables(&self) -> Nodes<'_>ⓘ
[src]
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());
pub fn constraints(&self) -> Nodes<'_>ⓘ
[src]
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
impl Clone for Graph
[src]
impl Debug for Graph
[src]
impl<'de> Deserialize<'de> for Graph
[src]
pub fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
[src]
__D: Deserializer<'de>,
impl Eq for Graph
[src]
impl PartialEq<Graph> for Graph
[src]
impl Serialize for Graph
[src]
pub fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
__S: Serializer,
[src]
__S: Serializer,
impl StructuralEq for Graph
[src]
impl StructuralPartialEq for Graph
[src]
Auto Trait Implementations
impl RefUnwindSafe for Graph
[src]
impl Send for Graph
[src]
impl Sync for Graph
[src]
impl Unpin for Graph
[src]
impl UnwindSafe for Graph
[src]
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> DeserializeOwned for T where
T: for<'de> Deserialize<'de>,
[src]
T: for<'de> Deserialize<'de>,
impl<Q, K> Equivalent<K> for Q where
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
[src]
K: Borrow<Q> + ?Sized,
Q: Eq + ?Sized,
pub fn equivalent(&self, key: &K) -> bool
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,