Struct graphbench::editgraph::EditGraph
source · [−]pub struct EditGraph { /* private fields */ }
Expand description
An implementation of the MutableGraph trait with additional convenient editing and generating functions.
Implementations
sourceimpl EditGraph
impl EditGraph
sourcepub fn independent(n: u32) -> EditGraph
pub fn independent(n: u32) -> EditGraph
Generates an empty graph (independent set) on n
vertices.
sourcepub fn biclique(s: u32, t: u32) -> EditGraph
pub fn biclique(s: u32, t: u32) -> EditGraph
Generates a complete bipartite graph (biclique) on s
+t
vertices.
sourcepub fn complete_kpartite<'a, I>(sizes: I) -> EditGraphwhere
I: IntoIterator<Item = &'a u32>,
pub fn complete_kpartite<'a, I>(sizes: I) -> EditGraphwhere
I: IntoIterator<Item = &'a u32>,
Generates a complete k-partite graph.
Arguments
sizes
- The sizes of each partite set as a sequence of integers.
sourcepub fn disj_union(&self, graph: &impl Graph) -> EditGraph
pub fn disj_union(&self, graph: &impl Graph) -> EditGraph
Creates a new graph that is the disjoint union of self
and graph
.
The vertices of the second graph are relabelled to avoid index clashes.
sourcepub fn disj_unions<'a, I, G>(it: I) -> EditGraphwhere
I: Iterator<Item = &'a G>,
G: Graph + 'a,
pub fn disj_unions<'a, I, G>(it: I) -> EditGraphwhere
I: Iterator<Item = &'a G>,
G: Graph + 'a,
Computes the disjoint unions of all graphs in the iterator it
.
sourcepub fn normalize(&self) -> (EditGraph, FxHashMap<Vertex, Vertex>)
pub fn normalize(&self) -> (EditGraph, FxHashMap<Vertex, Vertex>)
Creates a copy of the graph in which vertices are labelled from $0$ to $n-1$, where $n$ is the number of vertices in the graph. The relative order of the indices is preserved, e.g. the smallest vertex from the original graph will be labelled $0$ and the largest one $n-1$.
Returns a tuple (graph
, map
) where graph
is the relabelled graph and
map
stores the mapping from new vertices to old vertices.
sourcepub fn contract<'a, I>(&mut self, vertices: I) -> Vertexwhere
I: Iterator<Item = &'a Vertex>,
pub fn contract<'a, I>(&mut self, vertices: I) -> Vertexwhere
I: Iterator<Item = &'a Vertex>,
Contracts all vertices
into the first vertex of the sequence. The contracted vertex has
as its neighbours all vertices that were adjacent to at least one vertex in vertices
.
This function panics if the sequence is empty.
Returns the contracted vertex.
sourcepub fn contract_pair(&mut self, u: &Vertex, v: &Vertex)
pub fn contract_pair(&mut self, u: &Vertex, v: &Vertex)
Contracts the pair ${u,v}$ be identifying $v$ with $u$. The operation removes $v$ from the graph and adds $v$’s neighbours to $u$.
Panics if either of the two vertices does not exist.
sourcepub fn contract_into<'a, I>(&mut self, center: &Vertex, vertices: I)where
I: Iterator<Item = &'a Vertex>,
pub fn contract_into<'a, I>(&mut self, center: &Vertex, vertices: I)where
I: Iterator<Item = &'a Vertex>,
Contracts all vertices
into the center
vertex. The contracted vertex has
as its neighbours all vertices that were adjacent to at least one vertex in vertices
.
sourceimpl EditGraph
impl EditGraph
sourcepub fn from_txt(filename: &str) -> Result<EditGraph>
pub fn from_txt(filename: &str) -> Result<EditGraph>
Loads the graph from a text file which contains edges separated by line breaks. Edges must be pairs of integers separated by a space.
For example, assume the file edges.txt
contains the following:
0 1
0 2
0 3
We can then load the file as follows:
use graphbench::graph::*;
use graphbench::editgraph::EditGraph;
use graphbench::iterators::EdgeIterable;
fn main() {
let graph = EditGraph::from_txt("edges.txt").expect("Could not open edges.txt");
println!("Vertices: {:?}", graph.vertices().collect::<Vec<&Vertex>>());
println!("Edges: {:?}", graph.edges().collect::<Vec<Edge>>());
}
sourcepub fn from_gzipped(filename: &str) -> Result<EditGraph>
pub fn from_gzipped(filename: &str) -> Result<EditGraph>
Loads the graph from a gzipped text file which otherwise follows the format described in EditGraph::from_txt.
Trait Implementations
sourceimpl FromIterator<(u32, u32)> for EditGraph
impl FromIterator<(u32, u32)> for EditGraph
sourcefn from_iter<T: IntoIterator<Item = Edge>>(iter: T) -> Self
fn from_iter<T: IntoIterator<Item = Edge>>(iter: T) -> Self
sourceimpl Graph for EditGraph
impl Graph for EditGraph
sourcefn num_vertices(&self) -> usize
fn num_vertices(&self) -> usize
sourcefn adjacent(&self, u: &Vertex, v: &Vertex) -> bool
fn adjacent(&self, u: &Vertex, v: &Vertex) -> bool
u
and v
are connected by an edge.sourcefn vertices<'a>(&'a self) -> Box<dyn Iterator<Item = &'_ Vertex> + 'a>
fn vertices<'a>(&'a self) -> Box<dyn Iterator<Item = &'_ Vertex> + 'a>
sourcefn neighbours<'a>(
&'a self,
u: &Vertex
) -> Box<dyn Iterator<Item = &'_ Vertex> + 'a>
fn neighbours<'a>(
&'a self,
u: &Vertex
) -> Box<dyn Iterator<Item = &'_ Vertex> + 'a>
u
.sourcefn neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
fn neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
vertices
over vertices, returns all vertices of the graph
which are neighbours of those vertices but not part of vertices
themselves. Read moresourcefn closed_neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
fn closed_neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
vertices
over vertices, returns all vertices of the graph
which are neighbours of those vertices as well as all vertices contained in vertices
. Read moresourcefn r_neighbours(&self, u: &Vertex, r: usize) -> FxHashSet<Vertex>
fn r_neighbours(&self, u: &Vertex, r: usize) -> FxHashSet<Vertex>
r
to u
.sourcefn r_neighbourhood<'a, I>(&self, vertices: I, r: usize) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
fn r_neighbourhood<'a, I>(&self, vertices: I, r: usize) -> FxHashSet<Vertex>where
I: Iterator<Item = &'a Vertex>,
Vertex: 'a,
vertices
over vertices and a distance r
, returns all vertices of the graph
which are within distance at most r
to vertices contained in vertices
. Read moresourcefn subgraph<'a, M, I>(&self, vertices: I) -> Mwhere
M: MutableGraph,
I: Iterator<Item = &'a Vertex>,
fn subgraph<'a, M, I>(&self, vertices: I) -> Mwhere
M: MutableGraph,
I: Iterator<Item = &'a Vertex>,
vertices
.sourceimpl MutableGraph for EditGraph
impl MutableGraph for EditGraph
sourcefn with_capacity(n_guess: usize) -> Self
fn with_capacity(n_guess: usize) -> Self
sourcefn add_vertex(&mut self, u: &Vertex) -> bool
fn add_vertex(&mut self, u: &Vertex) -> bool
u
to the graph. Read moresourcefn add_edge(&mut self, u: &Vertex, v: &Vertex) -> bool
fn add_edge(&mut self, u: &Vertex, v: &Vertex) -> bool
uv
to the graph. Read moresourcefn remove_edge(&mut self, u: &Vertex, v: &Vertex) -> bool
fn remove_edge(&mut self, u: &Vertex, v: &Vertex) -> bool
uv
from the graph. Read moresourcefn remove_vertex(&mut self, u: &Vertex) -> bool
fn remove_vertex(&mut self, u: &Vertex) -> bool
u
from the graph. Read moresourcefn add_vertices(&mut self, vertices: impl Iterator<Item = Vertex>) -> u32
fn add_vertices(&mut self, vertices: impl Iterator<Item = Vertex>) -> u32
vertices
to the graph. Read moresourcefn add_edges(&mut self, edges: impl Iterator<Item = Edge>) -> u32
fn add_edges(&mut self, edges: impl Iterator<Item = Edge>) -> u32
edges
to the graph. Read moresourcefn remove_loops(&mut self) -> usize
fn remove_loops(&mut self) -> usize
sourcefn remove_isolates(&mut self) -> usize
fn remove_isolates(&mut self) -> usize
impl Eq for EditGraph
Auto Trait Implementations
impl RefUnwindSafe for EditGraph
impl Send for EditGraph
impl Sync for EditGraph
impl Unpin for EditGraph
impl UnwindSafe for EditGraph
Blanket Implementations
sourceimpl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
sourceimpl<G> EdgeIterable<G> for Gwhere
G: Graph,
impl<G> EdgeIterable<G> for Gwhere
G: Graph,
sourcefn edges(&self) -> EdgeIterator<'_, G>ⓘNotable traits for EdgeIterator<'a, G>impl<'a, G> Iterator for EdgeIterator<'a, G>where
G: Graph, type Item = (Vertex, Vertex);
fn edges(&self) -> EdgeIterator<'_, G>ⓘNotable traits for EdgeIterator<'a, G>impl<'a, G> Iterator for EdgeIterator<'a, G>where
G: Graph, type Item = (Vertex, Vertex);
G: Graph, type Item = (Vertex, Vertex);
sourceimpl<G> GraphAlgorithms for Gwhere
G: Graph,
impl<G> GraphAlgorithms for Gwhere
G: Graph,
sourcefn components(&self) -> Vec<HashSet<u32, BuildHasherDefault<FxHasher>>, Global>
fn components(&self) -> Vec<HashSet<u32, BuildHasherDefault<FxHasher>>, Global>
sourcefn degeneracy(
&self
) -> (u32, u32, Vec<u32, Global>, HashMap<u32, u32, BuildHasherDefault<FxHasher>>)
fn degeneracy(
&self
) -> (u32, u32, Vec<u32, Global>, HashMap<u32, u32, BuildHasherDefault<FxHasher>>)
sourcefn is_bipartite(&self) -> BipartiteWitness
fn is_bipartite(&self) -> BipartiteWitness
sourceimpl<G> MixedIterable<G> for Gwhere
G: Graph,
impl<G> MixedIterable<G> for Gwhere
G: Graph,
sourcefn vertices_and_edges(&self) -> MixedIterator<'_, G>ⓘNotable traits for MixedIterator<'a, G>impl<'a, G> Iterator for MixedIterator<'a, G>where
G: Graph, type Item = VertexOrEdge;
fn vertices_and_edges(&self) -> MixedIterator<'_, G>ⓘNotable traits for MixedIterator<'a, G>impl<'a, G> Iterator for MixedIterator<'a, G>where
G: Graph, type Item = VertexOrEdge;
G: Graph, type Item = VertexOrEdge;
sourceimpl<G> NeighIterable<G> for Gwhere
G: Graph,
impl<G> NeighIterable<G> for Gwhere
G: Graph,
sourcefn neighbourhoods(&self) -> NeighIterator<'_, G>ⓘNotable traits for NeighIterator<'a, G>impl<'a, G> Iterator for NeighIterator<'a, G>where
G: Graph, type Item = (Vertex, Box<dyn Iterator<Item = &'a Vertex> + 'a>);
fn neighbourhoods(&self) -> NeighIterator<'_, G>ⓘNotable traits for NeighIterator<'a, G>impl<'a, G> Iterator for NeighIterator<'a, G>where
G: Graph, type Item = (Vertex, Box<dyn Iterator<Item = &'a Vertex> + 'a>);
G: Graph, type Item = (Vertex, Box<dyn Iterator<Item = &'a Vertex> + 'a>);