pub struct GraphMap<N, E, Ty> { /* private fields */ }
Expand description

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§

source§

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

source

pub fn new() -> GraphMap<N, E, Ty>

Create a new GraphMap

source

pub fn with_capacity(nodes: usize, edges: usize) -> GraphMap<N, E, Ty>

Create a new GraphMap with estimated capacity.

source

pub fn capacity(&self) -> (usize, usize)

Return the current node and edge capacity of the graph.

source

pub fn is_directed(&self) -> bool

Whether the graph has directed edges.

source

pub fn from_edges<I>(iterable: I) -> GraphMap<N, E, Ty>
where I: IntoIterator, <I as IntoIterator>::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),
]);
source

pub fn node_count(&self) -> usize

Return the number of nodes in the graph.

source

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

source

pub fn clear(&mut self)

Remove all nodes and edges

source

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

Add node n to the graph.

source

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

Return true if node n was removed.

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

source

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

Return true if the node is contained in the graph.

source

pub 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. 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"));
source

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

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

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

source

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

Return an iterator over the nodes of the graph.

Iterator element type is N.

source

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

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.

source

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

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.

source

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

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, N, &E).

source

pub fn edges_directed( &self, a: N, dir: Direction ) -> EdgesDirected<'_, N, E, Ty>

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

  • Directed, Outgoing: All edges from a.
  • Directed, Incoming: All edges to a.
  • Undirected, Outgoing: All edges connected to a, with a being the source of each edge.
  • Undirected, Incoming: All edges connected to a, with a being the target of each edge.

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

source

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

source

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

source

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

source

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

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)

source

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

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.

source

pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> GraphMap<N, E, Ty>
where Ix: IndexType, E: Clone,

Creates a GraphMap that corresponds to the given Graph.

Warning: Nodes with the same weight are merged and only the last parallel edge is kept. Node and edge indices of the Graph are lost. Only use this function if the node weights are distinct and there are no parallel edges.

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

Trait Implementations§

source§

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

source§

fn add_node( &mut self, weight: <GraphMap<N, E, Ty> as Data>::NodeWeight ) -> <GraphMap<N, E, Ty> as GraphBase>::NodeId

source§

fn add_edge( &mut self, a: <GraphMap<N, E, Ty> as GraphBase>::NodeId, b: <GraphMap<N, E, Ty> as GraphBase>::NodeId, weight: <GraphMap<N, E, Ty> as Data>::EdgeWeight ) -> Option<<GraphMap<N, E, Ty> as GraphBase>::EdgeId>

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

fn update_edge( &mut self, a: <GraphMap<N, E, Ty> as GraphBase>::NodeId, b: <GraphMap<N, E, Ty> as GraphBase>::NodeId, weight: <GraphMap<N, E, Ty> as Data>::EdgeWeight ) -> <GraphMap<N, E, Ty> as GraphBase>::EdgeId

Add or update the edge from a to b. Return the id of the affected edge.
source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

fn with_capacity(nodes: usize, edges: usize) -> GraphMap<N, E, Ty>

source§

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

§

type NodeWeight = N

§

type EdgeWeight = E

source§

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

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter. Read more
source§

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

Create a new empty GraphMap.

source§

fn default() -> GraphMap<N, E, Ty>

Returns the “default value” for a type. Read more
source§

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

source§

fn edge_count(&self) -> usize

Return the number of edges in the graph.
source§

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

source§

fn edge_bound(&self) -> usize

Return an upper bound of the edge indices in the graph (suitable for the size of a bitmap).
source§

fn to_index(&self, ix: <GraphMap<N, E, Ty> as GraphBase>::EdgeId) -> usize

Convert a to an integer index.
source§

fn from_index(&self, ix: usize) -> <GraphMap<N, E, Ty> as GraphBase>::EdgeId

Convert i to an edge index. i must be a valid value in the graph.
source§

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.

source§

fn extend<I>(&mut self, iterable: I)
where I: IntoIterator<Item = Item>,

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more
source§

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

source§

fn from_elements<I>(iterable: I) -> GraphMap<N, E, Ty>
where GraphMap<N, E, Ty>: Sized, I: IntoIterator<Item = Element<<GraphMap<N, E, Ty> as Data>::NodeWeight, <GraphMap<N, E, Ty> as Data>::EdgeWeight>>,

source§

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.

source§

fn from_iter<I>(iterable: I) -> GraphMap<N, E, Ty>
where I: IntoIterator<Item = Item>,

Creates a value from an iterator. Read more
source§

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

The associated adjacency matrix type
source§

