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
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