Struct Graph

pub struct Graph<'a, N> { /* private fields */ }

This structure holds a graph in the Compressed Sparse Row format for compression of data size. This graph is represented via Memory Mapping, allowing the graph to be loaded into memory as required. This makes it possible to load any-size graphs, even those that do not fit into memory!

Implementations

impl<'a, N> Graph<'a, N>

where N: ValidGraphType + 'a,

pub fn from_txt_adjacency_list<T>( stream: T, folder_name: &str, ) -> Result<Graph<'a, N>, Error>

where T: Read + Sized,

Convenience method for reading an input stream in text format. Each line should contain two numbers, separated by a space. The graph will be converted to the underlying CSR representation, and stored in folder_name.

Examples found in repository

examples/from_txt.rs (line 15)

fn main() {
    let (input_graph, output_directory) = {
        let args = std::env::args().skip(1).collect::<Vec<_>>();

        if args.len() != 2 {
            println!("Usage: bfs <converted graph directory> <output directory>");
            return;
        }

        (args[0].clone(), args[1].clone())
    };

    let source_file = std::fs::File::open(input_graph).unwrap();

    graph_csr::Graph::<u32>::from_txt_adjacency_list(source_file, &output_directory).unwrap();
}

pub fn from_binary_adjancency<T>( stream: T, destination_folder_name: &str, ) -> Result<Graph<'a, N>, Error>

where T: Read + Sized,

Same as from_txt_adjacency, except this time it assumes the edge list to be in binary representation.

pub fn from_adjacency_list<T>( stream: T, folder_name: &str, ) -> Result<Graph<'a, N>, Error>

where T: Iterator<Item = Result<(N, N)>> + Sized,

Given a SORTED (by source) adjancency list file source_file_name, transforms this file into the underlying binary representation in CSR and returns a version of the Graph in this format. The graph will be stored in folder_name.

pub fn load_graph(graph_folder: &str) -> Result<Graph<'a, N>, Error>

Loads a graph from the underlying representation and returns it as a Graph struct.

Examples found in repository

examples/wcc.rs (line 21)

fn main() {
    let (input_graph, output_file) = {
        let args = std::env::args().skip(1).collect::<Vec<_>>();

        if args.len() != 1 && args.len() != 2 {
            println!("Usage: wcc <converted graph directory> [output_file]");
            return;
        }

        let output = {
            if args.len() == 2 {
                Some(args[1].clone())
            } else {
                None
            }
        };

        (args[0].clone(), output)
    };

    let graph = graph_csr::Graph::<u32>::load_graph(&input_graph).unwrap();

    let mut compute_graph = graph_csr::compute::ComputeGraph::<u32, u32>::new(&graph);

    // Initialize
    compute_graph.fill_active(true);
    for i in 0..graph.n_nodes() {
        compute_graph.set_data(i, i as u32);
    }
    compute_graph.step(); // Set data

    let mut i = 0;
    while compute_graph.n_active() > 0 {
        let time_start = std::time::Instant::now();
        compute_graph.push(|src, dst| graph_csr::compute::helper::atomic_min(src, dst, |v| v));
        let time_end = std::time::Instant::now();
        compute_graph.step();

        i += 1;
        println!(
            "Iteration {} took {}ms",
            i,
            (time_end - time_start).as_millis()
        );
    }

    // Print results
    print!("[ ");
    for (idx, data) in compute_graph
        .get_data_as_slice()
        .iter()
        .enumerate()
        .take(30)
    {
        print!(
            "{}:{}, ",
            idx,
            data.load(std::sync::atomic::Ordering::Relaxed)
        );
    }
    println!("]");

    // Save file
    if let Some(output_file) = output_file {
        println!("Saving file to {}", output_file);
        compute_graph.save_data_to_file(&output_file).unwrap();
    }
}

examples/bfs.rs (line 21)

