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 and E for edges, called weights.
  • The node weight 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.
  • 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]

Create a new GraphMap

Create a new GraphMap with estimated capacity.

Return the current node and edge capacity of the graph.

Whether the graph has directed edges.

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),
]);Run

Return the number of nodes in the graph.

Return the number of edges in the graph.

Remove all nodes and edges

Add node n to the graph.

Return true if node n was removed.

Return true if the node is contained in the graph.

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"));Run

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);Run

Return true if the edge connecting a with b is contained in the graph.

Return an iterator over the nodes of the graph.

Iterator element type is N.

Return an iterator of all nodes with an edge starting from a.

  • Directed: Outgoing edges from a.
  • Undirected: All edges from or to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is N.

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 from a.
  • Directed, Incoming: All edges to a.
  • Undirected: All edges from or to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is N.

Return an iterator of target nodes with an edge starting from a, paired with their respective edge weights.

  • Directed: Outgoing edges from a.
  • Undirected: All edges from or to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is (N, &E).

Return a reference to the edge weight connecting a with b, or None if the edge does not exist in the graph.

Return a mutable reference to the edge weight connecting a with b, or None if the edge does not exist in the graph.

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

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

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<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty> where N: Copy + Ord + Hash, Ty: EdgeType
[src]

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]

impl<N, E, Ty> Data for GraphMap<N, E, Ty> where N: Copy + PartialEq, Ty: EdgeType
[src]

impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

The kind edges in the graph.

impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty> where N: Copy + PartialEq
[src]

node identifier

edge identifier

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

The associated map type

Create a new visitor 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]

The GraphMap keeps an adjacency matrix internally.

The associated adjacency matrix type

Create the adjacency matrix

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]

Add a new edge. If parallel edges (duplicate) are not allowed and the edge already exists, return None. Read more

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]

impl<N, E, Ty> FromElements for GraphMap<N, E, Ty> where Ty: EdgeType, N: NodeTrait
[src]

impl<N: Clone, E: Clone, Ty: Clone> Clone for GraphMap<N, E, Ty>
[src]

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<N: Eq + Hash + Debug, E: Debug, Ty: EdgeType> Debug for GraphMap<N, E, Ty>
[src]

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
[src]

Create a new GraphMap from an iterable of edges.

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]

Extend the graph from an iterable of edges.

Nodes are inserted automatically to match the edges.

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]

impl<'a, N: 'a, E: 'a, Ty> IntoEdges for &'a GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

Index GraphMap by node pairs to access edge weights.

The returned type after indexing

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]

Index GraphMap by node pairs to access edge weights.

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]

Create a new empty GraphMap.

Returns the "default value" for a type. Read more

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

impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]

Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more

Convert a to an integer index.

Convert i to a node index

impl<N, E, Ty> NodeCompactIndexable for GraphMap<N, E, Ty> where N: NodeTrait, Ty: EdgeType
[src]