18 releases (10 breaking)

0.19.2 Jun 3, 2020
0.19.1 Feb 14, 2020
0.18.0 Jan 26, 2020
0.17.1 Jul 10, 2019
0.9.0 Dec 14, 2017

#734 in Algorithms

Download history 36/week @ 2020-08-08 36/week @ 2020-08-15 3/week @ 2020-08-22 18/week @ 2020-08-29 72/week @ 2020-09-05 1/week @ 2020-09-12 1/week @ 2020-09-26 18/week @ 2020-10-03 18/week @ 2020-10-17 2/week @ 2020-11-07 1/week @ 2020-11-14

85 downloads per month

GPL-3.0+

425KB
8K SLoC


lib.rs:

This crate provides automatic graph derivations.

In order to automatically implement graph traits for a struct that contains the actual graph data structure in a field, add #[derive(Graph)] to the struct. The field containing the graph must either be named graph or be attributed with #[graph]. All graph traits (Graph, Digraph, and IndexGraph) that are implemented for the nested graph, are implemented for the annotated struct, too.

Example

use rs_graph_derive::Graph;
use rs_graph::traits::*;
use rs_graph::linkedlistgraph::*;
use rs_graph::classes;

#[derive(Graph)]
struct MyGraph {
    #[graph] graph: LinkedListGraph, // #[graph] not need for fields named `graph`.
    balances: Vec<f64>,
    bounds: Vec<f64>,
}

impl From<LinkedListGraph> for MyGraph {
    fn from(g: LinkedListGraph) -> MyGraph {
        let n = g.num_nodes();
        let m = g.num_edges();
        MyGraph {
            graph: g,
            balances: vec![0.0; n],
            bounds: vec![0.0; m],
        }
    }
}

impl MyGraph {
    fn balance_mut(&mut self, u: Node) -> &mut f64 {
        &mut self.balances[self.graph.node_id(u)]
    }

    fn bound_mut(&mut self, e: Edge) -> &mut f64 {
        &mut self.bounds[self.graph.edge_id(e)]
    }
}

# fn main() {
let mut g: MyGraph = classes::path::<LinkedListGraph>(5).into();
let (s, t) = (g.id2node(0), g.id2node(4));
*g.balance_mut(s) = 1.0;
*g.balance_mut(t) = -1.0;
for e in g.edges() { *g.bound_mut(e) = g.edge_id(e) as f64; }
# }

Attributed graphs

Some algorithms require the presence of specific node or edge attributes. These requirements are represented by NodeAttributes and EdgeAttributes traits from rs_graph::attributes. These traits can also be automatically implemented using #[derive(Graph)] given that the wrapped graph is an IndexGraph. The node/edge attributes must be collected in indexable arrays (slice, Vec, ...) of an appropriate size and be annotated with nodeattrs or edgeattrs attributes. Note that it is the responsibility of the user to ensure that these vectors have to correct size.

Example

use rs_graph_derive::Graph;
use rs_graph::{traits::*};
use rs_graph::linkedlistgraph::*;
use rs_graph::classes;
use rs_graph::attributes::{NodeAttributes, EdgeAttributes, AttributedGraph};

#[derive(Clone, Default)]
struct NodeData {
    balance: f64,
}

#[derive(Clone, Default)]
struct EdgeData {
    bound: f64,
}

#[derive(Graph)]
struct MyGraph {
    #[graph] graph: LinkedListGraph,
    #[nodeattrs(NodeData)] nodedata: Vec<NodeData>,
    #[edgeattrs(EdgeData)] edgedata: Vec<EdgeData>,
}

#[derive(Graph)]
struct MyGraph2 {
    #[graph] graph: LinkedListGraph,
    #[nodeattrs(NodeData)] nodedata: Vec<NodeData>,
    #[edgeattrs(EdgeData)] edgedata: Vec<EdgeData>,
}

impl From<LinkedListGraph> for MyGraph {
    fn from(g: LinkedListGraph) -> MyGraph {
        let n = g.num_nodes();
        let m = g.num_edges();
        MyGraph {
            graph: g,
            nodedata: vec![Default::default(); n],
            edgedata: vec![Default::default(); m],
        }
    }
}

# fn main() {
let mut g: MyGraph = classes::peterson::<LinkedListGraph>().into();
let (s, t) = (g.id2node(0), g.id2node(4));
g.node_mut(s).balance = 1.0;
g.node_mut(t).balance = -1.0;
for e in g.edges() { g.edge_mut(e).bound = g.edge_id(e) as f64; }

{
    let (g, mut attrs) = g.split();
    // this would also work: let (g, mut attrs) = attrs.split();
    for u in g.nodes() {
        for (e, v) in g.outedges(u) {
            attrs.node_mut(v).balance = 42.0 + g.node_id(v) as f64;
        }
    }
}
for u in g.nodes() {
    assert_eq!(g.node(u).balance, 42.0 + g.node_id(u) as f64);
}
# }

Dependencies

~0.6–1MB
~25K SLoC