fn main() {
    let (input_graph, src_node, output_file) = {
        let args = std::env::args().skip(1).collect::<Vec<_>>();

        if args.len() != 2 && args.len() != 3 {
            println!("Usage: bfs <converted graph directory> <src_node> [output_file]");
            return;
        }

        let output = {
            if args.len() == 3 {
                Some(args[2].clone())
            } else {
                None
            }
        };

        (args[0].clone(), args[1].parse::<usize>().unwrap(), output)
    };

    let graph = graph_csr::Graph::<u32>::load_graph(&input_graph).unwrap();
    let mut compute_graph = graph_csr::compute::ComputeGraph::<u32, u32>::new(&graph);

    // Initialize nodes
    compute_graph.fill_active(false);
    compute_graph.fill_data(u32::MAX);

    // Initialize source
    compute_graph.set_active(src_node, true);
    compute_graph.set_data(src_node, 0);

    compute_graph.step(); // Set data

    let mut i = 0;
    while compute_graph.n_active() > 0 {
        let time_start = std::time::Instant::now();

        compute_graph.push(|src, dst| graph_csr::compute::helper::atomic_min(src, dst, |v| v + 1));
        compute_graph.step();

        let time_end = std::time::Instant::now();

        i += 1;
        println!(
            "Iteration {} took {}ms",
            i,
            (time_end - time_start).as_millis()
        );
    }

    // Print results
    print!("[ ");
    for (idx, data) in compute_graph
        .get_data_as_slice()
        .iter()
        .enumerate()
        .take(30)
    {
        print!(
            "{}:{}, ",
            idx,
            data.load(std::sync::atomic::Ordering::Relaxed)
        );
    }
    println!("]");

    // Save file
    if let Some(output_file) = output_file {
        println!("Saving file to {}", output_file);
        compute_graph.save_data_to_file(&output_file).unwrap();
    }
}

pub fn iter(&'a self) -> impl Iterator<Item = &[N]> + 'a

Returns an iterator over the edge list of each node.

pub fn par_iter(&'a self) -> impl ParallelIterator<Item = (usize, &[N])> + 'a

where N: Send + Sync,

pub fn n_nodes(&self) -> usize

Returns the number of nodes existing in the graph

Examples found in repository

examples/wcc.rs (line 27)

fn main() {
    let (input_graph, output_file) = {
        let args = std::env::args().skip(1).collect::<Vec<_>>();

        if args.len() != 1 && args.len() != 2 {
            println!("Usage: wcc <converted graph directory> [output_file]");
            return;
        }

        let output = {
            if args.len() == 2 {
                Some(args[1].clone())
            } else {
                None
            }
        };

        (args[0].clone(), output)
    };

    let graph = graph_csr::Graph::<u32>::load_graph(&input_graph).unwrap();

    let mut compute_graph = graph_csr::compute::ComputeGraph::<u32, u32>::new(&graph);

    // Initialize
    compute_graph.fill_active(true);
    for i in 0..graph.n_nodes() {
        compute_graph.set_data(i, i as u32);
    }
    compute_graph.step(); // Set data

    let mut i = 0;
    while compute_graph.n_active() > 0 {
        let time_start = std::time::Instant::now();
        compute_graph.push(|src, dst| graph_csr::compute::helper::atomic_min(src, dst, |v| v));
        let time_end = std::time::Instant::now();
        compute_graph.step();

        i += 1;
        println!(
            "Iteration {} took {}ms",
            i,
            (time_end - time_start).as_millis()
        );
    }

    // Print results
    print!("[ ");
    for (idx, data) in compute_graph
        .get_data_as_slice()
        .iter()
        .enumerate()
        .take(30)
    {
        print!(
            "{}:{}, ",
            idx,
            data.load(std::sync::atomic::Ordering::Relaxed)
        );
    }
    println!("]");

    // Save file
    if let Some(output_file) = output_file {
        println!("Saving file to {}", output_file);
        compute_graph.save_data_to_file(&output_file).unwrap();
    }
}

pub fn n_edges(&self) -> usize

Returns the number of edges existing in the graph