[][src]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 existence 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).

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

Return an iterator over the nodes of the graph.

Iterator element type is N.

pub fn neighbors(&self, a: N) -> Neighbors<N, Ty>[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>
[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>[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>[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>[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> Arbitrary for GraphMap<N, E, Ty> where
    N: NodeTrait + Arbitrary,
    E: Arbitrary,
    Ty: EdgeType + Clone + Send + 'static, 
[src]

Arbitrary for GraphMap creates a graph by selecting a node count and a probability for each possible edge to exist.

The result will be simple graph or digraph, self loops possible, no parallel edges.

The exact properties of the produced graph is subject to change.

Requires crate features "quickcheck" and "graphmap"

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> NodeCompactIndexable for 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<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

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