Type Alias UnGraphMap

pub type UnGraphMap<N, E> = GraphMap<N, E, Undirected>;

A GraphMap with undirected edges.

For example, an edge between 1 and 2 is equivalent to an edge between 2 and 1.

Aliased Type

struct UnGraphMap<N, E> {
    nodes: OrderMap<N, Vec<(N, CompactDirection)>>,
    edges: OrderMap<(N, N), E>,
    ty: PhantomData<Undirected>,
}

Fields

nodes: OrderMap<N, Vec<(N, CompactDirection)>>

edges: OrderMap<(N, N), E>

ty: PhantomData<Undirected>

Implementations

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

where N: NodeTrait, Ty: EdgeType,

pub fn new() -> Self

Create a new GraphMap

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

Create a new GraphMap with estimated capacity.

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

Return the current node and edge capacity of the graph.

fn edge_key(a: N, b: N) -> (N, N)

Use their natual order to map the node pair (a, b) to a canonical edge id.

pub fn is_directed(&self) -> bool

Whether the graph has directed edges.

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

pub fn node_count(&self) -> usize

Return the number of nodes in the graph.

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

pub fn clear(&mut self)

Remove all nodes and edges

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

Add node n to the graph.

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

Return true if node n was removed.

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

Return true if the node is contained in the graph.

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

fn remove_single_edge(&mut self, a: &N, b: &N, dir: Direction) -> bool

Remove edge relation from a to b

Return true if it did exist.

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

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

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

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

Return an iterator over the nodes of the graph.

Iterator element type is N.

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.

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.

pub fn edges(&self, from: 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, &E).

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.

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.

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)

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)

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.

Trait Implementations

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

where Ty: EdgeType, N: NodeTrait,

fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId

fn add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Option<Self::EdgeId>

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

fn update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Self::EdgeId

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

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

where Ty: EdgeType, N: NodeTrait,

fn with_capacity(nodes: usize, edges: usize) -> Self

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

where N: Copy + PartialEq, Ty: EdgeType,

type NodeWeight = N

type EdgeWeight = E

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

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

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.

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

where Ty: EdgeType, N: NodeTrait,

fn from_elements<I>(iterable: I) -> Self

where Self: Sized, I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,

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

fn adjacency_matrix(&self)

Create the adjacency matrix

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

Return true if there is an edge from a to b, false otherwise.

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

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

where N: NodeTrait, Ty: EdgeType,

type EdgeType = Ty

The kind edges in the graph.

fn is_directed(&self) -> bool

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

Performs the indexing (container[index]) 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

Performs the mutable indexing (container[index]) operation.

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

where N: NodeTrait, Ty: EdgeType,

fn node_count(&self) -> usize

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

where N: NodeTrait, Ty: EdgeType,

fn node_bound(&self) -> usize

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

fn to_index(&self, ix: Self::NodeId) -> usize

Convert a to an integer index.

fn from_index(&self, ix: usize) -> Self::NodeId

Convert i to a node index

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

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

Create a new visitor map

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

where N: NodeTrait, Ty: EdgeType,