[−][src]Struct safe_graph::graph::Graph
Graph<N, E, Ty>
is a graph datastructure using an associative array
of its node weights N
.
It uses an combined adjacency list and sparse adjacency matrix representation, using O(|V| + |E|) space, and allows testing for edge existance in constant time.
Graph
is parameterized over:
- Associated data
N
for nodes andE
for edges, called weights. - The node weight
N
must implementCopy
and will be used as node identifier, duplicated into several places in the data structure. It must be suitable as a hash table key (implementingEq + Hash
). The node type must also implementOrd
so that the implementation can order the pair (a
,b
) for an edge connecting any two nodesa
andb
. E
can be of arbitrary type.- Edge type
Ty
that determines whether the graph edges are directed or undirected.
You can use the type alias UndirectedGraph
for convenience.
Graph
does not allow parallel edges, but self loops are allowed.
Methods
impl<N, E, Ty> Graph<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
pub fn new() -> Self
[src]
Create a new Graph
instance.
Examples
use safe_graph::Graph; let graph: Graph<i32, f32> = Graph::new();
pub fn with_capacity(nodes: usize, edges: usize) -> Self
[src]
Create a new Graph
with estimated capacity.
pub fn capacity(&self) -> (usize, usize)
[src]
Return the current node and edge capacity of the graph.
pub fn edge_key(a: N, b: N) -> (N, N)
[src]
Use their natural order to map the node pair (a, b) to a canonical edge id.
pub fn is_directed(&self) -> bool
[src]
Whether the graph has directed edges.
pub fn from_edges<I>(iterable: I) -> Self where
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
[src]
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
Create a new Graph
from an iterable of edges.
Node values are taken directly from the list.
Edge weights E
may either be specified in the list,
or they are filled with default values.
Nodes are inserted automatically to match the edges.
Examples
use safe_graph::Graph; // Create a new directed Graph. // Use a type hint to have `()` be the edge weight type. let gr = Graph::<_, ()>::from_edges(&[ (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), ]);
pub fn node_count(&self) -> usize
[src]
Return the number of nodes in the graph.
pub fn edge_count(&self) -> usize
[src]
Return the number of edges in the graph.
pub fn clear(&mut self)
[src]
Remove all nodes and edges
pub fn add_node(&mut self, n: N) -> N
[src]
Add node n
to the graph.
pub fn contains_node(&self, n: N) -> bool
[src]
Return true
if the node is contained in the graph.
pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E>
[src]
Add an edge connecting a
and b
to the graph, with associated
data weight
. For a directed graph, the edge is directed from a
to b
.
Inserts nodes a
and/or b
if they aren't already part of the graph.
Return None
if the edge did not previously exist, otherwise,
the associated data is updated and the old value is returned
as Some(old_weight)
.
Examples
// Create a Graph with directed edges, and add one edge to it use safe_graph::Graph; let mut g: Graph<_, _> = Graph::new(); g.add_edge("x", "y", -1); assert_eq!(g.node_count(), 2); assert_eq!(g.edge_count(), 1); assert!(g.contains_edge("x", "y")); assert!(!g.contains_edge("y", "x"));
pub fn contains_edge(&self, a: N, b: N) -> bool
[src]
Return true
if the edge connecting a
with b
is contained in the graph.
ⓘImportant traits for Nodes<'a, N>pub fn nodes(&self) -> Nodes<N>
[src]
Return an iterator over the nodes of the graph.
Iterator element type is N
.
pub fn neighbors(&self, a: N) -> Neighbors<N, Ty>
[src]
Return an iterator of all nodes with an edge starting from a
.
Directed
: Outgoing edges froma
.Undirected
: All edges from or toa
.
Produces an empty iterator if the node doesn't exist.
Iterator element type is N
.
pub fn neighbors_directed(
&self,
a: N,
dir: Direction
) -> NeighborsDirected<N, Ty>
[src]
&self,
a: N,
dir: Direction
) -> NeighborsDirected<N, Ty>
Return an iterator of all neighbors that have an edge between them and
a
, in the specified direction.
If the graph's edges are undirected, this is equivalent to .neighbors(a).
Directed
,Outgoing
: All edges froma
.Directed
,Incoming
: All edges toa
.Undirected
: All edges from or toa
.
Produces an empty iterator if the node doesn't exist.
Iterator element type is N
.
ⓘImportant traits for Edges<'a, N, E, Ty>pub fn edges(&self, from: N) -> Edges<N, E, Ty>
[src]
Return an iterator of target nodes with an edge starting from a
,
paired with their respective edge weights.
Directed
: Outgoing edges froma
.Undirected
: All edges from or toa
.
Produces an empty iterator if the node doesn't exist.
Iterator element type is (N, &E)
.
pub fn edge_weight(&self, a: N, b: N) -> Option<&E>
[src]
Return a reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E>
[src]
Return a mutable reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
ⓘImportant traits for AllEdges<'a, N, E, Ty>pub fn all_edges(&self) -> AllEdges<N, E, Ty>
[src]
Return an iterator over all edges of the graph with their weight in arbitrary order.
Iterator element type is (N, N, &E)
Trait Implementations
impl<N: Clone, E: Clone, Ty: Clone> Clone for Graph<N, E, Ty>
[src]
fn clone(&self) -> Graph<N, E, Ty>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<N, E, Ty, Item> Extend<Item> for Graph<N, E, Ty> where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
[src]
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
Extend the graph from an iterable of edges.
Nodes are inserted automatically to match the edges.
fn extend<I>(&mut self, iterable: I) where
I: IntoIterator<Item = Item>,
[src]
I: IntoIterator<Item = Item>,
impl<N, E, Ty> Default for Graph<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
Create a new empty Graph
.
impl<N: Eq + Hash + Debug, E: Debug, Ty: EdgeType> Debug for Graph<N, E, Ty>
[src]
impl<N, E, Ty, Item> FromIterator<Item> for Graph<N, E, Ty> where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
[src]
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
Create a new Graph
from an iterable of edges.
fn from_iter<I>(iterable: I) -> Self where
I: IntoIterator<Item = Item>,
[src]
I: IntoIterator<Item = Item>,
Auto Trait Implementations
impl<N, E, Ty> Send for Graph<N, E, Ty> where
E: Send,
N: Send,
Ty: Send,
E: Send,
N: Send,
Ty: Send,
impl<N, E, Ty> Sync for Graph<N, E, Ty> where
E: Sync,
N: Sync,
Ty: Sync,
E: Sync,
N: Sync,
Ty: Sync,
Blanket Implementations
impl<T, U> Into for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
impl<T> From for T
[src]
impl<T, U> TryFrom for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = !
try_from
)The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T> Borrow for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> TryInto for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
try_from
)The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,