pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped = E> = Option<E>, Ix = u16> { /* private fields */ }
Expand description

MatrixGraph<N, E, Ty, Null> is a graph datastructure using an adjacency matrix representation.

MatrixGraph is parameterized over:

  • Associated data N for nodes and E for edges, called weights. The associated data can be of arbitrary type.
  • Edge type Ty that determines whether the graph edges are directed or undirected.
  • Nullable type Null, which denotes the edges’ presence (defaults to Option<E>). You may specify NotZero<E> if you want to use a sentinel value (such as 0) to mark the absence of an edge.
  • Index type Ix that sets the maximum size for the graph (defaults to DefaultIx).

The graph uses O(|V^2|) space, with fast edge insertion & amortized node insertion, as well as efficient graph search and graph algorithms on dense graphs.

This graph is backed by a flattened 2D array. For undirected graphs, only the lower triangular matrix is stored. Since the backing array stores edge weights, it is recommended to box large edge weights.

Implementations§

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Ty, Null, Ix>

source

pub fn with_capacity(node_capacity: usize) -> Self

Create a new MatrixGraph with estimated capacity for nodes.

source

pub fn clear(&mut self)

Remove all nodes and edges.

source

pub fn node_count(&self) -> usize

Return the number of nodes (vertices) in the graph.

Computes in O(1) time.

source

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

Computes in O(1) time.

source

pub fn is_directed(&self) -> bool

Return whether the graph has directed edges or not.

source

pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>

Add a node (also called vertex) with associated data weight to the graph.

Computes in O(1) time.

Return the index of the new node.

Panics if the MatrixGraph is at the maximum number of nodes for its index type.

source

pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N

Remove a from the graph.

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

Panics if the node a does not exist.

source

pub fn update_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E ) -> Option<E>

Update the edge from a to b to the graph, with its associated data weight.

Return the previous data, if any.

Computes in O(1) time, best case. Computes in O(|V|^2) time, worst case (matrix needs to be re-allocated).

Panics if any of the nodes don’t exist.

source

pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E)

Add an edge from a to b to the graph, with its associated data weight.

Computes in O(1) time, best case. Computes in O(|V|^2) time, worst case (matrix needs to be re-allocated).

Panics if any of the nodes don’t exist. Panics if an edge already exists from a to b.

Note: MatrixGraph does not allow adding parallel (“duplicate”) edges. If you want to avoid this, use .update_edge(a, b, weight) instead.

source

pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E

Remove the edge from a to b to the graph.

Panics if any of the nodes don’t exist. Panics if no edge exists between a and b.

source

pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool

Return true if there is an edge between a and b.

Panics if any of the nodes don’t exist.

source

pub fn node_weight(&self, a: NodeIndex<Ix>) -> &N

Access the weight for node a.

Also available with indexing syntax: &graph[a].

Panics if the node doesn’t exist.

source

pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N

Access the weight for node a, mutably.

Also available with indexing syntax: &mut graph[a].

Panics if the node doesn’t exist.

source

pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E

Access the weight for edge e.

Also available with indexing syntax: &graph[e].

Panics if no edge exists between a and b.

source

pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E

Access the weight for edge e, mutably.

Also available with indexing syntax: &mut graph[e].

Panics if no edge exists between a and b.

source

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

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

source

pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<'_, Ty, Null, Ix>

Return an iterator of all edges of a.

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

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

source

pub fn from_edges<I>(iterable: I) -> Selfwhere I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>, N: Default,

Create a new MatrixGraph from an iterable of edges.

Node weights N are set to default values. 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::matrix_graph::MatrixGraph;

let gr = MatrixGraph::<(), i32>::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 2), (1, 3),
    (2, 3),
]);
source

pub fn extend_with_edges<I>(&mut self, iterable: I)where I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>, N: Default,

Extend the graph from an iterable of edges.

Node weights N are set to default values. 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.

source§

impl<N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix>

source

pub fn neighbors_directed( &self, a: NodeIndex<Ix>, d: Direction ) -> Neighbors<'_, Directed, Null, Ix>

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

  • Outgoing: All edges from a.
  • Incoming: All edges to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

source

pub fn edges_directed( &self, a: NodeIndex<Ix>, d: Direction ) -> Edges<'_, Directed, Null, Ix>

Return an iterator of all edges of a, in the specified direction.

  • Outgoing: All edges from a.
  • Incoming: All edges to a.

Produces an empty iterator if the node a doesn’t exist.
Iterator element type is (NodeIndex<Ix>, NodeIndex<Ix>, &E).

source§

impl<N, E> MatrixGraph<N, E, Directed>

source

pub fn new() -> Self

Create a new MatrixGraph with directed edges.

This is a convenience method. Use MatrixGraph::with_capacity or MatrixGraph::default for a constructor that is generic in all the type parameters of MatrixGraph.

