Struct graph_search::Graph

pub struct Graph { /* private fields */ }

A graph is represeted by as a weighted Adjenceny matrix

Implementations

impl Graph

pub fn new(input: Vec<Vec<Option<i32>>>) -> Graph

new allows for initializing the graph struct with a given adjecency matrix

Arguments

• input - an adjecency matrix in made out of a two-dimensional Vec of weights. Weights are represented as i32:s and can thus be positive or negative numbers.

Example

 let rawgraph = vec![vec![Some(0), Some(20), Some(80), Some(50),     None,     None],
                     vec![   None,  Some(0),     None,     None,     None,     None],
                     vec![   None,     None,  Some(0),     None,     None,     None],
                     vec![   None,     None,     None,  Some(0), Some(50),     None],
                     vec![   None,     None, Some(20),     None,  Some(0), Some(50)],
                     vec![   None,     None,     None,     None,     None,  Some(0)]];
let g = Graph::new(rawgraph);

pub fn breadth_first_search( &self, start: usize, target: usize, ) -> Option<VecDeque<usize>>

breadth_first_search implements breadth first search from start to the target and returns the path found as a VecDeque<usize> of nodes. This is an optional type as there might not be a path.

NOTE as this is breadth first search this search ignores any assigned weight to nodes.

Arguments

• start - an usize designating the start node, or row in the adjecency matrix
• target - an usize designating the target node, or row in the adjecency matrix

Returns

Either the found path between start and target as a VecDeque of usize:s or None if there is no path.

pub fn depth_first_search( &self, start: usize, target: usize, ) -> Option<VecDeque<usize>>

depth_first_search implements depth first search from start to the target and returns the path found as a VecDeque<usize> of nodes. This is an optional type as there might not be a path.

NOTE as this is depth first search this search ignores any assigned weight to nodes.

Arguments

• start - an usize designating the start node, or row in the adjecency matrix
• target - an usize designating the target node, or row in the adjecency matrix

Returns

Either the found path between start and target as a VecDeque of usize:s or None if there is no path.