Type Definition robust_binary_search::CompressedDAG

type CompressedDAG = DAG<CompressedDAGSegment>;

A DAG whose nodes are CompressedDAGSegments, which represent sequences of nodes in a conceptual expanded graph. For example, given the graph:

  B-C-D
 /     \
A       G
 \     /
  E---F

this can be expressed in a CompressedDAG as:

  B'
 / \
A'  G'
 \ /
  E'

where A' and G' are segments of size 1 corresponding to A and G, E' is a segment of size 2 corresponding to E and F, and B' is a segment of size 3 corresponding to B, C, and D.

More formally, the nodes represented by a segment must be in a linear formation (i.e. directed, acyclic, connected, with each node having at most one incoming edge from another node in the segment and at most one outgoing edge to another node in the segment), with only the first node allowing edges from outside the segment, and only the last node allowing edges to outside the segment.

This representation allows many common graphs to be represented in a more compact form than directly as a DAG.