source§

impl<N, E> MatrixGraph<N, E, Undirected>

source

pub fn new_undirected() -> Self

Create a new MatrixGraph with undirected edges.

This is a convenience method. Use MatrixGraph::with_capacity or MatrixGraph::default for a constructor that is generic in all the type parameters of MatrixGraph.

Trait Implementations§

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Build for MatrixGraph<N, E, Ty, Null, Ix>

source§

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

source§

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

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

impl<N: Clone, E: Clone, Ty: Clone, Null: Clone + Nullable<Wrapped = E>, Ix: Clone> Clone for MatrixGraph<N, E, Ty, Null, Ix>

source§

fn clone(&self) -> MatrixGraph<N, E, Ty, Null, Ix>

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: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Data for MatrixGraph<N, E, Ty, Null, Ix>

§

type NodeWeight = N

§

type EdgeWeight = E

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Default for MatrixGraph<N, E, Ty, Null, Ix>

Create a new empty MatrixGraph.

source§

fn default() -> Self

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> EdgeCount for MatrixGraph<N, E, Ty, Null, Ix>

source§

fn edge_count(&self) -> usize

Return the number of edges in the graph.
source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix>

§

type AdjMatrix = ()

The associated adjacency matrix type
source§

fn adjacency_matrix(&self) -> Self::AdjMatrix

Create the adjacency matrix
source§

fn is_adjacent( &self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix> ) -> bool

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix>

§

type NodeId = NodeIndex<Ix>

node identifier
§

type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>)

edge identifier
source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix>

§

type EdgeType = Ty

The kind of edges in the graph.
source§

fn is_directed(&self) -> bool

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>

Index the MatrixGraph by NodeIndex pair to access edge weights.

Also available with indexing syntax: &graph[e].

Panics if no edge exists between a and b.

§

type Output = E

The returned type after indexing.
source§

fn index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>

Index the MatrixGraph by NodeIndex to access node weights.

Panics if the node doesn’t exist.

§

type Output = N

The returned type after indexing.
source§

fn index(&self, ax: NodeIndex<Ix>) -> &N

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>

Index the MatrixGraph by NodeIndex pair to access edge weights.

Also available with indexing syntax: &mut graph[e].

Panics if no edge exists between a and b.

source§

fn index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>

Index the MatrixGraph by NodeIndex to access node weights.

Panics if the node doesn’t exist.

source§

fn index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N

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

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>

§

type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E)

§

type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>

source§

fn edge_references(self) -> Self::EdgeReferences

source§

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdges for &'a MatrixGraph<N, E, Ty, Null, Ix>

§

type Edges = Edges<'a, Ty, Null, Ix>

source§

fn edges(self, a: Self::NodeId) -> Self::Edges

source§

impl<'a, N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgesDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>

§

type EdgesDirected = Edges<'a, Directed, Null, Ix>

source§

fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected

source§

impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null, Ix>

§

type Neighbors = Neighbors<'a, Ty, Null, Ix>

source§

fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors

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

impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>

source§

impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix>

source§

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix>

source§

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeIndexable for MatrixGraph<N, E, Ty, Null, Ix>

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: NodeIndex<Ix>) -> usize

Convert a to an integer index.
source§

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

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

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Visitable for MatrixGraph<N, E, Ty, Null, Ix>

§

type Map = FixedBitSet

The associated map type
source§

fn visit_map(&self) -> FixedBitSet

Create a new visitor map
source§

fn reset_map(&self, map: &mut Self::Map)

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

Auto Trait Implementations§

§

impl<N, E, Ty, Null, Ix> RefUnwindSafe for MatrixGraph<N, E, Ty, Null, Ix>where Ix: RefUnwindSafe, N: RefUnwindSafe, Null: RefUnwindSafe, Ty: RefUnwindSafe,

§

impl<N, E, Ty, Null, Ix> Send for MatrixGraph<N, E, Ty, Null, Ix>where Ix: Send, N: Send, Null: Send, Ty: Send,

§

impl<N, E, Ty, Null, Ix> Sync for MatrixGraph<N, E, Ty, Null, Ix>where Ix: Sync, N: Sync, Null: Sync, Ty: Sync,

§

impl<N, E, Ty, Null, Ix> Unpin for MatrixGraph<N, E, Ty, Null, Ix>where Ix: Unpin, N: Unpin, Null: Unpin, Ty: Unpin,

§

impl<N, E, Ty, Null, Ix> UnwindSafe for MatrixGraph<N, E, Ty, Null, Ix>where Ix: UnwindSafe, N: UnwindSafe, Null: UnwindSafe, Ty: UnwindSafe,

Blanket Implementations§

source§

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

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

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

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

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

source§

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

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere 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 Twhere 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> TryFrom<U> for Twhere 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 Twhere 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.