Trait Search 

pub trait Search<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    // Required methods
    fn has_path(&self, start: usize, target: usize) -> Result<bool, SearchError>;
    fn bfs_path(
        &self,
        start: usize,
        target: usize,
    ) -> Result<Option<Vec<usize>>, SearchError>;
    fn dfs(
        &self,
        current: usize,
        target: usize,
        visited: &mut HashSet<usize>,
    ) -> Result<bool, SearchError>;
    fn has_node(&self, node: usize) -> Result<bool, SearchError>;
    fn has_cycle(&self) -> Result<bool, SearchError>;
    fn has_cycle_directed(
        &self,
        node: usize,
        visited: &mut HashSet<usize>,
        recursion_stack: &mut HashSet<usize>,
    ) -> Result<bool, SearchError>;
    fn has_cycle_undirected(
        &self,
        node: usize,
        parent: Option<usize>,
        visited: &mut HashSet<usize>,
    ) -> Result<bool, SearchError>;
}

Trait for graph search operations.

Provides fundamental algorithms for graph traversal and analysis with error handling.

Type Parameters

• W: Edge weight type, must be copyable, have a default value, and support partial equality.
• N: Node data type, must be clonable, equatable, hashable, and debuggable.
• E: Edge data type, must be clonable and debuggable.

Examples

use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::search::Search;

let mut graph = Graph::<u32, u32, ()>::new(true);
let a = graph.add_node(0);
let b = graph.add_node(1);
graph.add_edge(a, b, 1, ()).unwrap();

assert!(graph.has_path(a, b).unwrap());
assert_eq!(graph.bfs_path(a, b).unwrap(), Some(vec![a, b]));

Required Methods

fn has_path(&self, start: usize, target: usize) -> Result<bool, SearchError>

Checks if a path exists between two nodes using DFS.

Traverses the graph depth-first to determine if there is a valid path from start to target.

Arguments

• start: The ID of the starting node.
• target: The ID of the target node.

Returns

• Ok(bool): true if a path exists, false otherwise.
• Err(SearchError): If either start or target is not a valid node.

Examples

use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::search::Search;

let mut graph = Graph::<u32, u32, ()>::new(true);
let a = graph.add_node(0);
let b = graph.add_node(1);
let c = graph.add_node(2);
graph.add_edge(a, b, 1, ()).unwrap();
graph.add_edge(b, c, 1, ()).unwrap();

assert!(graph.has_path(a, c).unwrap());
assert!(!graph.has_path(c, a).unwrap()); // Directed graph

fn bfs_path( &self, start: usize, target: usize, ) -> Result<Option<Vec<usize>>, SearchError>

Finds the shortest path between nodes using BFS.

Uses breadth-first search to find the shortest unweighted path from start to target.

Arguments

• start: The ID of the starting node.
• target: The ID of the target node.

Returns

• Ok(Option<Vec<usize>>): A vector of node IDs representing the shortest path, or None if no path exists.
• Err(SearchError): If either start or target is not a valid node.

Examples

use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::search::Search;

let mut graph = Graph::<u32, (), ()>::new(true);
let nodes = (0..4).map(|i| graph.add_node(())).collect::<Vec<_>>();
graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
graph.add_edge(nodes[1], nodes[2], 1, ()).unwrap();
graph.add_edge(nodes[0], nodes[3], 1, ()).unwrap();

assert_eq!(
    graph.bfs_path(nodes[0], nodes[2]).unwrap(),
    Some(vec![nodes[0], nodes[1], nodes[2]])
);

fn dfs( &self, current: usize, target: usize, visited: &mut HashSet<usize>, ) -> Result<bool, SearchError>

Performs a recursive DFS to check for a path between nodes.

Internal helper method for path checking, not typically called directly by users.

Arguments

• current: The current node ID in the recursion.
• target: The target node ID to find.
• visited: A mutable reference to a set tracking visited nodes.

Returns

• Ok(bool): true if a path to target is found, false otherwise.
• Err(SearchError): If current or target is not a valid node.

fn has_node(&self, node: usize) -> Result<bool, SearchError>

Checks if a node exists in the graph.

Verifies whether a node with the given ID is present in the graph.

Arguments

• node: The ID of the node to check.

Returns

• Ok(bool): true if the node exists, false otherwise.
• Err(SearchError): Never returned in this implementation, but included for consistency.

Examples

use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::search::Search;

let mut graph = Graph::<i32, (), ()>::new(false);
let n0 = graph.add_node(());
assert!(graph.has_node(n0).unwrap());
assert!(!graph.has_node(999).unwrap());

fn has_cycle(&self) -> Result<bool, SearchError>

Detects whether the graph contains any cycles.

Uses DFS-based algorithms tailored to the graph’s directionality:

• Directed graphs: Uses a recursion stack to detect back edges.
• Undirected graphs: Uses parent tracking to avoid false positives from bidirectional edges.

Returns

• Ok(bool): true if a cycle is detected, false otherwise.
• Err(SearchError): If an invalid node is encountered during traversal.

Examples

use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::search::Search;

let mut graph = Graph::<u32, (), ()>::new(true);
let nodes = (0..3).map(|i| graph.add_node(())).collect::<Vec<_>>();
graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
graph.add_edge(nodes[1], nodes[2], 1, ()).unwrap();
graph.add_edge(nodes[2], nodes[0], 1, ()).unwrap();
assert!(graph.has_cycle().unwrap());

fn has_cycle_directed( &self, node: usize, visited: &mut HashSet<usize>, recursion_stack: &mut HashSet<usize>, ) -> Result<bool, SearchError>

Helper method for cycle detection in directed graphs.

Uses DFS with a recursion stack to detect cycles in directed graphs.

Arguments

• node: The current node ID.
• visited: A mutable reference to a set of visited nodes.
• recursion_stack: A mutable reference to a set tracking the current recursion path.

Returns

• Ok(bool): true if a cycle is detected, false otherwise.
• Err(SearchError): If node is not a valid node.

fn has_cycle_undirected( &self, node: usize, parent: Option<usize>, visited: &mut HashSet<usize>, ) -> Result<bool, SearchError>

Helper method for cycle detection in undirected graphs.

Uses DFS with parent tracking to detect cycles in undirected graphs.

Arguments

• node: The current node ID.
• parent: The ID of the parent node in the DFS tree, or None if root.
• visited: A mutable reference to a set of visited nodes.

Returns

• Ok(bool): true if a cycle is detected, false otherwise.
• Err(SearchError): If node is not a valid node.

Implementors

impl<W, N, E> Search<W, N, E> for Graph<W, N, E>

where W: Copy + Default + PartialEq, N: Clone + Eq + Hash + Debug, E: Clone + Default + Debug,