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>
impl<E, Ix: IndexType> List<E, Ix>
sourcepub fn with_capacity(nodes: usize) -> List<E, Ix>
pub fn with_capacity(nodes: usize) -> List<E, Ix>
Creates a new, empty adjacency list tailored for nodes
nodes.
sourcepub fn edge_count(&self) -> usize
pub fn edge_count(&self) -> usize
Returns the number of edges in the list
Computes in O(|V|) time.
sourcepub fn add_node(&mut self) -> NodeIndex<Ix>
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.
sourcepub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix>
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.
sourcepub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
&mut self,
edges: I,
) -> NodeIndex<Ix>
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.
sourcepub fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E,
) -> EdgeIndex<Ix>
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.
sourcepub fn edge_endpoints(
&self,
e: EdgeIndex<Ix>,
) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
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> ⓘ
sourcepub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
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
.
sourcepub fn find_edge(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
) -> Option<EdgeIndex<Ix>>
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
.
sourcepub fn node_indices(&self) -> NodeIndices<Ix> ⓘ
pub fn node_indices(&self) -> NodeIndices<Ix> ⓘ
Returns an iterator over all node indices of the graph.
Consuming the whole iterator take O(|V|).
sourcepub fn edge_indices(&self) -> EdgeIndices<'_, E, Ix> ⓘ
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>
impl<E, Ix: IndexType> Build for List<E, Ix>
source§fn add_node(&mut self, _weight: ()) -> NodeIndex<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.
source§fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E,
) -> Option<EdgeIndex<Ix>>
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>
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, Ix: IndexType> Data for List<E, Ix>
impl<E, Ix: IndexType> Data for List<E, Ix>
type NodeWeight = ()
type EdgeWeight = E
source§impl<E, Ix: IndexType> DataMapMut for List<E, Ix>
impl<E, Ix: IndexType> DataMapMut for List<E, Ix>
source§impl<E, Ix: IndexType> EdgeCount for List<E, Ix>
impl<E, Ix: IndexType> EdgeCount for List<E, Ix>
source§fn edge_count(&self) -> usize
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,
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
type AdjMatrix = FixedBitSet
source§fn adjacency_matrix(&self) -> FixedBitSet
fn adjacency_matrix(&self) -> FixedBitSet
source§fn is_adjacent(
&self,
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
) -> bool
fn is_adjacent( &self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> bool
source§impl<'a, Ix: IndexType, E> IntoEdgeReferences for &'a List<E, Ix>
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
source§impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix>
impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix>
source§impl<'a, E, Ix: IndexType> IntoNodeIdentifiers for &'a List<E, Ix>
impl<'a, E, Ix: IndexType> IntoNodeIdentifiers for &'a List<E, Ix>
type NodeIdentifiers = NodeIndices<Ix>
fn node_identifiers(self) -> NodeIndices<Ix> ⓘ
source§impl<'a, Ix: IndexType, E> IntoNodeReferences for &'a List<E, 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
source§impl<E, Ix: IndexType> NodeCount for List<E, Ix>
impl<E, Ix: IndexType> NodeCount for List<E, Ix>
source§fn node_count(&self) -> usize
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>
impl<E, Ix: IndexType> NodeIndexable for List<E, Ix>
source§fn node_bound(&self) -> usize
fn node_bound(&self) -> usize
source§fn from_index(&self, i: usize) -> Self::NodeId
fn from_index(&self, i: usize) -> Self::NodeId
i
to a node index. i
must be a valid value in the graph.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>where
Ix: RefUnwindSafe,
E: RefUnwindSafe,
impl<E, Ix> Send for List<E, Ix>
impl<E, Ix> Sync for List<E, Ix>
impl<E, Ix> Unpin for List<E, Ix>
impl<E, Ix> UnwindSafe for List<E, Ix>where
Ix: UnwindSafe,
E: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)