fn adjacency_matrix(&self)

Create the adjacency matrix
source§

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

Return true if there is an edge from a to b, false otherwise. Read more
source§

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

§

type NodeId = N

node identifier
§

type EdgeId = (N, N)

edge identifier
source§

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

§

type EdgeType = Ty

The kind of edges in the graph.
source§

fn is_directed(&self) -> bool

source§

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

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

Performs the indexing (container[index]) operation. Read more
source§

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.

source§

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

Performs the mutable indexing (container[index]) operation. Read more
source§

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

§

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

§

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

source§

fn edge_references( self ) -> <&'a GraphMap<N, E, Ty> as IntoEdgeReferences>::EdgeReferences

source§

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

§

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

source§

fn edges( self, a: <&'a GraphMap<N, E, Ty> as GraphBase>::NodeId ) -> <&'a GraphMap<N, E, Ty> as IntoEdges>::Edges

source§

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

§

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

source§

fn edges_directed( self, a: <&'a GraphMap<N, E, Ty> as GraphBase>::NodeId, dir: Direction ) -> <&'a GraphMap<N, E, Ty> as IntoEdgesDirected>::EdgesDirected

source§

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

§

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

source§

fn neighbors( self, n: <&'a GraphMap<N, E, Ty> as GraphBase>::NodeId ) -> <&'a GraphMap<N, E, Ty> as IntoNeighbors>::Neighbors

Return an iterator of the neighbors of node a.
source§

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

source§

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

source§

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

§

type NodeRef = (N, &'a N)

§

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

source§

fn node_references( self ) -> <&'a GraphMap<N, E, Ty> as IntoNodeReferences>::NodeReferences

source§

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

source§

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

source§

fn node_bound(&self) -> usize

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

fn to_index(&self, ix: <GraphMap<N, E, Ty> as GraphBase>::NodeId) -> usize

Convert a to an integer index.
source§

fn from_index(&self, ix: usize) -> <GraphMap<N, E, Ty> as GraphBase>::NodeId

Convert i to a node index. i must be a valid value in the graph.
source§

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

§

type Map = HashSet<N>

The associated map type
source§

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

Create a new visitor map
source§

fn reset_map(&self, map: &mut <GraphMap<N, E, Ty> as Visitable>::Map)

Reset the visitor map (and resize to new size of graph if needed)
source§

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

Auto Trait Implementations§

§

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

§

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§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T, U> AsBindGroupShaderType<U> for T
where U: ShaderType, &'a T: for<'a> Into<U>,

source§

fn as_bind_group_shader_type(&self, _images: &RenderAssets<Image>) -> U

Return the T ShaderType for self. When used in AsBindGroup derives, it is safe to assume that all images in self exist.
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> Downcast<T> for T

source§

fn downcast(&self) -> &T

source§

impl<T> Downcast for T
where T: Any,

source§

fn into_any(self: Box<T>) -> Box<dyn Any>

Convert Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>. Box<dyn Any> can then be further downcast into Box<ConcreteType> where ConcreteType implements Trait.
source§

fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>

Convert Rc<Trait> (where Trait: Downcast) to Rc<Any>. Rc<Any> can then be further downcast into Rc<ConcreteType> where ConcreteType implements Trait.
source§

fn as_any(&self) -> &(dyn Any + 'static)

Convert &Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &Any’s vtable from &Trait’s.
source§

fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)

Convert &mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &mut Any’s vtable from &mut Trait’s.
source§

impl<T> DowncastSync for T
where T: Any + Send + Sync,

source§

fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>

Convert Arc<Trait> (where Trait: Downcast) to Arc<Any>. Arc<Any> can then be further downcast into Arc<ConcreteType> where ConcreteType implements Trait.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<S> FromSample<S> for S

source§

fn from_sample_(s: S) -> S

source§

impl<T> FromWorld for T
where T: Default,

source§

fn from_world(_world: &mut World) -> T

Creates Self using data from the given World.
source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> ToSample<U> for T
where U: FromSample<T>,

source§

fn to_sample_(self) -> U

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

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

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> TypeData for T
where T: 'static + Send + Sync + Clone,

source§

impl<T> Upcast<T> for T

source§

fn upcast(&self) -> Option<&T>

source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<S, T> Duplex<S> for T
where T: FromSample<S> + ToSample<S>,

source§

impl<T> Settings for T
where T: 'static + Send + Sync,

source§

impl<T> WasmNotSend for T
where T: Send,

source§

impl<T> WasmNotSendSync for T

source§

impl<T> WasmNotSync for T
where T: Sync,