Struct prepona::storage::AdjMap

pub struct AdjMap<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir = UndirectedEdge> { /* fields omitted */ }

AdjMap is a two-layer hash map in the form of: (source id) -> (destination id) -> (list of edges from source to destination).

Note

From now on

• |V|: Means number of vertices that are stored in the storage.
• |E_src->dst|: Means number of edges from source to destination.
• |E|: Means number of edges stored in the storage.

Space complexity

Space complexity of AdjMap depends on wether Dir is Directed or Undirected.

• Directed: For directed graphs AdjMap stores |V| + |E| elements.
• Undirected: For undirected graphs AdjMap stores each edge twice so it stores |V| + 2*|E| elements.

Generic Parameters

• W: Weight type associated with edges.
• E: Edge type that graph uses.
• Dir: Direction of edges: Directed or Undirected.

Implementations

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> AdjMap<W, E, Dir>

pub fn init() -> Self

Initializes an empty adjacency map.

AdjMap defines multiple types with different combination of values for generic parameters. These types are:

• Map: An adjacency map that uses undirected default edges.

• DiMap: An adjacency map that uses directed default edges.

• FlowMap: An adjacency map that uses undirected flow edges.

• DiFlowMap: An adjacency map that uses directed flow edges.

Returns

An empty AdjMap.

Examples

use prepona::prelude::*;
use prepona::storage::{Map, DiMap};

// To store an undirected graph with usize weights
let map = Map::<usize>::init();

// To store a directed graph with usize weights
let di_map = DiMap::<usize>::init();

Trait Implementations

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> GraphStorage<W, E, Dir> for AdjMap<W, E, Dir>

fn add_vertex(&mut self) -> usize

Adds a vertex to the graph.

Returns

Unique id of the newly added vertex.

Complexity

O(|1|)

fn remove_vertex_unchecked(&mut self, vertex_id: usize)

Removes the vertex with id: vertex_id from graph.

Arguments

vertex_id: Id of the vertex to be removed.

Complexity

O(|V|)

fn add_edge_unchecked(&mut self, src_id: usize, dst_id: usize, edge: E) -> usize

Adds edge from vertex with id src_id: to vertex with id: dst_id.

Arguments

• src_id: Id of the source vertex.
• dst_id: Id of the destination vertex.
• edge: Edge to be added from source to destination.

Returns

Unique id of the newly added edge.

Complexity

O(1)

Panics

If src_id or dst_id is not in 0..|V| range.

fn update_edge_unchecked(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize,
    edge: E
)

Replaces the edge with id: edge_id with edge.

Arguments

• src_id: Id of source vertex.
• dst_id: Id of destination vertex.
• edge_id: Id of the to be updated edge.
• edge: New edge to replace the old one.

Complexity

O(|E|)

Panics

• If src_id or dst_id is not in range 0..|V|.
• If there is no edge with id: edge_id from src_id to dst_id.

fn remove_edge_unchecked(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> E

Removes the edge with id: edge_id.

Arguments

• src_id: Id of source vertex.
• dst_id: Id of destination vertex.
• edge_id: Id of edge to be removed.

Returns

• Some: Containing the removed edge.
• None: If edge with edge_id does not exist in the graph.

Complexity

O(|E_src->dst|)

Panics

• If src_id or dst_id is not in range 0..|V|.
• If there is no edge with id: edge_id from src_id to dst_id.

fn vertex_count(&self) -> usize

Returns

Number of vertices in the graph.

Complexity

O(1)

fn edge_count(&self) -> usize

Returns

Number of edges in the graph.

Complexity:

O(1)

fn vertices(&self) -> Vec<usize>

Returns

Id of vertices that are present in the graph.

Complexity

O(|V|)

fn edges_from_unchecked(&self, src_id: usize) -> Vec<(usize, &E)>

Arguments

src_id: Id of the source vertex.

Returns

• All edges from the source vertex in the format of: (dst_id, edge)

Complexity

O(|E|)

Panics

If src_id is not in range 0..|V|.

fn contains_vertex(&self, vertex_id: usize) -> bool

Arguments

vertex_id: Id of the vertex to search for its existence in the storage.

Returns

• true: If storage contains the vertex with id: vertex_id.
• false: Otherwise.

fn contains_edge(&self, edge_id: usize) -> bool

Arguments

edge_id: Id of the edge to search for its existence in the storage.

Returns

• true: If storage contains the edge with id: edge_id.
• false: Otherwise.

fn remove_vertex(&mut self, vertex_id: usize) -> Result<()>

Removes the vertex with id: vertex_id from storage.

fn add_edge(&mut self, src_id: usize, dst_id: usize, edge: E) -> Result<usize>

Adds edge from vertex with id src_id: to vertex with id: dst_id.

fn update_edge(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize,
    edge: E
) -> Result<()>

Replaces the edge with id: edge_id with edge.

fn remove_edge(
    &mut self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> Result<E>

Removes the edge with id: edge_id.

fn edges_between(&self, src_id: usize, dst_id: usize) -> Result<Vec<&E>>

Arguments

fn edges_between_unchecked(&self, src_id: usize, dst_id: usize) -> Vec<&E>

Arguments

fn edge_between(
    &self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> Result<&E>

Arguments

fn edge_between_unchecked(
    &self,
    src_id: usize,
    dst_id: usize,
    edge_id: usize
) -> &E

Arguments

fn edge(&self, edge_id: usize) -> Result<&E>

Note:

fn edge_unchecked(&self, edge_id: usize) -> &E

Note:

fn has_any_edge(&self, src_id: usize, dst_id: usize) -> Result<bool>

Arguments

fn has_any_edge_unchecked(&self, src_id: usize, dst_id: usize) -> bool

Arguments

fn edges(&self) -> Vec<(usize, usize, &E)>

Returns

fn as_directed_edges(&self) -> Vec<(usize, usize, &E)>

Difference between this function and edges is that this function treats each edge as a directed edge. For example consider storage: a — b If you call edges on this storage, you will get: (a, b, edge). But if you call as_directed_edges, you will get two elements: (a, b, edge) and (b, a, edge). It’s specifically useful in algorithms that are for directed graphs but can also be applied to undirected graphs if we treat the edges as directed. One example is BellmanFord algorithm.

fn edges_from(&self, src_id: usize) -> Result<Vec<(usize, &E)>>

Arguments

fn neighbors(&self, src_id: usize) -> Result<Vec<usize>>

Arguments:

fn neighbors_unchecked(&self, src_id: usize) -> Vec<usize>

Arguments:

fn is_directed(&self) -> bool

Returns

fn is_undirected(&self) -> bool

Returns

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> Index<(usize, usize)> for AdjMap<W, E, Dir>

type Output = Vec<E>

The returned type after indexing.

fn index(&self, (src_id, dst_id): (usize, usize)) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> Index<usize> for AdjMap<W, E, Dir>

type Output = HashMap<usize, Vec<E>>

The returned type after indexing.

fn index(&self, src_id: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> IndexMut<(usize, usize)> for AdjMap<W, E, Dir>

fn index_mut(&mut self, (src_id, dst_id): (usize, usize)) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> IndexMut<usize> for AdjMap<W, E, Dir>

fn index_mut(&mut self, src_id: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.