Struct List

pub struct List<E, Ix = DefaultIx>
where
    Ix: IndexType,
{ /* private fields */ }

An adjacency list with labeled edges.

Can be interpreted as a directed graph with unweighted nodes.

This is the most simple adjacency list you can imagine. Graph, in contrast, maintains both the list of successors and predecessors for each node, which is a different trade-off.

Allows parallel edges and self-loops.

This data structure is append-only (except for clear), so indices returned at some point for a given graph will stay valid with this same graph until it is dropped or clear is called.

Space consumption: O(|E|).

Implementations

impl<E, Ix: IndexType> List<E, Ix>

pub fn new() -> List<E, Ix>

Creates a new, empty adjacency list.

pub fn with_capacity(nodes: usize) -> List<E, Ix>

Creates a new, empty adjacency list tailored for nodes nodes.

pub fn clear(&mut self)

Removes all nodes and edges from the list.

pub fn edge_count(&self) -> usize

Returns the number of edges in the list

Computes in O(|V|) time.

pub fn add_node(&mut self) -> NodeIndex<Ix>

Adds a new node to the list. This allocates a new Vec and then should run in amortized O(1) time.

pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix>

Adds a new node to the list. This allocates a new Vec and then should run in amortized O(1) time.

pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>( &mut self, edges: I, ) -> NodeIndex<Ix>

Adds a new node to the list by giving its list of successors and the corresponding weigths.

pub fn add_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E, ) -> EdgeIndex<Ix>

Add an edge from a to b to the graph, with its associated data weight.

Return the index of the new edge.

Computes in O(1) time.

Panics if the source node does not exist.

Note: List allows adding parallel (“duplicate”) edges. If you want to avoid this, use .update_edge(a, b, weight) instead.

pub fn edge_endpoints( &self, e: EdgeIndex<Ix>, ) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>

Accesses the source and target of edge e

Computes in O(1)

pub fn edge_indices_from(&self, a: NodeIndex<Ix>) -> OutgoingEdgeIndices<Ix>

pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool

Lookups whether there is an edge from a to b.

Computes in O(e’) time, where e’ is the number of successors of a.

pub fn find_edge( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> Option<EdgeIndex<Ix>>

Lookups whether there is an edge from a to b.

Computes in O(e’) time, where e’ is the number of successors of a.

pub fn node_indices(&self) -> NodeIndices<Ix>

Returns an iterator over all node indices of the graph.

Consuming the whole iterator take O(|V|).

pub fn edge_indices(&self) -> EdgeIndices<'_, E, Ix>

Returns an iterator over all edge indices of the graph.

Consuming the whole iterator take O(|V| + |E|).

Trait Implementations

impl<E, Ix: IndexType> Build for List<E, Ix>

fn add_node(&mut self, _weight: ()) -> NodeIndex<Ix>

Adds a new node to the list. This allocates a new Vec and then should run in amortized O(1) time.

fn add_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E, ) -> Option<EdgeIndex<Ix>>

Add an edge from a to b to the graph, with its associated data weight.

Return the index of the new edge.

Computes in O(1) time.

Panics if the source node does not exist.

Note: List allows adding parallel (“duplicate”) edges. If you want to avoid this, use .update_edge(a, b, weight) instead.

fn update_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E, ) -> EdgeIndex<Ix>

Updates or adds an edge from a to b to the graph, with its associated data weight.

Return the index of the new edge.

Computes in O(e’) time, where e’ is the number of successors of a.

Panics if the source node does not exist.

impl<E: Clone, Ix> Clone for List<E, Ix>

where Ix: IndexType + Clone,

fn clone(&self) -> List<E, Ix>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E, Ix: IndexType> Data for List<E, Ix>

type NodeWeight = ()

type EdgeWeight = E

impl<E, Ix: IndexType> DataMap for List<E, Ix>

fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>

Accesses the weight of edge e

Computes in O(1)

fn node_weight(&self, n: Self::NodeId) -> Option<&()>

impl<E, Ix: IndexType> DataMapMut for List<E, Ix>

fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E>

Accesses the weight of edge e

Computes in O(1)

fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()>

impl<E, Ix> Debug for List<E, Ix>

where E: Debug, Ix: IndexType,

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

Formats the value using the given formatter.

impl<E: Default, Ix> Default for List<E, Ix>

where Ix: IndexType + Default,

fn default() -> List<E, Ix>

Returns the “default value” for a type.

impl<E, Ix: IndexType> EdgeCount for List<E, Ix>

fn edge_count(&self) -> usize

Returns the number of edges in the list

Computes in O(|V|) time.

impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>

where Ix: IndexType,

The adjacency matrix for List 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<E, Ix> GraphBase for List<E, Ix>

where Ix: IndexType,

type NodeId = Ix

node identifier

type EdgeId = EdgeIndex<Ix>

edge identifier

impl<E, Ix: IndexType> GraphProp for List<E, Ix>

type EdgeType = Directed

The kind of edges in the graph.

fn is_directed(&self) -> bool

impl<'a, Ix: IndexType, E> IntoEdgeReferences for &'a List<E, Ix>

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

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

fn edge_references(self) -> Self::EdgeReferences

impl<'a, Ix: IndexType, E> IntoEdges for &'a List<E, Ix>

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

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

impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix>

fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors

Returns an iterator of all nodes with an edge starting from a. Panics if a is out of bounds. Use List::edge_indices_from instead if you do not want to borrow the adjacency list while iterating.

type Neighbors = Neighbors<'a, E, Ix>

impl<'a, E, Ix: IndexType> IntoNodeIdentifiers for &'a List<E, Ix>

type NodeIdentifiers = NodeIndices<Ix>

fn node_identifiers(self) -> NodeIndices<Ix>

impl<'a, Ix: IndexType, E> IntoNodeReferences for &'a List<E, Ix>

type NodeRef = Ix

type NodeReferences = NodeIndices<Ix>

fn node_references(self) -> Self::NodeReferences

impl<E, Ix: IndexType> NodeCount for List<E, Ix>

fn node_count(&self) -> usize

Returns the number of nodes in the list

Computes in O(1) time.

impl<E, Ix: IndexType> NodeIndexable for List<E, Ix>

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

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

impl<E, Ix> Visitable for List<E, Ix>

where 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<E, Ix: IndexType> NodeCompactIndexable for List<E, Ix>