Struct hadean_std::graph::Graph

pub struct Graph<V, E> where V: ProcessSendable, E: ProcessSendable {
    // some fields omitted
}

A scalable distributed graph datastructure. Graph<V,E> is a graph datastructure using an adjacency list representation.

Graph is parameterized over:

• Associated data V for nodes and E for edges. The associated data can be of arbitrary type.

The graph uses O(|V| + |E|) space, and allows fast node and edge insert, efficient graph search and graph algorithms.

Here's an example of building a graph with directed edges, and running 30 iterations of pagerank on it:

use hadean_std::graph::{GraphConstructor,Graph,GraphInterpreter};

let mut graph_constructor: GraphConstructor<String,_,(),()> = GraphConstructor::new(|_|());
graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
let (graph, graph_interpreter): (Graph<(),()>, GraphInterpreter<String>) = graph_constructor.construct();
let damping = 0.85f64;
let iterations = 30;
let graph: Graph<((),f64),()> = graph.pagerank(damping, iterations);
let graph: Graph<f64,()> = graph.map(move |vertex| vertex.1, move |edge| edge);
let rankmap: HashMap<String, f64> = graph_interpreter.interpret(graph);
for (name,score) in rankmap {
    println!("{}: {}", name, score);
}

Methods

impl<V, E> Graph<V, E> where V: ProcessSendable, E: ProcessSendable

fn new() -> Graph<V, E>

Constructs a new, empty Graph<V,E>.

fn add_vertex(&mut self, v: V)

Adds a vertex with associated data v.

fn add_edge(&mut self, a: usize, b: usize, e: E)

Adds an edge between vertices a and b, with associated data e. Vertices a and b must have already been added.

fn num_vertices(&self) -> usize

Returns the number of vertices added to the graph.

fn num_edges(&self) -> usize

Returns the number of edges added to the graph.

fn map<VM, EM, V1, E1>(self, vertex_map: VM, edge_map: EM) -> Graph<V1, E1> where VM: Fn(V) -> V1 + ProcessSendable, EM: Fn(E) -> E1 + ProcessSendable, V1: ProcessSendable, E1: ProcessSendable

Map the associated data of vertices and edges using vertex_map and edge_map respectively.

fn step<F1, F2, M>(&mut self, send: F1, receive: F2) where F1: Fn(V, EdgeIter<E, M>) + ProcessSendable, F2: Fn(V, MessageIter<M>) -> V + ProcessSendable, M: ProcessSendable

Run a pregel-like superstep

fn step_reduce<F1, F2, F3, M>(&mut self, send: F1, initial: M, reduce: F2, receive: F3) where F1: Fn(V, EdgeIter<E, M>) + ProcessSendable, F2: Fn(M, M) -> M + ProcessSendable, F3: Fn(V, M) -> V + ProcessSendable, M: ProcessSendable

Run a pregel-like superstep

Examples

let mut graph_constructor: GraphConstructor<String,_,(),()> = GraphConstructor::new(|_|());
graph_constructor.push(String::from("http://google.com"), String::from("https://hadean.com"), ());
graph_constructor.push(String::from("http://bbc.co.uk"), String::from("https://hadean.com"), ());
graph_constructor.push(String::from("https://hadean.com"), String::from("http://alecmocatta.com"), ());
let (graph, graph_interpreter): (Graph<(),()>, GraphInterpreter<String>) = graph_constructor.construct();
let damping = 0.85f64;
let iterations = 30;
let num_vertices = self.num_vertices();
let initial = 1.0/num_vertices as f64;
let mut graph: Graph<(V,f64),E> = self.map(move |vertex| (vertex,initial), move |edge| edge);
for _ in 0..iterations {
    graph.step(
        move |(_vertex,score), edges| {
            let out = score / edges.len() as f64;
            for mut edge in edges {
                edge.send(out);
            }
        }, move |(vertex,score), messages| {
            let mut sum = 0f64;
            for val in messages {
                sum += val;
            }
            (vertex,(1.0-damping) / num_vertices as f64 + damping * sum)
        }
    )
}

impl<V, E> Graph<V, E> where V: ProcessSendable, E: ProcessSendable

fn pagerank(self, damping: f64, iterations: usize) -> Graph<(V, f64), E> where V: ProcessSendable, (V, f64): ProcessSendable, E: ProcessSendable

Run pagerank on the graph.