Module rs_graph::adjacencies

source ·
Expand description

Abstraction of neighboring edges.

This module implements the arguably simplest representation of a graph: for each node the list of adjacent edges and nodes. No further information like the number of nodes or edges in a graph is available.

The purpose of the trait Adjacencies is therefore to abstract over the concept of adjacent edges and nodes. Standard examples are “all edges” (in the undirected sense), “incoming edges” and “outgoing edges” represented by the structs Neighbors, InEdges and OutEdges.

Some algorithms (e.g. breadth-first search or depth-first search) can be described in terms of adjacencies only.

There are three basic ways to define an adjacency:

  1. From an existing graph or digraph using Neighbors, OutEdges or InEdges,
  2. From a function returning an iterator over adjacent edges for a given node, see FnAdj,
  3. By implementing the Adjacencies trait on your own.

Example

use rs_graph::classes;
use rs_graph::Net;
use rs_graph::traits::*;
use rs_graph::adjacencies::*;

let g = classes::peterson::<Net>();

let neighs = Neighbors(&g);
let neighs = neighs.filter(|&(e, _)| {
  let (u,v) = g.enodes(e);
  (g.node_id(u) < 5) == (g.node_id(v) < 5)
});
for u in g.nodes() {
    assert_eq!(neighs.neighs(u).count(), 2);
}

Structs

Traits