Struct prepona::storage::AdjMap [−][src]
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.
- |Esrc->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
orUndirected
.
Implementations
impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> AdjMap<W, E, Dir>
[src]
impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> AdjMap<W, E, Dir>
[src]pub fn init() -> Self
[src]
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 usesundirected
default edges
. -
DiMap
: An adjacency map that usesdirected
default edges
. -
FlowMap
: An adjacency map that usesundirected
flow edges
. -
DiFlowMap
: An adjacency map that usesdirected
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>
[src]
impl<W: Copy, E: Edge<W> + Copy, Dir: EdgeDir> GraphStorage<W, E, Dir> for AdjMap<W, E, Dir>
[src]fn add_vertex(&mut self) -> usize
[src]
fn remove_vertex_unchecked(&mut self, vertex_id: usize)
[src]
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
[src]
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
)
[src]
&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
ordst_id
is not in range 0..|V|. - If there is no edge with id:
edge_id
fromsrc_id
todst_id
.
fn remove_edge_unchecked(
&mut self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> E
[src]
&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 withedge_id
does not exist in the graph.
Complexity
O(|Esrc->dst|)
Panics
- If
src_id
ordst_id
is not in range 0..|V|. - If there is no edge with id:
edge_id
fromsrc_id
todst_id
.
fn vertex_count(&self) -> usize
[src]
fn edge_count(&self) -> usize
[src]
fn vertices(&self) -> Vec<usize>
[src]
fn edges_from_unchecked(&self, src_id: usize) -> Vec<(usize, &E)>
[src]
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
[src]
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
[src]
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<()>
[src]
fn add_edge(&mut self, src_id: usize, dst_id: usize, edge: E) -> Result<usize>
[src]
fn update_edge(
&mut self,
src_id: usize,
dst_id: usize,
edge_id: usize,
edge: E
) -> Result<()>
[src]
&mut self,
src_id: usize,
dst_id: usize,
edge_id: usize,
edge: E
) -> Result<()>
fn remove_edge(
&mut self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> Result<E>
[src]
&mut self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> Result<E>
fn edges_between(&self, src_id: usize, dst_id: usize) -> Result<Vec<&E>>
[src]
fn edges_between_unchecked(&self, src_id: usize, dst_id: usize) -> Vec<&E>
[src]
fn edge_between(
&self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> Result<&E>
[src]
&self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> Result<&E>
fn edge_between_unchecked(
&self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> &E
[src]
&self,
src_id: usize,
dst_id: usize,
edge_id: usize
) -> &E
fn edge(&self, edge_id: usize) -> Result<&E>
[src]
fn edge_unchecked(&self, edge_id: usize) -> &E
[src]
fn has_any_edge(&self, src_id: usize, dst_id: usize) -> Result<bool>
[src]
fn has_any_edge_unchecked(&self, src_id: usize, dst_id: usize) -> bool
[src]
fn edges(&self) -> Vec<(usize, usize, &E)>
[src]
fn as_directed_edges(&self) -> Vec<(usize, usize, &E)>
[src]
fn edges_from(&self, src_id: usize) -> Result<Vec<(usize, &E)>>
[src]
fn neighbors(&self, src_id: usize) -> Result<Vec<usize>>
[src]
fn neighbors_unchecked(&self, src_id: usize) -> Vec<usize>
[src]
fn is_directed(&self) -> bool
[src]
fn is_undirected(&self) -> bool
[src]
Auto Trait Implementations
impl<W, E, Dir> RefUnwindSafe for AdjMap<W, E, Dir> where
Dir: RefUnwindSafe,
E: RefUnwindSafe,
W: RefUnwindSafe,
impl<W, E, Dir> RefUnwindSafe for AdjMap<W, E, Dir> where
Dir: RefUnwindSafe,
E: RefUnwindSafe,
W: RefUnwindSafe,
impl<W, E, Dir> UnwindSafe for AdjMap<W, E, Dir> where
Dir: UnwindSafe,
E: UnwindSafe,
W: UnwindSafe,
impl<W, E, Dir> UnwindSafe for AdjMap<W, E, Dir> where
Dir: UnwindSafe,
E: UnwindSafe,
W: UnwindSafe,