1 unstable release
0.0.1 | Jul 14, 2023 |
---|
#5 in #pie
43KB
668 lines
A modified version of the incremental-topo
crate for use in PIE and the
PIE tutorial.
The purpose of this crate is to maintain an topological order in the face of single updates, like adding new nodes, adding new edges, deleting edges, and deleting nodes.
Adding nodes, deleting nodes, and deleting dependencies require a trivial amount of work to perform an update, because those operations do not change the topological ordering. Adding new dependencies can change the topological ordering.
What is a Topological Order
To define a topological order requires at least a simple definition of a
graph, and specifically a directed acyclic graph (DAG). A graph can be
described as a pair of sets, (V, E)
where V
is the set of all nodes in
the graph, and E
is the set of edges. An edge is defined as a pair, (m, n)
where m
and n
are nodes. A directed graph means that edges only
imply a single direction of relationship between two nodes, as opposed to a
undirected graph which implies the relationship goes both ways. An example
of undirected vs. directed in social networks would be Facebook vs.
Twitter. Facebook friendship is a two way relationship, while following
someone on Twitter does not imply that they follow you back.
A topological ordering, ord_D
of a directed acyclic graph, D = (V, E)
where x, y ∈ V
, is a mapping of nodes to priority values such that
ord_D(x) < ord_D(y)
holds for all edges (x, y) ∈ E
. This yields a total
ordering of the nodes in D
.
Examples
use pie_graph::DAG;
use std::{cmp::Ordering::*, collections::HashSet};
let mut dag = DAG::new();
let dog = dag.add_node(());
let cat = dag.add_node(());
let mouse = dag.add_node(());
let lion = dag.add_node(());
let human = dag.add_node(());
let gazelle = dag.add_node(());
let grass = dag.add_node(());
assert_eq!(dag.len(), 7);
dag.add_edge(&lion, &human, ()).unwrap();
dag.add_edge(&lion, &gazelle, ()).unwrap();
dag.add_edge(&human, &dog, ()).unwrap();
dag.add_edge(&human, &cat, ()).unwrap();
dag.add_edge(&dog, &cat, ()).unwrap();
dag.add_edge(&cat, &mouse, ()).unwrap();
dag.add_edge(&gazelle, &grass, ()).unwrap();
dag.add_edge(&mouse, &grass, ()).unwrap();
let pairs = dag
.descendants_unsorted(&human)
.unwrap()
.collect::<HashSet<_>>();
let expected_pairs = [(4, cat), (3, dog), (5, mouse), (7, grass)]
.iter()
.cloned()
.collect::<HashSet<_>>();
assert_eq!(pairs, expected_pairs);
assert!(dag.contains_transitive_edge(&lion, &grass));
assert!(!dag.contains_transitive_edge(&human, &gazelle));
assert_eq!(dag.topo_cmp(&cat, &dog), Greater);
assert_eq!(dag.topo_cmp(&lion, &human), Less);
Sources
The paper by D. J. Pearce and P. H. J. Kelly contains descriptions of three different algorithms for incremental topological ordering, along with analysis of runtime bounds for each.
Dependencies
~2.4–3MB
~54K SLoC