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 existence in constant time.

GraphMap is parameterized over:

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).

Implementations

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

pub fn new() -> Self[src]

Create a new GraphMap

pub fn with_capacity(nodes: usize, edges: usize) -> Self[src]

Create a new GraphMap with estimated capacity.

pub fn capacity(&self) -> (usize, usize)[src]

Return the current node and edge capacity of the graph.

pub fn is_directed(&self) -> bool[src]

Whether the graph has directed edges.

pub fn from_edges<I>(iterable: I) -> Self where
    I: IntoIterator,
    I::Item: IntoWeightedEdge<E, NodeId = N>, 
[src]

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

pub fn node_count(&self) -> usize[src]

Return the number of nodes in the graph.

pub fn edge_count(&self) -> usize[src]

Return the number of edges in the graph.

pub fn clear(&mut self)[src]

Remove all nodes and edges

pub fn add_node(&mut self, n: N) -> N[src]

Add node n to the graph.

pub fn remove_node(&mut self, n: N) -> bool[src]

Return true if node n was removed.

Computes in O(V) time, due to the removal of edges with other nodes.

pub fn contains_node(&self, n: N) -> bool[src]

Return true if the node is contained in the graph.

pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E>[src]

Add an edge connecting a and b to the graph, with associated data weight. For a directed graph, the edge is directed from a to b.

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

pub fn remove_edge(&mut self, a: N, b: N) -> Option<E>[src]

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

pub fn contains_edge(&self, a: N, b: N) -> bool[src]

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

pub fn nodes(&self) -> Nodes<'_, N>

Notable traits for Nodes<'a, N>

impl<'a, N> Iterator for Nodes<'a, N> where
    N: 'a + NodeTrait
type Item = N;
[src]

Return an iterator over the nodes of the graph.

Iterator element type is N.

pub fn neighbors(&self, a: N) -> Neighbors<'_, N, Ty>

Notable traits for Neighbors<'a, N, Ty>

impl<'a, N, Ty> Iterator for Neighbors<'a, N, Ty> where
    N: NodeTrait,
    Ty: EdgeType
type Item = N;
[src]

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.

pub fn neighbors_directed(
    &self,
    a: N,
    dir: Direction
) -> NeighborsDirected<'_, N, Ty>

Notable traits for NeighborsDirected<'a, N, Ty>

impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty> where
    N: NodeTrait,
    Ty: EdgeType
type Item = N;
[src]

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.

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

Notable traits for Edges<'a, N, E, Ty>

impl<'a, N, E, Ty> Iterator for Edges<'a, N, E, Ty> where
    N: 'a + NodeTrait,
    E: 'a,
    Ty: EdgeType
type Item = (N, N, &'a E);
[src]

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).

pub fn edge_weight(&self, a: N, b: N) -> Option<&E>[src]

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

pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E>[src]

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

pub fn all_edges(&self) -> AllEdges<'_, N, E, Ty>

Notable traits for AllEdges<'a, N, E, Ty>

impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty> where
    N: 'a + NodeTrait,
    E: 'a,
    Ty: EdgeType
type Item = (N, N, &'a E);
[src]

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

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

pub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty>

Notable traits for AllEdgesMut<'a, N, E, Ty>

impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty> where
    N: 'a + NodeTrait,
    E: 'a,
    Ty: EdgeType
type Item = (N, N, &'a mut E);
[src]

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)

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

Return a Graph that corresponds to this GraphMap.

  1. Note that 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.
  2. Note that the index type is user-chosen.

Computes in O(|V| + |E|) time (average).

Panics if the number of nodes or edges does not fit with the resulting graph’s index type.

Trait Implementations

impl<N, E, Ty> Build 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]

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

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

type NodeWeight = N

type EdgeWeight = E

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

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

Create a new empty GraphMap.

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.

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

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.

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.

type AdjMatrix = ()

The associated adjacency matrix type

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

type NodeId = N

node identifier

type EdgeId = (N, N)

edge identifier

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

type EdgeType = Ty

The kind edges in the graph.

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.

type Output = E

The returned type after indexing.

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.

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

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

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

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

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

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

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

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

impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a 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]

type NodeRef = (N, &'a N)

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

impl<N, E, Ty> NodeCount for 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]

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

type Map = HashSet<N>

The associated map type

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

Auto Trait Implementations

impl<N, E, Ty> RefUnwindSafe for GraphMap<N, E, Ty> where
    E: RefUnwindSafe,
    N: RefUnwindSafe,
    Ty: RefUnwindSafe

impl<N, E, Ty> Send for GraphMap<N, E, Ty> where
    E: Send,
    N: Send,
    Ty: Send

impl<N, E, Ty> Sync for GraphMap<N, E, Ty> where
    E: Sync,
    N: Sync,
    Ty: Sync

impl<N, E, Ty> Unpin for GraphMap<N, E, Ty> where
    E: Unpin,
    N: Unpin,
    Ty: Unpin

impl<N, E, Ty> UnwindSafe for GraphMap<N, E, Ty> where
    E: UnwindSafe,
    N: UnwindSafe,
    Ty: UnwindSafe

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<T> Pointable for T[src]

type Init = T

The type for initializers.

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.