Struct graphsearch::Graph

pub struct Graph<T> { /* fields omitted */ }

A graph, represeted by as a weighted Adjacency list of Nodes

Methods

impl<T: PartialEq> Graph<T>

fn new(input: Vec<Node<T>>) -> Graph<T>

new allows for initializing the graph struct with a given adjacency list

Arguments

• input - an adjacency list in made out of a Vec of Nodes. Weights are represented as i32:s and can thus be positive or negative numbers.

Example

use graphsearch::{Graph, Node, Vertex};
let rawgraph = vec![Node{content: "Helsinki",
                         adjacent: vec![Vertex{cost: 20, node: 1},
                                        Vertex{cost: 50, node: 2},
                                        Vertex{cost: 10, node: 3}]},
                    Node{content: "Turku",
                         adjacent: Vec::new()},
                    Node{content: "Tampere",
                         adjacent: vec![Vertex{cost: 50, node: 6}]},
                    Node{content: "Jyväskylä",
                         adjacent: vec![Vertex{cost: 20, node: 4}]},
                    Node{content: "Oulu",
                         adjacent: vec![Vertex{cost: 20, node: 3},
                                        Vertex{cost: 30, node: 6}]},
                    Node{content: "Rovaniemi",
                         adjacent: Vec::new()},
                    Node{content: "Vasa",
                         adjacent: Vec::new()}];
let g = Graph::new(rawgraph);

fn search(&self, start: usize, target: T) -> Option<VecDeque<usize>>

search promises to use a correct method, i.e. one which will return the best path between start and target if there is a valid path between them. Which search method applied is not specified but currently Dijkstras algorithm is used. The path found is returned as a VecDeque<usize> of nodes. The VecDeque<usize> is an optional type as there might not be a path.

Arguments

• start - an usize designating the start node, or row in the adjacency list
• target - an T designating the target node

Returns

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

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

search_using_index promises to use a correct method, i.e. one which will return the best path between the start index and target index if there is a valid path between them. Which search method applied is not specified but currently Dijkstras algorithm is used. The path found is returned as a VecDeque<usize> of nodes. The VecDeque<usize> is an optional type as there might not be a path.

Arguments

• start - an usize designating the start node, or row in the adjacency list
• target - an usize designating the target node, or row in the adjacency list

Returns

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

fn breadth_first_search(
    &self,
    start: usize,
    target: T
) -> 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 adjacency list
• target - an T designating the target node

Returns

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

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

breadth_first_search implements breadth first search from the start index 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 adjacency list
• target - an usize designating the target node, or row in the adjacency list

Returns

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

fn depth_first_search(&self, start: usize, target: T) -> 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 adjacency list
• target - an T designating the target node

Returns

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

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

depth_first_search_using_index implements depth first search from the start index to the target index 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 adjacency list
• target - an usize designating the target node, or row in the adjacency list

Returns

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

fn dijkstra(&self, start: usize, target: &T) -> Option<VecDeque<usize>>

dijkstra implements Dijkstras algorithm for 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.

Arguments

• start - an usize designating the start node, or row in the adjacency list
• target - an ref T designating the target node

Returns

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

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

dijkstra_using_index implements Dijkstras algorithm for search from the start index to the target index and returns the path found as a VecDeque<usize> of nodes. This is an optional type as there might not be a path.

Arguments

• start - an usize designating the start node, or row in the adjacency list
• target - an usize designating the target node, or row in the adjacency list

Returns

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

fn cost_of_path(&self, path: &VecDeque<usize>) -> i32

cost_of_path takes a path returned from any of the search functions and calculates the cost of the path.

Arguments

• path - a borrowed reference to a VecDeque<usize> representing a path through the graph

Returns

The cost of traversing said path represented as an i32

fn node_to_index(&self, node: Node<T>) -> Option<usize>

node_to_index takes an Node (from the graph) and returns its index, if it exists in the graph.

Note: This operation searches the graph array for the input node and is thus an (ammortized) O(N) computation.

Arguments

• node - The node for which we want an index

Returns

An Optional index, either None if the node does not exist in the graph or Some(index)

fn index_to_node(&self, index: usize) -> Option<&Node<T>>

index_to_node takes an index (from the graph) and returns the node at the index, if the index is within the bounds of the graph. This is equivalent to accessing the underlying vector and thus is of O(1) complexity

Arguments

• index - The usize index for which we want to know the corresponding Node

Returns

An Optional Node if the index supplied is within the bounds of the graph, None otherwise