Struct petgraph::csr::Csr[][src]

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

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. [CSR]: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)

Methods

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

Create an empty Csr.

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
[src]

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
[src]

Remove all edges

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

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.

Computes in O(log |V|) time.

Panics if the node a does not exist.

Computes in O(1) time.

Panics if the node a does not exist.

Computes in O(1) time.

Panics if the node a does not exist.

Computes in O(1) time.

Panics if the node a does not exist.

Important traits for Edges<'a, 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>
[src]

Formats the value using the given formatter. Read more

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

Returns the "default value" for a type. Read more

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

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

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

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

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

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

node identifier

edge identifier

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

The associated map type

Create a new visitor 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
[src]

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
[src]

Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more

Convert a to an integer index.

Convert i to a node index

impl<N, E, Ty, Ix> NodeCompactIndexable for Csr<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Csr<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

The returned type after indexing.

Performs the indexing (container[index]) operation.

impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Csr<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

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

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

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

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

The kind edges in the graph.

Auto Trait Implementations

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

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