Struct EditGraph

pub struct EditGraph { /* private fields */ }

An implementation of the MutableGraph trait with additional convenient editing and generating functions.

Implementations

impl EditGraph

pub fn path(n: u32) -> EditGraph

Generates a path on n vertices.

pub fn cycle(n: u32) -> EditGraph

Generates a cycle on n vertices.

pub fn matching(n: u32) -> EditGraph

Generates a matching on 2n vertices.

pub fn star(n: u32) -> EditGraph

Generates a star with n leaves, so n+1 vertices total.

pub fn clique(n: u32) -> EditGraph

Generates a complete graph (clique) on n vertices.

pub fn independent(n: u32) -> EditGraph

Generates an empty graph (independent set) on n vertices.

pub fn biclique(s: u32, t: u32) -> EditGraph

Generates a complete bipartite graph (biclique) on s+t vertices.

pub fn complete_kpartite<'a, I>(sizes: I) -> EditGraph

where I: IntoIterator<Item = &'a u32>,

Generates a complete k-partite graph.

Arguments

• sizes - The sizes of each partite set as a sequence of integers.

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.

pub fn disj_unions<'a, I, G>(it: I) -> EditGraph

where I: Iterator<Item = &'a G>, G: Graph + 'a,

Computes the disjoint unions of all graphs in the iterator it.

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.

pub fn contract<'a, I>(&mut self, vertices: I) -> Vertex

where 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.

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.

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.

impl EditGraph

I/O operations for EditGraph defined in crate::io

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>>());
}

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

impl Clone for EditGraph

fn clone(&self) -> EditGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for EditGraph

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

Formats the value using the given formatter.

impl FromIterator<(u32, u32)> for EditGraph

fn from_iter<T: IntoIterator<Item = Edge>>(iter: T) -> Self

Creates a value from an iterator.

impl Graph for EditGraph

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 adjacent(&self, u: &Vertex, v: &Vertex) -> bool

Returns whether vertices u and v are connected by an edge.

fn degree(&self, u: &Vertex) -> u32

Returns the number of edges incident to u in the graph.

fn contains(&self, u: &Vertex) -> bool

Returns whether the vertex u is contained in the graph.

fn vertices<'a>(&'a self) -> Box<dyn Iterator<Item = &Vertex> + 'a>

Returns an iterator to this graph’s vertices.

fn neighbours<'a>( &'a self, u: &Vertex, ) -> Box<dyn Iterator<Item = &Vertex> + 'a>

Returns an iterator over the neighbours of u.

fn degrees(&self) -> VertexMap<u32>

Returns the degrees of all vertices in the graph as a map.

fn len(&self) -> usize

Alias for Graph::num_vertices()

fn is_empty(&self) -> bool

Returns true if the graph contains no vertices

fn neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>

where I: Iterator<Item = &'a Vertex>, Vertex: 'a,

Given an iterator vertices over vertices, returns all vertices of the graph which are neighbours of those vertices but not part of vertices themselves.

fn closed_neighbourhood<'a, I>(&self, vertices: I) -> FxHashSet<Vertex>

where I: Iterator<Item = &'a Vertex>, Vertex: 'a,

Given an iterator vertices over vertices, returns all vertices of the graph which are neighbours of those vertices as well as all vertices contained in vertices.

fn r_neighbours(&self, u: &Vertex, r: usize) -> FxHashSet<Vertex>

Returns all vertices which lie within distance at most r to u.

fn r_neighbourhood<'a, I>(&self, vertices: I, r: usize) -> FxHashSet<Vertex>

where I: Iterator<Item = &'a Vertex>, Vertex: 'a,

Given an iterator 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.

fn subgraph<'a, M, I>(&self, vertices: I) -> M

where M: MutableGraph, I: Iterator<Item = &'a Vertex>,

Returns the subgraph induced by the vertices contained in vertices.

impl MutableGraph for EditGraph

fn new() -> EditGraph

Creates an emtpy mutable graph.

fn with_capacity(n_guess: usize) -> Self

Creates a mutable graph with a hint on how many vertices it will probably contain.

fn add_vertex(&mut self, u: &Vertex) -> bool

Adds the vertex u to the graph.

fn add_edge(&mut self, u: &Vertex, v: &Vertex) -> bool

Adds the edge uv to the graph.

fn remove_edge(&mut self, u: &Vertex, v: &Vertex) -> bool

Removes the edge uv from the graph.

fn remove_vertex(&mut self, u: &Vertex) -> bool

Removes the vertex u from the graph.

fn add_vertices(&mut self, vertices: impl Iterator<Item = Vertex>) -> u32

Adds a collection of vertices to the graph.

fn add_edges(&mut self, edges: impl Iterator<Item = Edge>) -> u32

Adds a collection of edges to the graph.

fn remove_loops(&mut self) -> usize

Removes all loops from the graph.

fn remove_isolates(&mut self) -> usize

Removes all isolate vertices, that is, vertices without any neighbours.

impl PartialEq for EditGraph

fn eq(&self, other: &Self) -> 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 Eq for EditGraph