21 releases (12 breaking)

0.21.0 Aug 28, 2023
0.20.1 May 8, 2021
0.19.2 Jun 3, 2020
0.19.1 Feb 14, 2020
0.9.0 Dec 14, 2017

#21 in #combinatorics

GPL-3.0+

505KB
11K SLoC

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 needed 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)]
    }
}

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 eid in 0..g.num_edges() { *g.bound_mut(g.id2edge(eid)) = eid 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],
        }
    }
}

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 eid in 0..g.num_edges() { g.edge_mut(g.id2edge(eid)).bound = eid 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

~2MB
~41K SLoC