pub struct Csr<N = (), E = (), Ty = Directed, Ix = DefaultIx> { /* private fields */ }
Expand description
Compressed Sparse Row (CSR
) is a sparse adjacency matrix graph.
CSR
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. - Index type
Ix
, which determines the maximum size of the graph.
Using O(|E| + |V|) space.
Self loops are allowed, no parallel edges.
Fast iteration of the outgoing edges of a vertex.
Implementations§
source§impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
sourcepub fn with_nodes(n: usize) -> Selfwhere
N: Default,
pub fn with_nodes(n: usize) -> Selfwhere
N: Default,
Create a new Csr
with n
nodes. N
must implement Default
for the weight of each node.
§Example
use petgraph::csr::Csr;
use petgraph::prelude::*;
let graph = Csr::<u8,()>::with_nodes(5);
assert_eq!(graph.node_count(),5);
assert_eq!(graph.edge_count(),0);
assert_eq!(graph[0],0);
assert_eq!(graph[4],0);
source§impl<N, E, Ix> Csr<N, E, Directed, Ix>where
Ix: IndexType,
impl<N, E, Ix> Csr<N, E, Directed, Ix>where
Ix: IndexType,
sourcepub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>
pub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>
Create a new Csr
from a sorted sequence of edges
Edges must be sorted and unique, where the sort order is the default order for the pair (u, v) in Rust (u has priority).
Computes in O(|E| + |V|) time.
§Example
use petgraph::csr::Csr;
use petgraph::prelude::*;
let graph = Csr::<(),()>::from_sorted_edges(&[
(0, 1), (0, 2),
(1, 0), (1, 2), (1, 3),
(2, 0),
(3, 1),
]);
source§impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
pub fn node_count(&self) -> usize
pub fn edge_count(&self) -> usize
pub fn is_directed(&self) -> bool
sourcepub fn clear_edges(&mut self)
pub fn clear_edges(&mut self)
Remove all edges
sourcepub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>
pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>
Adds a new node with the given weight, returning the corresponding node index.
sourcepub fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E,
) -> boolwhere
E: Clone,
pub fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E,
) -> boolwhere
E: Clone,
Return true
if the edge was added
If you add all edges in row-major order, the time complexity is O(|V|·|E|) for the whole operation.
Panics if a
or b
are out of bounds.
sourcepub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
Computes in O(log |V|) time.
Panics if the node a
does not exist.
sourcepub fn out_degree(&self, a: NodeIndex<Ix>) -> usize
pub fn out_degree(&self, a: NodeIndex<Ix>) -> usize
Computes in O(1) time.
Panics if the node a
does not exist.
sourcepub fn neighbors_slice(&self, a: NodeIndex<Ix>) -> &[NodeIndex<Ix>]
pub fn neighbors_slice(&self, a: NodeIndex<Ix>) -> &[NodeIndex<Ix>]
Computes in O(1) time.
Panics if the node a
does not exist.
sourcepub fn edges_slice(&self, a: NodeIndex<Ix>) -> &[E]
pub fn edges_slice(&self, a: NodeIndex<Ix>) -> &[E]
Computes in O(1) time.
Panics if the node a
does not exist.
Trait Implementations§
source§impl<N, E, Ty, Ix> Data for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Data for Csr<N, E, Ty, Ix>
type NodeWeight = N
type EdgeWeight = E
source§impl<N, E, Ty, Ix> EdgeCount for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> EdgeCount for Csr<N, E, Ty, Ix>
source§fn edge_count(&self) -> usize
fn edge_count(&self) -> usize
source§impl<'a, N, E, Ty, Ix> GetAdjacencyMatrix for &'a Csr<N, E, Ty, Ix>
impl<'a, N, E, Ty, Ix> GetAdjacencyMatrix for &'a Csr<N, E, Ty, Ix>
The adjacency matrix for Csr is a bitmap that’s computed by
.adjacency_matrix()
.
§type AdjMatrix = FixedBitSet
type AdjMatrix = FixedBitSet
source§fn adjacency_matrix(&self) -> FixedBitSet
fn adjacency_matrix(&self) -> FixedBitSet
source§fn is_adjacent(
&self,
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
) -> bool
fn is_adjacent( &self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> bool
source§impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr<N, E, Ty, Ix>
impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr<N, E, Ty, Ix>
type EdgeRef = EdgeReference<'a, E, Ty, Ix>
type EdgeReferences = EdgeReferences<'a, E, Ty, Ix>
fn edge_references(self) -> Self::EdgeReferences
source§impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix>
impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix>
source§fn neighbors(self, a: Self::NodeId) -> Self::Neighbors
fn neighbors(self, a: Self::NodeId) -> Self::Neighbors
Return an iterator of all neighbors of a
.
Directed
: Targets of outgoing edges froma
.Undirected
: Opposing endpoints of all edges connected toa
.
Panics if the node a
does not exist.
Iterator element type is NodeIndex<Ix>
.
type Neighbors = Neighbors<'a, Ix>
source§impl<'a, N, E, Ty, Ix> IntoNodeIdentifiers for &'a Csr<N, E, Ty, Ix>
impl<'a, N, E, Ty, Ix> IntoNodeIdentifiers for &'a Csr<N, E, Ty, Ix>
type NodeIdentifiers = NodeIdentifiers<Ix>
fn node_identifiers(self) -> Self::NodeIdentifiers
source§impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Csr<N, E, Ty, Ix>
impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Csr<N, E, Ty, Ix>
type NodeRef = (Ix, &'a N)
type NodeReferences = NodeReferences<'a, N, Ix>
fn node_references(self) -> Self::NodeReferences
source§impl<N, E, Ty, Ix> NodeIndexable for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> NodeIndexable for Csr<N, E, Ty, 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.impl<N, E, Ty, Ix> NodeCompactIndexable for Csr<N, E, Ty, Ix>
Auto Trait Implementations§
impl<N, E, Ty, Ix> Freeze for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> RefUnwindSafe for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Send for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Sync for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> Unpin for Csr<N, E, Ty, Ix>
impl<N, E, Ty, Ix> UnwindSafe for Csr<N, E, Ty, 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
)