Struct petgraph::graphmap::GraphMap

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() -> Self

Create a new GraphMap.

fn with_capacity(nodes: usize, edges: usize) -> Self

Create a new GraphMap with estimated capacity.

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, edge: E) -> bool

Add an edge connecting a and b to the graph.

Inserts nodes a and/or b if they aren't already part of the graph.

Return true if edge did not previously exist.

Example

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.

Example

use petgraph::GraphMap;

let mut g = GraphMap::new();
g.add_node(1);
g.add_node(2);
g.add_edge(1, 2, -1);

let edge = g.remove_edge(2, 1);
assert_eq!(edge, 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<'a>(&'a self) -> Nodes<'a, N>

Return an iterator over the nodes of the graph.

Iterator element type is N.

fn neighbors<'a>(&'a self, from: N) -> Neighbors<'a, 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<'a>(&'a self, from: N) -> Edges<'a, 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, &'a E).

fn edge_weight<'a>(&'a self, a: N, b: N) -> Option<&'a 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<'a>(&'a mut self, a: N, b: N) -> Option<&'a 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.

Trait Implementations

impl<N: Clone, E: Clone> Clone for GraphMap<N, E>

fn clone(&self) -> GraphMap<N, E>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Eq + Hash + Debug, E: Debug> Debug for GraphMap<N, E>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

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.

fn index_mut(&mut self, index: (N, N)) -> &mut E

The method for the indexing (Foo[Bar]) operation

impl<'a, N: 'a, E> NeighborIter<'a> for GraphMap<N, E> where N: 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: Clone, E> Graphlike for GraphMap<N, E>

type NodeId = N

impl<N, E> Visitable for GraphMap<N, E> where N: Copy + Ord + Hash

type Map = HashSet<N>

fn visit_map(&self) -> HashSet<N>

impl<N, E> GetAdjacencyMatrix for GraphMap<N, E> where N: Copy + Ord + Hash

The GraphMap keeps an adjacency matrix internally.

type AdjMatrix = ()

fn adjacency_matrix(&self)

fn is_adjacent(&self, _: &(), a: N, b: N) -> bool