Struct graphsearch::Graph
[−]
[src]
pub struct Graph<T> { /* fields omitted */ }
A graph, represeted by as a weighted
Adjacency list of Node
s
Methods
impl<T: PartialEq> Graph<T>
[src]
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 aVec
of Nodes. Weights are represented asi32
: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
- anusize
designating the start node, or row in the adjacency listtarget
- anT
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>>
&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
- anusize
designating the start node, or row in the adjacency listtarget
- anusize
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>>
&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
- anusize
designating the start node, or row in the adjacency listtarget
- anT
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>>
&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
- anusize
designating the start node, or row in the adjacency listtarget
- anusize
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
- anusize
designating the start node, or row in the adjacency listtarget
- anT
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>>
&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
- anusize
designating the start node, or row in the adjacency listtarget
- anusize
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
- anusize
designating the start node, or row in the adjacency listtarget
- an refT
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>>
&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
- anusize
designating the start node, or row in the adjacency listtarget
- anusize
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 aVecDeque<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
- Theusize
index for which we want to know the correspondingNode
Returns
An Optional Node
if the index supplied is within the bounds of the graph,
None
otherwise