Struct petgraph::matrix_graph::MatrixGraph
source · 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 andE
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 toOption<E>
). You may specifyNotZero<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 toDefaultIx
).
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>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Ty, Null, Ix>
sourcepub fn with_capacity(node_capacity: usize) -> Self
pub fn with_capacity(node_capacity: usize) -> Self
Create a new MatrixGraph
with estimated capacity for nodes.
sourcepub fn node_count(&self) -> usize
pub fn node_count(&self) -> usize
Return the number of nodes (vertices) in the graph.
Computes in O(1) time.
sourcepub fn edge_count(&self) -> usize
pub fn edge_count(&self) -> usize
Return the number of edges in the graph.
Computes in O(1) time.
sourcepub fn is_directed(&self) -> bool
pub fn is_directed(&self) -> bool
Return whether the graph has directed edges or not.
sourcepub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>
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.
sourcepub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N
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.
sourcepub fn update_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E,
) -> Option<E>
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.
sourcepub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E)
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.
sourcepub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E
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
.
sourcepub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
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.
sourcepub fn node_weight(&self, a: NodeIndex<Ix>) -> &N
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.
sourcepub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N
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.
sourcepub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E
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
.
sourcepub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E
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
.
sourcepub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, Ty, Null, Ix> ⓘ
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 froma
.Undirected
: All edges from or toa
.
Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>
.
sourcepub fn edges(&self, a: NodeIndex<Ix>) -> Edges<'_, Ty, Null, Ix> ⓘ
pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<'_, Ty, Null, Ix> ⓘ
Return an iterator of all edges of a
.
Directed
: Outgoing edges froma
.Undirected
: All edges connected toa
.
Produces an empty iterator if the node doesn’t exist.
Iterator element type is (NodeIndex<Ix>, NodeIndex<Ix>, &E)
.
sourcepub fn from_edges<I>(iterable: I) -> Selfwhere
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
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),
]);
sourcepub 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,
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>
impl<N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix>
sourcepub fn neighbors_directed(
&self,
a: NodeIndex<Ix>,
d: Direction,
) -> Neighbors<'_, Directed, Null, Ix> ⓘ
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 froma
.Incoming
: All edges toa
.
Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>
.
sourcepub fn edges_directed(
&self,
a: NodeIndex<Ix>,
d: Direction,
) -> Edges<'_, Directed, Null, Ix> ⓘ
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 froma
.Incoming
: All edges toa
.
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>
impl<N, E> MatrixGraph<N, E, Directed>
source§impl<N, E> MatrixGraph<N, E, Undirected>
impl<N, E> MatrixGraph<N, E, Undirected>
sourcepub fn new_undirected() -> Self
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>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Build for MatrixGraph<N, E, Ty, Null, Ix>
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>
fn add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Option<Self::EdgeId>
None
.source§fn update_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight,
) -> Self::EdgeId
fn update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Self::EdgeId
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>
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>
fn clone(&self) -> MatrixGraph<N, E, Ty, Null, Ix>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Data for MatrixGraph<N, E, Ty, Null, Ix>
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>
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§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> EdgeCount for MatrixGraph<N, E, Ty, Null, Ix>
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
fn edge_count(&self) -> usize
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix>
source§fn adjacency_matrix(&self) -> Self::AdjMatrix
fn adjacency_matrix(&self) -> Self::AdjMatrix
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix>
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix>
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
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
.
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>
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.
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
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§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>
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§impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>
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>
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>
impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdges for &'a MatrixGraph<N, E, Ty, Null, Ix>
source§impl<'a, N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgesDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>
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>
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>
impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null, Ix>
source§impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>
impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>
type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>
fn neighbors_directed( self, a: NodeIndex<Ix>, d: Direction, ) -> Self::NeighborsDirected
source§impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix>
impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix>
type NodeIdentifiers = NodeIdentifiers<'a, Ix>
fn node_identifiers(self) -> Self::NodeIdentifiers
source§impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>
impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>
type NodeRef = (NodeIndex<Ix>, &'a N)
type NodeReferences = NodeReferences<'a, N, Ix>
fn node_references(self) -> Self::NodeReferences
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix>
fn node_count(&self) -> usize
source§impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeIndexable for MatrixGraph<N, E, Ty, Null, Ix>
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
fn node_bound(&self) -> usize
source§fn from_index(&self, ix: usize) -> Self::NodeId
fn from_index(&self, ix: usize) -> Self::NodeId
i
to a node index. i
must be a valid value in the graph.Auto Trait Implementations§
impl<N, E, Ty, Null, Ix> Freeze for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty, Null, Ix> RefUnwindSafe for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty, Null, Ix> Send for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty, Null, Ix> Sync for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty, Null, Ix> Unpin for MatrixGraph<N, E, Ty, Null, Ix>
impl<N, E, Ty, Null, Ix> UnwindSafe for MatrixGraph<N, E, Ty, Null, Ix>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)