Struct petgraph::csr::Csr

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

source§

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

source

pub fn new() -> Self

Create an empty `Csr`.

source

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,

source

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

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

source

source

source

source

Remove all edges

source

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

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

source

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.

source

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.

source

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

Computes in O(1) time.

Panics if the node `a` does not exist.

source

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

Computes in O(1) time.

Panics if the node `a` does not exist.

source

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

Computes in O(1) time.

Panics if the node `a` does not exist.

source

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§

source§

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

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from `source`. Read more
source§

§

§

source§

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

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

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

source§

fn edge_count(&self) -> usize

Return the number of edges in the graph.
source§

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()`.

§

source§

source§

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. Read more
source§

§

node identifier
§

edge identifier
source§

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

source§

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

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

Performs the indexing (`container[index]`) operation. Read more
source§

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

source§

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

Performs the mutable indexing (`container[index]`) operation. Read more
source§

§

§

source§

source§

§

source§

source§

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

source§

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

§

source§

§

source§

source§

§

§

source§

source§

source§

source§

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

source§

fn node_bound(&self) -> usize

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

fn to_index(&self, a: Self::NodeId) -> usize

Convert `a` to an integer index.
source§

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

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

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

§

type Map = FixedBitSet

The associated map type
source§

fn visit_map(&self) -> FixedBitSet

Create a new visitor map
source§

fn reset_map(&self, map: &mut Self::Map)

Reset the visitor map (and resize to new size of graph if needed)
source§

§

§

§

§

§

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the `TypeId` of `self`. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls `U::from(self)`.

That is, this conversion is whatever the implementation of `From<T> for U` chooses to do.

source§

impl<T> Pointable for T

source§

const ALIGN: usize = mem::align_of::<T>()

The alignment of pointer.
§

type Init = T

The type for initializers.
source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.