Struct petgraph::graphmap::GraphMap
[−]
[src]
pub struct GraphMap<N, E, Ty> { /* fields omitted */ }
GraphMap<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.
GraphMap
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 aliases UnGraphMap
and DiGraphMap
for convenience.
GraphMap
does not allow parallel edges, but self loops are allowed.
Depends on crate feature graphmap
(default).
Methods
impl<N, E, Ty> GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
fn new() -> Self
Create a new GraphMap
fn with_capacity(nodes: usize, edges: usize) -> Self
Create a new GraphMap
with estimated capacity.
fn capacity(&self) -> (usize, usize)
Return the current node and edge capacity of the graph.
fn is_directed(&self) -> bool
Whether the graph has directed edges.
fn from_edges<I>(iterable: I) -> Self where
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
Create a new GraphMap
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.
use petgraph::graphmap::UnGraphMap; // Create a new undirected GraphMap. // Use a type hint to have `()` be the edge weight type. let gr = UnGraphMap::<_, ()>::from_edges(&[ (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), ]);
fn node_count(&self) -> usize
Return the number of nodes in the graph.
fn edge_count(&self) -> usize
Return the number of edges in the graph.
fn clear(&mut self)
Remove all nodes and edges
fn add_node(&mut self, n: N) -> N
Add node n
to the graph.
fn remove_node(&mut self, n: N) -> bool
Return true
if node n
was removed.
fn contains_node(&self, n: N) -> bool
Return true
if the node is contained in the graph.
fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E>
Add an edge connecting a
and b
to the graph, with associated
data weight
.
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)
.
// Create a GraphMap with directed edges, and add one edge to it use petgraph::graphmap::DiGraphMap; let mut g = DiGraphMap::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"));
fn remove_edge(&mut self, a: N, b: N) -> Option<E>
Remove edge from a
to b
from the graph and return the edge weight.
Return None
if the edge didn't exist.
// Create a GraphMap with undirected edges, and add and remove an edge. use petgraph::graphmap::UnGraphMap; let mut g = UnGraphMap::new(); g.add_edge("x", "y", -1); let edge_data = g.remove_edge("y", "x"); assert_eq!(edge_data, Some(-1)); assert_eq!(g.edge_count(), 0);
fn contains_edge(&self, a: N, b: N) -> bool
Return true
if the edge connecting a
with b
is contained in the graph.
fn nodes(&self) -> Nodes<N>
Return an iterator over the nodes of the graph.
Iterator element type is N
.
fn neighbors(&self, a: N) -> Neighbors<N, Ty>
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
.
fn neighbors_directed(&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
.
fn edges(&self, from: N) -> Edges<N, E, Ty>
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)
.
fn edge_weight(&self, a: N, b: N) -> Option<&E>
Return a reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E>
Return a mutable reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
fn all_edges(&self) -> AllEdges<N, E, Ty>
Return an iterator over all edges of the graph with their weight in arbitrary order.
Iterator element type is (N, N, &E)
fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty>
Return an iterator over all edges of the graph in arbitrary order, with a mutable reference to their weight.
Iterator element type is (N, N, &mut E)
fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix> where
Ix: IndexType,
Ix: IndexType,
Return a Graph
that corresponds to this GraphMap
.
Note: node and edge indices in the Graph
have nothing in common
with the GraphMap
s node weights N
. The node weights N
are
used as node weights in the resulting Graph
, too.
Trait Implementations
impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty> where
N: Copy + Ord + Hash,
Ty: EdgeType,
[src]
N: Copy + Ord + Hash,
Ty: EdgeType,
type Neighbors = Neighbors<'a, N, Ty>
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors
Return an iterator of the neighbors of node a
.
impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty> where
N: Copy + Ord + Hash,
Ty: EdgeType,
[src]
N: Copy + Ord + Hash,
Ty: EdgeType,
type NeighborsDirected = NeighborsDirected<'a, N, Ty>
fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected
impl<N, E, Ty> Data for GraphMap<N, E, Ty> where
N: Copy + PartialEq,
Ty: EdgeType,
[src]
N: Copy + PartialEq,
Ty: EdgeType,
type NodeWeight = N
type EdgeWeight = E
impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty> where
N: Copy + PartialEq,
[src]
N: Copy + PartialEq,
impl<N, E, Ty> Visitable for GraphMap<N, E, Ty> where
N: Copy + Ord + Hash,
Ty: EdgeType,
[src]
N: Copy + Ord + Hash,
Ty: EdgeType,
type Map = HashSet<N>
The associated map type
fn visit_map(&self) -> HashSet<N>
Create a new visitor map
fn reset_map(&self, map: &mut Self::Map)
Reset the visitor map (and resize to new size of graph if needed)
impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty> where
N: Copy + Ord + Hash,
Ty: EdgeType,
[src]
N: Copy + Ord + Hash,
Ty: EdgeType,
The GraphMap
keeps an adjacency matrix internally.
type AdjMatrix = ()
The associated adjacency matrix type
fn adjacency_matrix(&self)
Create the adjacency matrix
fn is_adjacent(&self, _: &(), a: N, b: N) -> bool
Return true if there is an edge from a
to b
, false otherwise. Read more
impl<N, E, Ty> Build for GraphMap<N, E, Ty> where
Ty: EdgeType,
N: NodeTrait,
[src]
Ty: EdgeType,
N: NodeTrait,
fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId
fn add_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) -> Option<Self::EdgeId>
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) -> Option<Self::EdgeId>
Add a new edge. If parallel edges (duplicate) are not allowed and the edge already exists, return None
. Read more
fn update_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) -> Self::EdgeId
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) -> Self::EdgeId
Add or update the edge from a
to b
. Return the id of the affected edge. Read more
impl<N, E, Ty> Create for GraphMap<N, E, Ty> where
Ty: EdgeType,
N: NodeTrait,
[src]
Ty: EdgeType,
N: NodeTrait,
fn with_capacity(nodes: usize, edges: usize) -> Self
impl<N, E, Ty> FromElements for GraphMap<N, E, Ty> where
Ty: EdgeType,
N: NodeTrait,
[src]
Ty: EdgeType,
N: NodeTrait,
fn from_elements<I>(iterable: I) -> Self where
Self: Sized,
I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
Self: Sized,
I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
impl<N: Clone, E: Clone, Ty: Clone> Clone for GraphMap<N, E, Ty>
[src]
fn clone(&self) -> GraphMap<N, E, Ty>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<N: Eq + Hash + Debug, E: Debug, Ty: EdgeType> Debug for GraphMap<N, E, Ty>
[src]
impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<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 GraphMap
from an iterable of edges.
fn from_iter<I>(iterable: I) -> Self where
I: IntoIterator<Item = Item>,
I: IntoIterator<Item = Item>,
Creates a value from an iterator. Read more
impl<N, E, Ty, Item> Extend<Item> for GraphMap<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>,
I: IntoIterator<Item = Item>,
Extends a collection with the contents of an iterator. Read more
impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
type EdgeRef = (N, N, &'a E)
type EdgeReferences = AllEdges<'a, N, E, Ty>
fn edge_references(self) -> Self::EdgeReferences
impl<'a, N: 'a, E: 'a, Ty> IntoEdges for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
Index GraphMap
by node pairs to access edge weights.
type Output = E
The returned type after indexing
fn index(&self, index: (N, N)) -> &E
The method for the indexing (container[index]
) operation
impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
Index GraphMap
by node pairs to access edge weights.
fn index_mut(&mut self, index: (N, N)) -> &mut E
The method for the mutable indexing (container[index]
) operation
impl<N, E, Ty> Default for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
Create a new empty GraphMap
.
impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>
fn node_identifiers(self) -> Self::NodeIdentifiers
impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
fn node_count(&self) -> usize
impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
type NodeRef = (N, &'a N)
type NodeReferences = NodeReferences<'a, N, E, Ty>
fn node_references(self) -> Self::NodeReferences
impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,
fn node_bound(&self) -> usize
Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more
fn to_index(&self, ix: Self::NodeId) -> usize
Convert a
to an integer index.
fn from_index(&self, ix: usize) -> Self::NodeId
Convert i
to a node index
impl<N, E, Ty> NodeCompactIndexable for GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
[src]
N: NodeTrait,
Ty: EdgeType,