pub struct List<E, Ix = u32>
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> List<E, Ix>
where Ix: IndexType,

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) -> 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) -> 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>(&mut self, edges: I) -> Ix
where I: Iterator<Item = (Ix, E)>,

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: Ix, b: 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<(Ix, Ix)>

Accesses the source and target of edge e

Computes in O(1)

source

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

source

pub fn contains_edge(&self, a: Ix, b: 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: Ix, b: 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> Build for List<E, Ix>
where Ix: IndexType,

source§

fn add_node(&mut self, _weight: ()) -> 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: Ix, b: 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: Ix, b: 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, Ix> Clone for List<E, Ix>
where E: Clone, Ix: Clone + IndexType,

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

source§

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

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: <List<E, Ix> as GraphBase>::NodeId) -> Option<&()>

source§

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

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: <List<E, Ix> as GraphBase>::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<(), Error>

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

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

source§

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

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

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

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

§

type EdgeType = Directed

The kind of edges in the graph.
source§

fn is_directed(&self) -> bool

source§

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

source§

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

§

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

source§

fn edges( self, a: <&'a List<E, Ix> as GraphBase>::NodeId ) -> <&'a List<E, Ix> as IntoEdges>::Edges

source§

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

source§

fn neighbors(self, a: Ix) -> <&'a List<E, Ix> as IntoNeighbors>::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> IntoNodeIdentifiers for &'a List<E, Ix>
where Ix: IndexType,

source§

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

source§

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

source§

fn node_count(&self) -> usize

Returns the number of nodes in the list

Computes in O(1) time.

source§

impl<E, Ix> NodeIndexable for List<E, Ix>
where 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: <List<E, Ix> as GraphBase>::NodeId) -> usize

Convert a to an integer index.
source§

fn from_index(&self, i: usize) -> <List<E, Ix> as GraphBase>::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 <List<E, Ix> as Visitable>::Map)

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

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

Auto Trait Implementations§

§

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

§

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

§

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

§

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

§

impl<E, Ix> UnwindSafe for List<E, Ix>
where E: UnwindSafe, Ix: 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, U> AsBindGroupShaderType<U> for T
where U: ShaderType, &'a T: for<'a> Into<U>,

source§

fn as_bind_group_shader_type(&self, _images: &RenderAssets<Image>) -> U

Return the T ShaderType for self. When used in AsBindGroup derives, it is safe to assume that all images in self exist.
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> Downcast<T> for T

source§

fn downcast(&self) -> &T

source§

impl<T> Downcast for T
where T: Any,

source§

fn into_any(self: Box<T>) -> Box<dyn Any>

Convert Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>. Box<dyn Any> can then be further downcast into Box<ConcreteType> where ConcreteType implements Trait.
source§

fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>

Convert Rc<Trait> (where Trait: Downcast) to Rc<Any>. Rc<Any> can then be further downcast into Rc<ConcreteType> where ConcreteType implements Trait.
source§

fn as_any(&self) -> &(dyn Any + 'static)

Convert &Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &Any’s vtable from &Trait’s.
source§

fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)

Convert &mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &mut Any’s vtable from &mut Trait’s.
source§

impl<T> DowncastSync for T
where T: Any + Send + Sync,

source§

fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>

Convert Arc<Trait> (where Trait: Downcast) to Arc<Any>. Arc<Any> can then be further downcast into Arc<ConcreteType> where ConcreteType implements Trait.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<S> FromSample<S> for S

source§

fn from_sample_(s: S) -> S

source§

impl<T> FromWorld for T
where T: Default,

source§

fn from_world(_world: &mut World) -> T

Creates Self using data from the given World.
source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
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> ToSample<U> for T
where U: FromSample<T>,

source§

fn to_sample_(self) -> U

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

impl<T> TypeData for T
where T: 'static + Send + Sync + Clone,

source§

impl<T> Upcast<T> for T

source§

fn upcast(&self) -> Option<&T>

source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<S, T> Duplex<S> for T
where T: FromSample<S> + ToSample<S>,

source§

impl<T> Settings for T
where T: 'static + Send + Sync,

source§

impl<T> WasmNotSend for T
where T: Send,

source§

impl<T> WasmNotSendSync for T

source§

impl<T> WasmNotSync for T
where T: Sync,