Struct DTFGraph 

pub struct DTFGraph { /* private fields */ }

The augmentation data structure.

Implementations

impl DTFGraph

pub fn get_depth(&self) -> usize

Returns the depth of augmentation.

pub fn to_undirected<G>(&self) -> G

where G: MutableGraph,

pub fn layer(&mut self, depth: usize) -> DTFLayer<'_>

pub fn num_arcs_at_depth(&self, depth: usize) -> usize

pub fn add_vertex(&mut self, u: Vertex)

pub fn orient_deep<G>(graph: &G, depth: usize) -> DTFGraph

where G: Graph,

pub fn edge_subgraph<I>(&self, it: I) -> DTFGraph

where I: Iterator<Item = (Vertex, Vertex)>,

pub fn orient<G>(graph: &G) -> DTFGraph

where G: Graph,

pub fn add_arc(&mut self, u: &Vertex, v: &Vertex, depth: usize)

pub fn has_arc_at(&self, u: &Vertex, v: &Vertex, depth: usize) -> bool

pub fn get_arc_depth(&self, u: &Vertex, v: &Vertex) -> Option<u32>

pub fn arcs(&self) -> DTFArcIterator<'_>

pub fn arcs_at(&self, depth: usize) -> DTFArcIterator<'_>

pub fn in_neighbourhoods_iter(&self) -> DTFNIterator<'_>

pub fn in_neighbourhoods_iter_at(&self, depth: usize) -> DTFNIterator<'_>

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

pub fn in_neighbours_with_weights(&self, u: &Vertex) -> FxHashMap<Vertex, u32>

pub fn small_distance(&self, u: &Vertex, v: &Vertex) -> Option<u32>

Returns the distance between the vertices u and v if it it smaller than the depth of the augmentation. Otherwise returns None.

pub fn augment(&mut self, depth: usize, frat_depth: usize)

Increases the depth of the augmentation.

Arguments

• depth - The target depth of the augmentation
• frat_depth - An optimisation parameter. Larger values increase computation time, recommended values are 2 or 1.

pub fn domset(&mut self, radius: u32) -> VertexSet

Computes an approximate $r$-dominating set of the underlying graph, where $r$ is the provided radius.

Note that if radius is larger than the current augmentation depth then graph is augmented further until the depth matches the radius.

The approximation ratio is a function of the graph’s ‘sparseness’. See [Dvořák13] and [Reidl16] for the underlying theory and [Brown20] for the details of this specific version of the algorithm.

[Dvořák13] Dvořák, Z. (2013). Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics, 34(5), 833-840.

[Brown20] Brown, C.T., Moritz, D., O’Brien, M.P., Reidl, F., Reiter, T. and Sullivan, B.D., 2020. Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity. Genome biology, 21(1), pp.1-16.

[Reidl16] Reidl, F. (2016). Structural sparseness and complex networks (No. RWTH-2015-07564). Fachgruppe Informatik.

Trait Implementations

impl Digraph for DTFGraph

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

Returns whether the arc uv exists in the digraph.

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

Returns the number of arcs which point to u in the digraph.

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

Returns the number of arcs which point away from u in the digraph.

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

Returns an iterator over the out-neighbours of u.

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

Returns an iterator over the in-neighbours of u.

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

Returns the in-degrees of all vertices in the digraph as a map.

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

Returns the out-degrees of all vertices in the digraph as a map.

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

Returns the set of all in- and out-neighbours of u as an iterator.

impl Graph for DTFGraph

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

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

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

Returns an iterator over the neighbours of u.

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

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

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.