Struct petgraph::csr::Csr

pub struct Csr<N = (), E = (), Ty = Directed, Ix = DefaultIx> { /* private fields */ }

Compressed Sparse Row (CSR) is a sparse adjacency matrix graph.

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

impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

pub fn new() -> Self

Create an empty Csr.

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

impl<N, E, Ix> Csr<N, E, Directed, Ix>where
    Ix: IndexType,

pub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>where
    Edge: Clone + IntoWeightedEdge<E, NodeId = NodeIndex<Ix>>,
    N: Default,

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

impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

pub fn node_count(&self) -> usize

pub fn edge_count(&self) -> usize

pub fn is_directed(&self) -> bool

pub fn clear_edges(&mut self)

Remove all edges

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

Adds a new node with the given weight, returning the corresponding node index.

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.

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.

pub fn out_degree(&self, a: NodeIndex<Ix>) -> usize

Computes in O(1) time.

Panics if the node a does not exist.

pub fn neighbors_slice(&self, a: NodeIndex<Ix>) -> &[NodeIndex<Ix>]

Computes in O(1) time.

Panics if the node a does not exist.

pub fn edges_slice(&self, a: NodeIndex<Ix>) -> &[E]

Computes in O(1) time.

Panics if the node a does not exist.

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

Return an iterator of all edges of a.

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

Panics if the node a does not exist.
Iterator element type is EdgeReference<E, Ty, Ix>.

Trait Implementations

impl<N: Clone, E: Clone, Ty, Ix: Clone> Clone for Csr<N, E, Ty, Ix>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, E, Ty, Ix> Data for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type NodeWeight = N

type EdgeWeight = E

impl<N: Debug, E: Debug, Ty: Debug, Ix: Debug> Debug for Csr<N, E, Ty, Ix>

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

Formats the value using the given formatter.

impl<N, E, Ty, Ix> Default for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

fn default() -> Self

Returns the “default value” for a type.

impl<N, E, Ty, Ix> EdgeCount for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

fn edge_count(&self) -> usize

Return the number of edges in the graph.

impl<'a, N, E, Ty, Ix> GetAdjacencyMatrix for &'a Csr<N, E, Ty, Ix>where
    Ix: IndexType,
    Ty: EdgeType,

The adjacency matrix for Csr is a bitmap that’s computed by .adjacency_matrix().

type AdjMatrix = FixedBitSet

The associated adjacency matrix type

fn adjacency_matrix(&self) -> FixedBitSet

Create the adjacency matrix

fn is_adjacent(
    &self,
    matrix: &FixedBitSet,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>
) -> bool

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

impl<N, E, Ty, Ix> GraphBase for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type NodeId = Ix

node identifier

type EdgeId = usize

edge identifier

impl<N, E, Ty, Ix> GraphProp for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type EdgeType = Ty

The kind edges in the graph.

fn is_directed(&self) -> bool

impl<N, E, Ty, Ix> Index<Ix> for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type Output = N

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<N, E, Ty, Ix> IndexMut<Ix> for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

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

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

impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type EdgeRef = EdgeReference<'a, E, Ty, Ix>

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

fn edge_references(self) -> Self::EdgeReferences

impl<'a, N, E, Ty, Ix> IntoEdges for &'a Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

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

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

impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

fn neighbors(self, a: Self::NodeId) -> Self::Neighbors

Return an iterator of all neighbors of a.

• Directed: Targets of outgoing edges from a.
• Undirected: Opposing endpoints of all edges connected to a.

Panics if the node a does not exist.
Iterator element type is NodeIndex<Ix>.

type Neighbors = Neighbors<'a, Ix>

impl<'a, N, E, Ty, Ix> IntoNodeIdentifiers for &'a Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type NodeIdentifiers = NodeIdentifiers<Ix>

fn node_identifiers(self) -> Self::NodeIdentifiers

impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type NodeRef = (Ix, &'a N)

type NodeReferences = NodeReferences<'a, N, Ix>

fn node_references(self) -> Self::NodeReferences

impl<N, E, Ty, Ix> NodeCount for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

fn node_count(&self) -> usize

impl<N, E, Ty, Ix> NodeIndexable for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

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, a: Self::NodeId) -> usize

Convert a to an integer index.

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

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

impl<N, E, Ty, Ix> Visitable for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,

type Map = FixedBitSet

The associated map type

fn visit_map(&self) -> FixedBitSet

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, Ix> NodeCompactIndexable for Csr<N, E, Ty, Ix>where
    Ty: EdgeType,
    Ix: IndexType,