Struct graph::Graph

pub struct Graph<'a, T, V> {
    // some fields omitted
}

Base Graph implementation

Methods

impl<'a, T, V> Graph<'a, T, V>

fn new() -> Graph<'a, T, V>

Create a new Graph

• T is the data type to be stored on the Nodes
• V is the data type to be stored on the Edges

fn get(&self, index: NodeIdentifier) -> &T

Get the value for the given NodeIdentifier

fn insert(&mut self, value: T) -> NodeIdentifier

Insert a value into the graph, returns the node identifier

Example

use graph::Graph;

let mut g: Graph<int, ()> = Graph::new();
let n1 = g.insert(5i);
assert!(*g.get(n1) == 5i);

fn connect(&mut self, from_index: NodeIdentifier, to_index: NodeIdentifier, data: V)

Connect two nodes in the graph.

This is a directed edge, with the edge going from from_index going to to_index. The data is attached to the edge.

fn connected(&self, from_index: NodeIdentifier, to_index: NodeIdentifier) -> bool

Test if two nodes are connected

True if the node represented by from_index has an edge from it to the node identified by to_index.

fn connection(&self, from_index: NodeIdentifier, to_index: NodeIdentifier) -> Option<&Edge<V>>

Get the edge between nodes.

None is used to imply that there is no edge between these nodes.

fn connections(&self, for_node: NodeIdentifier) -> &Vec<Edge<V>>

Get a complete list of edges from the node indentified by for_node

fn visit_breadth_first(&self, from_index: NodeIdentifier, visitor: |NodeIdentifier, &T| -> bool)

Traverse the graph, visiting each node directly, or indirectly, connected to the node identified by from_index.

Calls visitor with the value of each node on the trip, visiting sibling nodes first before decending deeper into the graph. In the event of cycles, each node is visited only once.

fn iter(&'a self) -> Items<'a, T>

Iterate over the nodes of the graph

fn node_count(&self) -> uint

Get the number of nodes in the graph

impl<'a, T: Eq, V> Graph<'a, T, V>

fn bfs(&self, from_node: NodeIdentifier, wanted: T) -> Option<NodeIdentifier>

Search the graph for a node with the value wanted. Returns true if the value is in the graph, false otherwise.

Starting at from_node, traverse the graph, breadth first looking for the wanted value.

fn contains(&self, value: T) -> Option<NodeIdentifier>

Searches the graph for the first node with the value given.

Note that this is different from bfs which conserns itself with connectedness.

fn contains_ref(&self, value: &T) -> Option<NodeIdentifier>

impl<'a, T: Clone, V> Graph<'a, T, V>

fn insert_all(&mut self, values: &[T]) -> Vec<NodeIdentifier>

Insert a slice of values into the graph

Inserts clones of each of the values in the slice given into the graph Returns a vector of identifiers for the nodes inserted, in the order of the values that were input.

impl<'a, T, V: Clone> Graph<'a, T, V>

fn connect_all(&mut self, connections: &[(NodeIdentifier, NodeIdentifier, V)])

Connects many nodes together

Each tuple in the input makes a new connection, with the first element being the from node, the second being a target node and the third being the data stored on the created edge.

Note that the data will be cloned onto the edge.

impl<'a, T, V: Clone + Ord + PartialOrd + Eq + Unsigned> Graph<'a, T, V>

fn shortest_path(&self, from_node: NodeIdentifier, to_node: NodeIdentifier) -> Option<ShortestPathResult<V>>

Finds the shortest path between two nodes.

Uses Dijkstra's shortest path to connect two nodes with the least cost. Edge data is used as the "cost" metric, where a greater value incurs more cost.

The returned Option has Some if a route can be calculated, containing a structure that has the path taken and the total cost of the path or None if there was no path between nodes.

Trait Implementations

impl<'a, T: Show, V: Show> Show for Graph<'a, T, V>

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