Struct petgraph::adj::List

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

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§

source§

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

source

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

Creates a new, empty adjacency list.

source

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

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

source

pub fn clear(&mut self)

Removes all nodes and edges from the list.

source

pub fn edge_count(&self) -> usize

Returns the number of edges in the list

Computes in O(|V|) time.

source

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.

source

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.

source

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.

source

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.

source

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)

source

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

source

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.

source

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.

source

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

Returns an iterator over all node indices of the graph.

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

source

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§

source§

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

source§

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.

source§

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.

source§

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.

source§

impl<E: Clone, Ix> Clone for List<E, Ix>
where Ix: IndexType + Clone,

source§

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

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§

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

source§

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

source§

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

Accesses the weight of edge e

Computes in O(1)

source§

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

source§

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

source§

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

Accesses the weight of edge e

Computes in O(1)

source§

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

source§

impl<E, Ix> Debug for List<E, Ix>
where E: Debug, Ix: IndexType,

source§

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

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

impl<E: Default, Ix> Default for List<E, Ix>
where Ix: IndexType + Default,

source§

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

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

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

source§

fn edge_count(&self) -> usize

Returns the number of edges in the list

Computes in O(|V|) time.

source§

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

fn adjacency_matrix(&self) -> FixedBitSet

Create the adjacency matrix
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§

impl<E, Ix> GraphBase for List<E, Ix>
where Ix: IndexType,

§

type NodeId = Ix

node identifier
§

type EdgeId = EdgeIndex<Ix>

edge identifier
source§

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

§

type EdgeType = Directed

The kind of edges in the graph.
source§

fn is_directed(&self) -> bool

source§

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

source§

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

§

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

source§

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

source§

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

source§

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>

source§

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

source§

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

source§

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

source§

fn node_count(&self) -> usize

Returns the number of nodes in the list

Computes in O(1) time.

source§

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

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

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

impl<E, Ix> Visitable for List<E, Ix>
where 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§

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

Auto Trait Implementations§

§

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

§

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

§

impl<E, Ix> Send for List<E, Ix>
where Ix: Send, E: Send,

§

impl<E, Ix> Sync for List<E, Ix>
where Ix: Sync, E: Sync,

§

impl<E, Ix> Unpin for List<E, Ix>
where Ix: Unpin, E: Unpin,

§

impl<E, Ix> UnwindSafe for List<E, Ix>
where Ix: UnwindSafe, E: UnwindSafe,

Blanket Implementations§

source§

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

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

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

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

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

source§

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

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

default unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. 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 T
where 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> ToOwned for T
where 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 T
where 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 T
where 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.