use bitvec::BitVector;
use std::fmt::Debug;
use std::usize;
use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
#[cfg(test)]
mod tests;
pub struct Graph<N, E> {
nodes: SnapshotVec<Node<N>>,
edges: SnapshotVec<Edge<E>>,
}
pub struct Node<N> {
first_edge: [EdgeIndex; 2], pub data: N,
}
#[derive(Debug)]
pub struct Edge<E> {
next_edge: [EdgeIndex; 2], source: NodeIndex,
target: NodeIndex,
pub data: E,
}
impl<N> SnapshotVecDelegate for Node<N> {
type Value = Node<N>;
type Undo = ();
fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
}
impl<N> SnapshotVecDelegate for Edge<N> {
type Value = Edge<N>;
type Undo = ();
fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
pub struct NodeIndex(pub usize);
#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
pub struct EdgeIndex(pub usize);
pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Direction {
repr: usize,
}
pub const OUTGOING: Direction = Direction { repr: 0 };
pub const INCOMING: Direction = Direction { repr: 1 };
impl NodeIndex {
pub fn node_id(&self) -> usize {
self.0
}
}
impl<N: Debug, E: Debug> Graph<N, E> {
pub fn new() -> Graph<N, E> {
Graph {
nodes: SnapshotVec::new(),
edges: SnapshotVec::new(),
}
}
pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
Graph {
nodes: SnapshotVec::with_capacity(nodes),
edges: SnapshotVec::with_capacity(edges),
}
}
#[inline]
pub fn all_nodes(&self) -> &[Node<N>] {
&self.nodes
}
#[inline]
pub fn len_nodes(&self) -> usize {
self.nodes.len()
}
#[inline]
pub fn all_edges(&self) -> &[Edge<E>] {
&self.edges
}
#[inline]
pub fn len_edges(&self) -> usize {
self.edges.len()
}
pub fn next_node_index(&self) -> NodeIndex {
NodeIndex(self.nodes.len())
}
pub fn add_node(&mut self, data: N) -> NodeIndex {
let idx = self.next_node_index();
self.nodes.push(Node {
first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
data,
});
idx
}
pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
&mut self.nodes[idx.0].data
}
pub fn node_data(&self, idx: NodeIndex) -> &N {
&self.nodes[idx.0].data
}
pub fn node(&self, idx: NodeIndex) -> &Node<N> {
&self.nodes[idx.0]
}
pub fn next_edge_index(&self) -> EdgeIndex {
EdgeIndex(self.edges.len())
}
pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
let idx = self.next_edge_index();
let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
self.edges.push(Edge {
next_edge: [source_first, target_first],
source,
target,
data,
});
self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
self.nodes[target.0].first_edge[INCOMING.repr] = idx;
return idx;
}
pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
&self.edges[idx.0]
}
pub fn enumerated_nodes(&self) -> EnumeratedNodes<N> {
EnumeratedNodes {
iter: self.nodes.iter().enumerate()
}
}
pub fn enumerated_edges(&self) -> EnumeratedEdges<E> {
EnumeratedEdges {
iter: self.edges.iter().enumerate()
}
}
pub fn each_node<'a, F>(&'a self, mut f: F) -> bool
where F: FnMut(NodeIndex, &'a Node<N>) -> bool
{
self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node))
}
pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool
where F: FnMut(EdgeIndex, &'a Edge<E>) -> bool
{
self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge))
}
pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
self.adjacent_edges(source, OUTGOING)
}
pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
self.adjacent_edges(source, INCOMING)
}
pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
let first_edge = self.node(source).first_edge[direction.repr];
AdjacentEdges {
graph: self,
direction,
next: first_edge,
}
}
pub fn successor_nodes(&self, source: NodeIndex) -> AdjacentTargets<N, E> {
self.outgoing_edges(source).targets()
}
pub fn predecessor_nodes(&self, target: NodeIndex) -> AdjacentSources<N, E> {
self.incoming_edges(target).sources()
}
pub fn depth_traverse<'a>(&'a self,
start: NodeIndex,
direction: Direction)
-> DepthFirstTraversal<'a, N, E> {
DepthFirstTraversal::with_start_node(self, start, direction)
}
pub fn nodes_in_postorder<'a>(&'a self,
direction: Direction,
entry_node: NodeIndex)
-> Vec<NodeIndex>
{
let mut visited = BitVector::new(self.len_nodes());
let mut stack = vec![];
let mut result = Vec::with_capacity(self.len_nodes());
let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
if visited.insert(node.0) {
stack.push((node, self.adjacent_edges(node, direction)));
}
};
for node in Some(entry_node).into_iter()
.chain(self.enumerated_nodes().map(|(node, _)| node))
{
push_node(&mut stack, node);
while let Some((node, mut iter)) = stack.pop() {
if let Some((_, child)) = iter.next() {
let target = child.source_or_target(direction);
stack.push((node, iter));
push_node(&mut stack, target);
} else {
result.push(node);
}
}
}
assert_eq!(result.len(), self.len_nodes());
result
}
}
pub struct EnumeratedNodes<'g, N>
where N: 'g,
{
iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Node<N>>>
}
impl<'g, N: Debug> Iterator for EnumeratedNodes<'g, N> {
type Item = (NodeIndex, &'g Node<N>);
fn next(&mut self) -> Option<(NodeIndex, &'g Node<N>)> {
self.iter.next().map(|(idx, n)| (NodeIndex(idx), n))
}
}
pub struct EnumeratedEdges<'g, E>
where E: 'g,
{
iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Edge<E>>>
}
impl<'g, E: Debug> Iterator for EnumeratedEdges<'g, E> {
type Item = (EdgeIndex, &'g Edge<E>);
fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
self.iter.next().map(|(idx, e)| (EdgeIndex(idx), e))
}
}
pub struct AdjacentEdges<'g, N, E>
where N: 'g,
E: 'g
{
graph: &'g Graph<N, E>,
direction: Direction,
next: EdgeIndex,
}
impl<'g, N, E> AdjacentEdges<'g, N, E> {
fn targets(self) -> AdjacentTargets<'g, N, E> {
AdjacentTargets { edges: self }
}
fn sources(self) -> AdjacentSources<'g, N, E> {
AdjacentSources { edges: self }
}
}
impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
type Item = (EdgeIndex, &'g Edge<E>);
fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
let edge_index = self.next;
if edge_index == INVALID_EDGE_INDEX {
return None;
}
let edge = self.graph.edge(edge_index);
self.next = edge.next_edge[self.direction.repr];
Some((edge_index, edge))
}
}
pub struct AdjacentTargets<'g, N, E>
where N: 'g,
E: 'g
{
edges: AdjacentEdges<'g, N, E>,
}
impl<'g, N: Debug, E: Debug> Iterator for AdjacentTargets<'g, N, E> {
type Item = NodeIndex;
fn next(&mut self) -> Option<NodeIndex> {
self.edges.next().map(|(_, edge)| edge.target)
}
}
pub struct AdjacentSources<'g, N, E>
where N: 'g,
E: 'g
{
edges: AdjacentEdges<'g, N, E>,
}
impl<'g, N: Debug, E: Debug> Iterator for AdjacentSources<'g, N, E> {
type Item = NodeIndex;
fn next(&mut self) -> Option<NodeIndex> {
self.edges.next().map(|(_, edge)| edge.source)
}
}
pub struct DepthFirstTraversal<'g, N, E>
where N: 'g,
E: 'g
{
graph: &'g Graph<N, E>,
stack: Vec<NodeIndex>,
visited: BitVector,
direction: Direction,
}
impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
pub fn with_start_node(graph: &'g Graph<N, E>,
start_node: NodeIndex,
direction: Direction)
-> Self {
let mut visited = BitVector::new(graph.len_nodes());
visited.insert(start_node.node_id());
DepthFirstTraversal {
graph,
stack: vec![start_node],
visited,
direction,
}
}
fn visit(&mut self, node: NodeIndex) {
if self.visited.insert(node.node_id()) {
self.stack.push(node);
}
}
}
impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
type Item = NodeIndex;
fn next(&mut self) -> Option<NodeIndex> {
let next = self.stack.pop();
if let Some(idx) = next {
for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
let target = edge.source_or_target(self.direction);
self.visit(target);
}
}
next
}
}
impl<E> Edge<E> {
pub fn source(&self) -> NodeIndex {
self.source
}
pub fn target(&self) -> NodeIndex {
self.target
}
pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
if direction == OUTGOING {
self.target
} else {
self.source
}
}
}