use super::{
ArrangeError, CycleError, DirectFanoutError, EdgeEndpointError, EdgeId, NodeId,
builder::{Edge, GraphBuilder, Node},
};
#[derive(Debug)]
pub struct ChannelGraph {
nodes: Vec<Node>,
edges: Vec<Edge>,
layers: Vec<Vec<NodeId>>,
orphans: Vec<NodeId>,
}
impl ChannelGraph {
#[inline]
pub fn nodes(&self) -> &[Node] {
&self.nodes
}
#[inline]
pub fn edges(&self) -> &[Edge] {
&self.edges
}
#[inline]
pub fn layers(&self) -> &[Vec<NodeId>] {
&self.layers
}
#[inline]
pub fn orphans(&self) -> &[NodeId] {
&self.orphans
}
#[inline]
pub fn node(&self, id: NodeId) -> Option<&Node> {
self.nodes.get(id.index())
}
}
impl GraphBuilder {
pub fn validate(self) -> Result<ChannelGraph, ArrangeError> {
let (nodes, edges) = self.into_parts();
let n = nodes.len();
for (i, e) in edges.iter().enumerate() {
for endpoint in [e.from(), e.to()] {
if endpoint.index() >= n {
return Err(ArrangeError::EdgeEndpointOutOfRange(
EdgeEndpointError::new(EdgeId::new(i), endpoint, n),
));
}
}
}
let mut out_count = vec![0usize; n];
let mut has_direct = vec![false; n];
for e in &edges {
let f = e.from().index();
out_count[f] += 1;
if e.kind().is_direct() {
has_direct[f] = true;
}
}
for i in 0..n {
if out_count[i] > 1 && has_direct[i] {
return Err(ArrangeError::DirectFanout(DirectFanoutError::new(
NodeId::new(i),
nodes[i].name().into(),
out_count[i],
)));
}
}
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut indeg = vec![0usize; n];
for e in &edges {
adj[e.from().index()].push(e.to().index());
indeg[e.to().index()] += 1;
}
let mut remaining = indeg;
let mut placed = vec![false; n];
let mut placed_count = 0usize;
let mut layers: Vec<Vec<NodeId>> = Vec::new();
loop {
let layer: Vec<usize> = (0..n)
.filter(|&i| !placed[i] && remaining[i] == 0)
.collect();
if layer.is_empty() {
break;
}
for &i in &layer {
placed[i] = true;
}
placed_count += layer.len();
for &i in &layer {
for &t in &adj[i] {
remaining[t] -= 1;
}
}
layers.push(layer.into_iter().map(NodeId::new).collect());
}
if placed_count < n {
let mut pred: Vec<Vec<usize>> = vec![Vec::new(); n];
for e in &edges {
pred[e.to().index()].push(e.from().index());
}
let mut visited = vec![false; n];
let mut cur = (0..n)
.find(|&i| !placed[i])
.expect("a node remains unplaced");
while !visited[cur] {
visited[cur] = true;
cur = pred[cur]
.iter()
.copied()
.find(|&p| !placed[p])
.expect("Kahn stalled, so every unplaced node has an unplaced predecessor");
}
return Err(ArrangeError::Cycle(CycleError::new(
NodeId::new(cur),
nodes[cur].name().into(),
)));
}
let mut reachable = vec![false; n];
let mut stack: Vec<usize> = (0..n).filter(|&i| nodes[i].is_source()).collect();
for &s in &stack {
reachable[s] = true;
}
while let Some(i) = stack.pop() {
for &t in &adj[i] {
if !reachable[t] {
reachable[t] = true;
stack.push(t);
}
}
}
let orphans: Vec<NodeId> = (0..n).filter(|&i| !reachable[i]).map(NodeId::new).collect();
Ok(ChannelGraph {
nodes,
edges,
layers,
orphans,
})
}
}
#[cfg(test)]
mod tests;