Struct DirectedGraph

Source

pub struct DirectedGraph<N: NodeConstraints> { /* private fields */ }

Expand description

A generic directed graph data structure implemented with an adjacency list.

The graph uses a IndexMap to map each node to an IndexSet of its adjacent nodes (outgoing edges), ensuring efficient:

Node/edge lookups (O(1) average for hash map)
Duplicate edge prevention (via IndexSet)
Node/edge addition/removal

The node type N must implement the NodeConstraints trait for core operations.

Implementations§

Source §

impl<N: NodeConstraints> DirectedGraph<N>

Source

pub fn new() -> Self

Create a new empty directed graph.

§Examples

use directed_graph::DirectedGraph;
let graph: DirectedGraph<u32> = DirectedGraph::new();
assert_eq!(graph.node_count(), 0);

Source

pub fn contains(&self, n: &N) -> bool

Check if the graph contains a specific node.

§Arguments

n - Reference to the node to check for existence

§Returns

true if the node exists in the graph, false otherwise.

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node("Alice", vec![]);
assert!(graph.contains(&"Alice"));
assert!(!graph.contains(&"Bob"));

Source

pub fn add_node(&mut self, start: N, ends_vec: Vec<N>)

Add a node to the graph with a list of outgoing edges (adjacent nodes).

If the node already exists in the graph, the new edges are appended (duplicate edges are ignored). If the node does not exist, it is created with the provided outgoing edges.

§Arguments

start - The node to add to the graph (source node for the outgoing edges)
ends_vec - Vector of adjacent nodes (target nodes for the outgoing edges from start)

§Notes

The target nodes in ends_vec do not need to exist in the graph (orphaned edges are allowed)
Duplicate edges in ends_vec are automatically removed (via IndexSet)

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
// Add a new node with two outgoing edges
graph.add_node(1, vec![2, 3]);
// Append a new edge to an existing node (duplicate 3 is ignored)
graph.add_node(1, vec![3, 4]);
assert!(graph.get_adjacent_nodes(&1).unwrap().contains(&4));

Source

pub fn get_adjacent_nodes(&self, n: &N) -> Option<&NodeSet<N>>

Get the set of adjacent nodes (outgoing edges) for a specific node.

§Arguments

n - Reference to the node to query for adjacent nodes

§Returns

Some(&NodeSet<N>) if the node exists (containing all adjacent nodes), None otherwise.

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node(1, vec![2, 3]);
let adj = graph.get_adjacent_nodes(&1).unwrap();
assert!(adj.contains(&2) && adj.contains(&3));

Source

pub fn node_count(&self) -> usize

Get the total number of unique nodes in the graph.

§Returns

The count of nodes in the graph (length of the adjacency list).

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node(1, vec![2]);
graph.add_node(2, vec![3]);
assert_eq!(graph.node_count(), 2);

Source

pub fn edge_count(&self) -> usize

Get the total number of unique edges in the graph.

Counts all outgoing edges across all nodes (duplicate edges are not counted, via IndexSet).

§Returns

The total number of unique outgoing edges in the graph.

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node(1, vec![2, 3]);
graph.add_node(2, vec![3]);
assert_eq!(graph.edge_count(), 3);

Source

pub fn remove_node(&mut self, n: N) -> Option<NodeSet<N>>

Remove a node from the graph and return its outgoing edges (if the node existed).

Removes the node and all its outgoing edges from the adjacency list. Incoming edges to this node are not removed (they remain as orphaned edges from other nodes).

§Arguments

n - The node to remove from the graph

§Returns

Some(NodeSet<N>) if the node existed (containing its outgoing edges), None otherwise.

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node(1, vec![2, 3]);
let edges = graph.remove_node(1).unwrap();
assert_eq!(edges.len(), 2);
assert!(!graph.contains(&1));

Source

pub fn remove_edge(&mut self, start: &N, end: &N) -> bool

Remove a single outgoing edge from a source node to a target node.

§Arguments

start - The source node of the edge to remove
end - The target node of the edge to remove

§Returns

true if the edge existed and was removed, false otherwise (either the source node does not exist, or the edge does not exist).

§Examples

use directed_graph::DirectedGraph;
let mut graph = DirectedGraph::new();
graph.add_node(1, vec![2, 3]);
assert!(graph.remove_edge(&1, &3));
assert!(!graph.remove_edge(&1, &4));