## macro rs-graph-derive

Automatic implementation of graph types

### 21 releases(12 breaking)

 0.21.0 Aug 28, 2023 May 8, 2021 Jun 3, 2020 Feb 14, 2020 Dec 14, 2017

#1829 in Algorithms

GPL-3.0+

505KB
10K 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::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::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 {
#[nodeattrs(NodeData)] nodedata: Vec<NodeData>,
#[edgeattrs(EdgeData)] edgedata: Vec<EdgeData>,
}

#[derive(Graph)]
struct MyGraph2 {
#[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);
}
``````

~1.1–1.5MB
~35K SLoC