Struct AdjacencyNodeList

pub struct AdjacencyNodeList { /* private fields */ }

Sparse, node first, adjacency list

Space Complexity

• $O(|V|+|E|)$ for undirected graph(deprecated)
• $O(|V|+2|E|)$ for directed graph

Node Time Complexity

This structure has very good performance for nodes

• Insert: $O\left(1\right)$
• Query: $O\left(1\right)$
• Removal: $O\left(1\right)$
• Count: $O\left(1\right)$
• Neighbors: $O\left(1\right)$

Edge Time Complexity

This structure has linear complexity across the edges

• Insert edge: $O\left(1\right)$
• Query edge: $O\left(|V|\right)$
• Removal edge: $O\left(|V|\right)$
• Count edges: $O\left(|V|\right)$

Trait Implementations

impl Debug for AdjacencyNodeList

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

Formats the value using the given formatter.

impl Default for AdjacencyNodeList

fn default() -> Self

Returns the “default value” for a type.

impl<'a> GraphEngine<'a> for AdjacencyNodeList

type NeighborIterator = PlaceholderNodeIterator

According to a given vertex, find all neighbor nodes

type BridgeIterator = PlaceholderEdgeIterator

An iterator over the edges.

type NodeTraverser = PlaceholderNodeIterator

An iterator over the nodes.

type EdgeTraverser = PlaceholderNodeIterator

An iterator over the edges.

type BridgeTraverser = PlaceholderEdgeIterator

An iterator over the edges.

fn graph_kind(&self) -> GraphKind

Check the graph kind, it can be directed or undirected.

fn get_node(&self, node: NodeID) -> Result<NodeID, GraphError>

Check if the node exists, return the node id if exists.

fn all_nodes(&self) -> Self::NodeTraverser

Traverse all nodes in the graph.

fn all_neighbors(&'a self, node: NodeID) -> Self::NeighborIterator

Check if the node exists, return the node id if exists.

fn get_edge(&self, edge: EdgeID) -> Result<EdgeID, GraphError>

Check if the edge exists, return the node id if exists.

fn all_edges(&self) -> Self::EdgeTraverser

Get the edges of the graph.

fn get_bridge(&self, edge: EdgeID) -> Result<IndeterminateEdge, GraphError>

fn get_bridges(&'a self, from: NodeID, goto: NodeID) -> Self::BridgeIterator

Give all edges matching the start and end points

fn all_bridges(&self) -> Self::BridgeIterator

Get the edges of the graph.

fn count_nodes(&'a self) -> usize

Count the number of nodes in the graph.

fn get_outgoing(&'a self, node: usize) -> Self::NeighborIterator

Find all vertices ending at a given point

fn get_incoming(&'a self, node: usize) -> Self::NeighborIterator

Check if the node exists, return the node id if exists.

fn count_degree(&'a self, node: usize) -> NodeDegree

Check if the node exists, return the node id if exists.

fn count_edges(&'a self) -> usize

Count the number of edges in the graph.

fn size_hint(&self) -> usize

Query the total space occupied by the structure, return 0 if failed to query

impl MutableGraph for AdjacencyNodeList

fn insert_node(&mut self, node_id: usize) -> bool

Insert a node without any neighbors (edges).

fn create_node(&mut self) -> usize

Insert a node without any neighbors (edges).

fn remove_node_with_edges(&mut self, node_id: usize)

Remove the given node and all edges connected to it.

fn insert_edge_with_nodes<E: Edge>(&mut self, edge: E) -> EdgeInsertID

Insert edge to graph, if the nodes does not exist, also insert them.

fn remove_edge<E>(&mut self, edge: E)

where E: Into<EdgeQuery>,

Remove edge by given edge-id or start and end node-id.

fn remove_node(&mut self, node_id: usize)

Remove the given node.

fn insert_edge<E>(&mut self, edge: E) -> EdgeInsertID

where E: Edge,

Insert a edge between two nodes.

fn shrink(&mut self)

Remove invalid edges and nodes to improve the efficiency of subsequent queries.