Struct TreeBackedGraph

pub struct TreeBackedGraph { /* private fields */ }

A directed graph with balanced computational complexity.

	Complexity
add_vertex	$O(\log |V|)$
add_edge	$O(\log |V| + \log |E|)$
remove_edge	$O(\log |E|)$
remove_vertex	$O(\log |V| + |E’|)$, where $E’$ is the set of edges connecting to the vertex to remove.
vertex_size	$O(1)$
iter_vertices	amortized $O(1)$ and $O(\log |V|)$ in the worst cases.
contains_vertex	$O(\log |V|)$
edge_size	$O(1)$
iter_edges	amortized $O(1)$ and $O(\log |E|)$ in the worst cases.
contains_edge	$O(\log |E|)$
find_edge	$O(\log |E|)$
edges_connecting	returns in $O(\log |E|)$. amortized $O(1)$ and $O(\log |E|)$ in the worst cases on each call to .next.
in_edges	returns in $O(\log |E|)$. amortized $O(1)$ and $O(\log |E|)$ in the worst cases on each call to .next.
out_edges	returns in $O(\log |E|)$. amortized $O(1)$ and $O(\log |E|)$ in the worst cases on each call to .next.

Trait Implementations

impl Clone for TreeBackedGraph

fn clone(&self) -> TreeBackedGraph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for TreeBackedGraph

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

Formats the value using the given formatter.

impl DirectedOrNot for TreeBackedGraph

const DIRECTED_OR_NOT: bool = true

When the graph is directed, it is true; otherwise, it is false.

impl EdgeShrinkableGraph for TreeBackedGraph

fn remove_edge(&mut self, edge: &EdgeId) -> Option<Edge>

Remove an edge from the graph.

impl GrowableGraph for TreeBackedGraph

fn new() -> Self

Generate a new and empty graph.

fn add_vertex(&mut self) -> VertexId

Add a new vertex into the graph.

fn add_edge(&mut self, source: VertexId, sink: VertexId) -> EdgeId

Add a new edge from source to sink for directed graphs or between them for undirected graphs.

impl QueryableGraph for TreeBackedGraph

fn vertex_size(&self) -> usize

Number of vertices in the graph.

fn iter_vertices(&self) -> Box<dyn Iterator<Item = VertexId> + '_>

Iteration over all vertices in the graph.

fn contains_vertex(&self, v: &VertexId) -> bool

Whether a vertex is in the graph or not.

fn edge_size(&self) -> usize

Number of edges in the graph.

fn iter_edges(&self) -> Box<dyn Iterator<Item = Edge> + '_>

Iteration over all edges in the graph.

fn contains_edge(&self, e: &EdgeId) -> bool

Whether an edge is in the graph or not.

fn find_edge(&self, e: &EdgeId) -> Option<Edge>

Returns information about a specified edge in the graph.

fn in_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_>

Iteration over all edges going into the vertex v.

fn out_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_>

Iteration over all edges going out of v.

fn edges_connecting<'a, 'b>( &'a self, source: &'b VertexId, sink: &'b VertexId, ) -> Box<dyn Iterator<Item = Edge> + 'a>

Iteration over all edges between two vertices in undirected graphs or those from source to sink in directed graphs.

fn debug(&self) -> Box<dyn Debug + '_>

where Self: Sized,

Returns something can inspect into the graph.

fn debug_with_indent( &self, init_indent: usize, indent_step: usize, ) -> Box<dyn Debug + '_>

where Self: Sized,

Returns something can inspect into the graph, with customzied indentation.

impl VertexShrinkableGraph for TreeBackedGraph

fn remove_vertex( &mut self, vertex: &VertexId, ) -> Box<dyn Iterator<Item = Edge> + 'static>

Removes a vertex from the graph and all edges connected to this vertex.