Struct petgraph::graphmap::GraphMap

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.

The edge type Ty can be Directed or Undirected.

You can use the type aliases UnGraphMap and DiGraphMap for convenience.

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, Ty> GraphMap<N, E, Ty> where 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>

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, from: N) -> Neighbors<N, Ty>

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 neighbors_directed(&self, a: N, dir: EdgeDirection) -> NeighborsDirected<N, Ty>

Return an iterator of all neighbors that have an edge between a and themselves, in the specified direction.

If the graph's edges are undirected, this is equivalent to .neighbors(a).

If the node a does not exist in the graph, return an empty iterator.

Iterator element type is N.

fn edges(&self, from: N) -> Edges<N, E, Ty>

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, Ty>

Return an iterator over all edges of the graph with their weight in arbitrary order.

Iterator element type is (N, N, &E)

fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix> where Ix: IndexType

Return a Graph that corresponds to this GraphMap.

Note: node and edge indices in the Graph have nothing in common with the GraphMaps node weights N. The node weights N are used as node weights in the resulting Graph, too.

Trait Implementations

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

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

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, Ty: EdgeType> Debug for GraphMap<N, E, Ty>

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

Formats the value using the given formatter.

impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<N, E, Ty> where 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>

Creates a value from an iterator.

impl<N, E, Ty, Item> Extend<Item> for GraphMap<N, E, Ty> where 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>

Extends a collection with the contents of an iterator.

impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty> where 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 (Foo[Bar]) operation

impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty> where 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 indexing (Foo[Bar]) operation

impl<N, E, Ty> Default for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType

Create a new empty GraphMap.

fn default() -> Self

Returns the "default value" for a type.

impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType

type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>

fn node_identifiers(self) -> Self::NodeIdentifiers

fn node_count(&self) -> usize

impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty> where N: Copy + Ord + Hash, Ty: EdgeType

type Neighbors = Neighbors<'a, N, Ty>

fn neighbors(self, n: Self::NodeId) -> Self::Neighbors

impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty> where N: Copy + Ord + Hash, Ty: EdgeType

type NeighborsDirected = NeighborsDirected<'a, N, Ty>

fn neighbors_directed(self, n: N, dir: EdgeDirection) -> Self::NeighborsDirected

impl<'a, N: 'a, E: 'a, Ty> GraphEdgeRef for &'a GraphMap<N, E, Ty> where N: Copy, Ty: EdgeType

type EdgeRef = (N, N, &'a E)

impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType

type EdgeReferences = AllEdges<'a, N, E, Ty>

fn edge_references(self) -> Self::EdgeReferences

impl<N: Copy, E, Ty> GraphBase for GraphMap<N, E, Ty>

type NodeId = N

node identifier

type EdgeId = (N, N)

edge identifier

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

type Map = HashSet<N>

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

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

The GraphMap keeps an adjacency matrix internally.

type AdjMatrix = ()

fn adjacency_matrix(&self)

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