Trait Graph

Source

pub trait Graph:
    Clone
    + Send
    + Sync {
    // Required methods
    fn num_vertices(&self) -> usize;
    fn num_edges(&self) -> usize;
    fn edges(&self) -> Vec<(usize, usize)>;
    fn has_edge(&self, u: usize, v: usize) -> bool;
    fn neighbors(&self, v: usize) -> Vec<usize>;

    // Provided methods
    fn degree(&self, v: usize) -> usize { ... }
    fn is_empty(&self) -> bool { ... }
    fn for_each_edge<F>(&self, f: F)
       where F: FnMut(usize, usize) { ... }
}

Expand description

Trait for graph types, following Julia’s Graphs.jl AbstractGraph pattern.

This trait abstracts over different graph representations, allowing problems to be generic over the underlying graph type.

§Example

use problemreductions::topology::{Graph, SimpleGraph};

fn count_triangles<G: Graph>(graph: &G) -> usize {
    let mut count = 0;
    for u in 0..graph.num_vertices() {
        for v in graph.neighbors(u) {
            if v > u {
                for w in graph.neighbors(v) {
                    if w > v && graph.has_edge(u, w) {
                        count += 1;
                    }
                }
            }
        }
    }
    count
}