Struct daggy::petgraph::GraphMap
[−]
[src]
pub struct GraphMap<N, E> {
// some fields omitted
}GraphMap<N, E> is an undirected graph, with generic node values N and edge weights E.
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.
The node type N must implement Copy and will be used as node identifier, duplicated
into several places in the data structure.
It must be suitable as a hash table key (implementing Eq + Hash).
The node type must also implement Ord so that the implementation can
order the pair (a, b) for an edge connecting any two nodes a and b.
GraphMap does not allow parallel edges, but self loops are allowed.
Methods
impl<N, E> GraphMap<N, E> where N: NodeTrait
fn new() -> GraphMap<N, E>
Create a new GraphMap.
fn with_capacity(nodes: usize, edges: usize) -> GraphMap<N, E>
Create a new GraphMap with estimated capacity.
fn capacity(&self) -> (usize, usize)
Return the current node and edge capacity of the graph.
fn from_edges<I>(iterable: I) -> GraphMap<N, E> where I: IntoIterator, I::Item: IntoWeightedEdge<E>, I::Item::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; let gr = GraphMap::<_, ()>::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).
use petgraph::GraphMap; let mut g = GraphMap::new(); g.add_edge(1, 2, -1); assert_eq!(g.node_count(), 2); assert_eq!(g.edge_count(), 1);
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.
use petgraph::GraphMap; let mut g = GraphMap::new(); g.add_edge(1, 2, -1); let edge_data = g.remove_edge(2, 1); 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, from: N) -> Neighbors<N>
Return an iterator over the nodes that are connected with from by edges.
If the node from does not exist in the graph, return an empty iterator.
Iterator element type is N.
fn edges(&self, from: N) -> Edges<N, E>
Return an iterator over the nodes that are connected with from by edges,
paired with the edge weight.
If the node from does not exist in the graph, return an empty iterator.
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>
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, E> Debug for GraphMap<N, E> where E: Debug, N: Eq + Hash + Debug
impl<N, E, Item> FromIterator<Item> for GraphMap<N, E> where Item: IntoWeightedEdge<E, NodeId=N>, N: NodeTrait
Create a new GraphMap from an iterable of edges.
fn from_iter<I>(iterable: I) -> GraphMap<N, E> where I: IntoIterator<Item=Item>
impl<N, E, Item> Extend<Item> for GraphMap<N, E> where Item: IntoWeightedEdge<E, NodeId=N>, N: NodeTrait
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>
impl<N, E> Index<(N, N)> for GraphMap<N, E> where N: NodeTrait
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 (Foo[Bar]) operation
impl<N, E> IndexMut<(N, N)> for GraphMap<N, E> where N: NodeTrait
Index GraphMap by node pairs to access edge weights.
impl<N, E> Default for GraphMap<N, E> where N: NodeTrait
Create a new empty GraphMap.
impl<'a, N, E> NeighborIter<'a> for GraphMap<N, E> where N: 'a + Copy + Ord + Hash
type Iter = Neighbors<'a, N>
fn neighbors(&'a self, n: N) -> Neighbors<'a, N>
Return an iterator that visits all neighbors of the node n.
impl<N, E> Graphlike for GraphMap<N, E> where N: Clone
type NodeId = N
impl<N, E> Visitable for GraphMap<N, E> where N: Copy + Ord + Hash
type Map = HashSet<N, RandomState>
fn visit_map(&self) -> HashSet<N, RandomState>
impl<N, E> Revisitable for GraphMap<N, E> where N: Copy + Ord + Hash
impl<N, E> GetAdjacencyMatrix for GraphMap<N, E> where N: Copy + Ord + Hash
The GraphMap keeps an adjacency matrix internally.
Derived Implementations
impl<N, E> Clone for GraphMap<N, E> where E: Clone, N: Clone
fn clone(&self) -> GraphMap<N, E>
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