Struct Graph

pub struct Graph { /* private fields */ }

Graph data structure

This create implements a Graph data structure

Implementations

impl Graph

pub fn new(num_nodes: usize, routes: Vec<(usize, usize)>) -> Self

Create a new graph with the given routes tuple(current, neighbor) current <— neighbor

Example

use flex_algo::Graph;
 
let graph = Graph::new(6, vec![(1, 0), (2, 1), (2, 5), (0, 3), (4, 3), (3, 5), (4, 5)]);
println!("graph: {:?}", graph);

pub fn is_acyclic_bfs(&self) -> bool

Breadth First Search algorithm to check if it’s an acyclic graph,

Example

use flex_algo::Graph;
 
let graph = Graph::new(6, vec![(1, 0), (2, 1), (2, 5), (0, 3), (4, 3), (3, 5), (4, 5)]);
println!("graph: {:?}", graph);
assert_eq!(graph.is_acyclic_bfs(), true);
 

pub fn is_acyclic_top_sort(&mut self) -> bool

Topological Sort algorithm to check if it’s an acyclic graph

Example

use flex_algo::Graph;
 
let mut graph = Graph::new(6, vec![(1, 0), (2, 1), (2, 5), (0, 3), (4, 3), (3, 5), (4, 5)]);
println!("graph: {:?}", graph);
assert_eq!(graph.is_acyclic_top_sort(), true);
 

pub fn breadth_first_search(&self, start: usize) -> Vec<usize>

Return the path by breadth first search algo for the graph

Example

use flex_algo::Graph;
 
let mut graph = Graph::new(6, vec![(1, 0), (2, 1), (2, 5), (0, 3), (4, 3), (3, 5), (4, 5)]);
let visit = graph.breadth_first_search(5);
assert_eq!(visit, vec![5, 4, 3, 0, 1, 2]);
 

pub fn depth_first_search(&self, vertex: usize) -> Vec<usize>

Return the path by depth first search algo for the graph

Example

use flex_algo::Graph;
 
let graph = Graph::new(8, vec![
    (5, 4), (2, 4), (6, 4), 
    (7, 5), (0, 2), (1, 2), (3, 6)
]);
let visit = graph.depth_first_search(4);
 
assert_eq!(visit, vec![7, 5, 0, 1, 2, 3, 6, 4]);

Trait Implementations

impl Debug for Graph

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

Formats the value using the given formatter.