Struct petgraph::csr::Csr

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

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

Using O(|E| + |V|) space.

Self loops are allowed, no parallel edges.

Fast iteration of the outgoing edges of a vertex.

Implementation notes: N is not actually used yet, but it is “reserved” as the first type parameter for forward compatibility.

Methods

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

fn with_nodes(n: usize) -> Self where N: Default

Create a new Csr with n nodes.

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

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.

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

fn node_count(&self) -> usize

fn edge_count(&self) -> usize

fn is_directed(&self) -> bool

fn clear_edges(&mut self)

Remove all edges

fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> bool where 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.

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.

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

Computes in O(1) time.

Panics if the node a does not exist.

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

Computes in O(1) time.

Panics if the node a does not exist.

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

Computes in O(1) time.

Panics if the node a does not exist.

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: Debug, E: Debug, Ty: Debug, Ix: Debug> Debug for Csr<N, E, Ty, Ix>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

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

type NodeId = NodeIndex<Ix>

node identifier

type EdgeId = EdgeIndex

edge identifier

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<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix> where Ty: EdgeType,
        Ix: IndexType

type Neighbors = Neighbors<'a, Ix>

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

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

impl<N, E, Ty> NodeCompactIndexable for Csr<N, E, Ty> where Ty: EdgeType

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