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
sourceimpl Graph
impl Graph
sourcepub fn complete_graph(
number_of_variables: usize,
number_of_constraints: usize
) -> Self
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)));
sourcepub fn contains_edge(&self, edge: Edge) -> bool
pub fn contains_edge(&self, edge: Edge) -> bool
Checks if the given edge is in the graph.
sourcepub fn insert_edge(&mut self, edge: Edge) -> bool
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);
sourcepub fn remove_edge(&mut self, edge: Edge) -> bool
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);
sourcepub fn edges(&self) -> impl Iterator<Item = Edge> + '_
pub fn edges(&self) -> impl Iterator<Item = Edge> + '_
Returns an iterator over all edges in the graph in some possibly random order.
sourcepub fn number_of_variables(&self) -> usize
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.
sourcepub fn number_of_constraints(&self) -> usize
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.
sourcepub fn number_of_edges(&self) -> usize
pub fn number_of_edges(&self) -> usize
Returns the number of edges in the graph.
sourcepub fn variables(&self) -> Nodes<'_>ⓘNotable traits for Nodes<'g>impl<'g> Iterator for Nodes<'g> type Item = Node<'g>;
pub fn variables(&self) -> Nodes<'_>ⓘNotable traits for Nodes<'g>impl<'g> Iterator for Nodes<'g> type Item = Node<'g>;
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());
sourcepub fn constraints(&self) -> Nodes<'_>ⓘNotable traits for Nodes<'g>impl<'g> Iterator for Nodes<'g> type Item = Node<'g>;
pub fn constraints(&self) -> Nodes<'_>ⓘNotable traits for Nodes<'g>impl<'g> Iterator for Nodes<'g> type Item = Node<'g>;
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
sourceimpl<'de> Deserialize<'de> for Graph
impl<'de> Deserialize<'de> for Graph
sourcefn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
impl Eq for Graph
impl StructuralEq for Graph
impl StructuralPartialEq for Graph
Auto Trait Implementations
impl RefUnwindSafe for Graph
impl Send for Graph
impl Sync for Graph
impl Unpin for Graph
impl UnwindSafe for Graph
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<Q, K> Equivalent<K> for Q where
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
impl<Q, K> Equivalent<K> for Q where
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
sourcefn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
Compare self to key
and return true
if they are equal.
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcefn clone_into(&self, target: &mut T)
fn clone_into(&self, target: &mut T)
toowned_clone_into
)Uses borrowed data to replace owned data, usually by cloning. Read more