1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A graph module for use in dataflow, region resolution, and elsewhere.
13 //! # Interface details
15 //! You customize the graph by specifying a "node data" type `N` and an
16 //! "edge data" type `E`. You can then later gain access (mutable or
17 //! immutable) to these "user-data" bits. Currently, you can only add
18 //! nodes or edges to the graph. You cannot remove or modify them once
19 //! added. This could be changed if we have a need.
21 //! # Implementation details
23 //! The main tricky thing about this code is the way that edges are
24 //! stored. The edges are stored in a central array, but they are also
25 //! threaded onto two linked lists for each node, one for incoming edges
26 //! and one for outgoing edges. Note that every edge is a member of some
27 //! incoming list and some outgoing list. Basically you can load the
28 //! first index of the linked list from the node data structures (the
29 //! field `first_edge`) and then, for each edge, load the next index from
30 //! the field `next_edge`). Each of those fields is an array that should
31 //! be indexed by the direction (see the type `Direction`).
33 #![allow(dead_code)] // still WIP
35 use std::fmt::{Formatter, Error, Show};
37 use std::collections::BitvSet;
39 pub struct Graph<N,E> {
45 first_edge: [EdgeIndex; 2], // see module comment
50 next_edge: [EdgeIndex; 2], // see module comment
56 impl<E: Show> Show for Edge<E> {
57 fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
58 write!(f, "Edge {{ next_edge: [{}, {}], source: {}, target: {}, data: {} }}",
59 self.next_edge[0], self.next_edge[1], self.source,
60 self.target, self.data)
64 #[derive(Clone, Copy, PartialEq, Show)]
65 pub struct NodeIndex(pub uint);
66 #[allow(non_upper_case_globals)]
67 pub const InvalidNodeIndex: NodeIndex = NodeIndex(uint::MAX);
69 #[derive(Copy, PartialEq, Show)]
70 pub struct EdgeIndex(pub uint);
71 #[allow(non_upper_case_globals)]
72 pub const InvalidEdgeIndex: EdgeIndex = EdgeIndex(uint::MAX);
74 // Use a private field here to guarantee no more instances are created:
76 pub struct Direction { repr: uint }
77 #[allow(non_upper_case_globals)]
78 pub const Outgoing: Direction = Direction { repr: 0 };
79 #[allow(non_upper_case_globals)]
80 pub const Incoming: Direction = Direction { repr: 1 };
83 fn get(&self) -> uint { let NodeIndex(v) = *self; v }
84 /// Returns unique id (unique with respect to the graph holding associated node).
85 pub fn node_id(&self) -> uint { self.get() }
89 fn get(&self) -> uint { let EdgeIndex(v) = *self; v }
90 /// Returns unique id (unique with respect to the graph holding associated edge).
91 pub fn edge_id(&self) -> uint { self.get() }
94 impl<N,E> Graph<N,E> {
95 pub fn new() -> Graph<N,E> {
102 pub fn with_capacity(num_nodes: uint,
103 num_edges: uint) -> Graph<N,E> {
105 nodes: Vec::with_capacity(num_nodes),
106 edges: Vec::with_capacity(num_edges),
110 ///////////////////////////////////////////////////////////////////////////
114 pub fn all_nodes<'a>(&'a self) -> &'a [Node<N>] {
115 let nodes: &'a [Node<N>] = self.nodes.as_slice();
120 pub fn all_edges<'a>(&'a self) -> &'a [Edge<E>] {
121 let edges: &'a [Edge<E>] = self.edges.as_slice();
125 ///////////////////////////////////////////////////////////////////////////
128 pub fn next_node_index(&self) -> NodeIndex {
129 NodeIndex(self.nodes.len())
132 pub fn add_node(&mut self, data: N) -> NodeIndex {
133 let idx = self.next_node_index();
134 self.nodes.push(Node {
135 first_edge: [InvalidEdgeIndex, InvalidEdgeIndex],
141 pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
142 &mut self.nodes[idx.get()].data
145 pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
146 &self.nodes[idx.get()].data
149 pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
150 &self.nodes[idx.get()]
153 ///////////////////////////////////////////////////////////////////////////
154 // Edge construction and queries
156 pub fn next_edge_index(&self) -> EdgeIndex {
157 EdgeIndex(self.edges.len())
160 pub fn add_edge(&mut self,
163 data: E) -> EdgeIndex {
164 let idx = self.next_edge_index();
166 // read current first of the list of edges from each node
167 let source_first = self.nodes[source.get()]
168 .first_edge[Outgoing.repr];
169 let target_first = self.nodes[target.get()]
170 .first_edge[Incoming.repr];
172 // create the new edge, with the previous firsts from each node
173 // as the next pointers
174 self.edges.push(Edge {
175 next_edge: [source_first, target_first],
181 // adjust the firsts for each node target be the next object.
182 self.nodes[source.get()].first_edge[Outgoing.repr] = idx;
183 self.nodes[target.get()].first_edge[Incoming.repr] = idx;
188 pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E {
189 &mut self.edges[idx.get()].data
192 pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
193 &self.edges[idx.get()].data
196 pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
197 &self.edges[idx.get()]
200 pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
201 //! Accesses the index of the first edge adjacent to `node`.
202 //! This is useful if you wish to modify the graph while walking
203 //! the linked list of edges.
205 self.nodes[node.get()].first_edge[dir.repr]
208 pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
209 //! Accesses the next edge in a given direction.
210 //! This is useful if you wish to modify the graph while walking
211 //! the linked list of edges.
213 self.edges[edge.get()].next_edge[dir.repr]
216 ///////////////////////////////////////////////////////////////////////////
217 // Iterating over nodes, edges
219 pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where
220 F: FnMut(NodeIndex, &'a Node<N>) -> bool,
222 //! Iterates over all edges defined in the graph.
223 self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node))
226 pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where
227 F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
229 //! Iterates over all edges defined in the graph
230 self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
233 pub fn each_outgoing_edge<'a, F>(&'a self, source: NodeIndex, f: F) -> bool where
234 F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
236 //! Iterates over all outgoing edges from the node `from`
238 self.each_adjacent_edge(source, Outgoing, f)
241 pub fn each_incoming_edge<'a, F>(&'a self, target: NodeIndex, f: F) -> bool where
242 F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
244 //! Iterates over all incoming edges to the node `target`
246 self.each_adjacent_edge(target, Incoming, f)
249 pub fn each_adjacent_edge<'a, F>(&'a self,
254 F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
256 //! Iterates over all edges adjacent to the node `node`
257 //! in the direction `dir` (either `Outgoing` or `Incoming)
259 let mut edge_idx = self.first_adjacent(node, dir);
260 while edge_idx != InvalidEdgeIndex {
261 let edge = &self.edges[edge_idx.get()];
262 if !f(edge_idx, edge) {
265 edge_idx = edge.next_edge[dir.repr];
270 ///////////////////////////////////////////////////////////////////////////
271 // Fixed-point iteration
273 // A common use for graphs in our compiler is to perform
274 // fixed-point iteration. In this case, each edge represents a
275 // constraint, and the nodes themselves are associated with
276 // variables or other bitsets. This method facilitates such a
279 pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where
280 F: FnMut(uint, EdgeIndex, &'a Edge<E>) -> bool,
282 let mut iteration = 0;
283 let mut changed = true;
287 for (i, edge) in self.edges.iter().enumerate() {
288 changed |= op(iteration, EdgeIndex(i), edge);
293 pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> {
294 DepthFirstTraversal {
297 visited: BitvSet::new()
302 pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
303 graph: &'g Graph<N, E>,
304 stack: Vec<NodeIndex>,
308 impl<'g, N, E> Iterator for DepthFirstTraversal<'g, N, E> {
311 fn next(&mut self) -> Option<&'g N> {
312 while let Some(idx) = self.stack.pop() {
313 if !self.visited.insert(idx.node_id()) {
316 self.graph.each_outgoing_edge(idx, |_, e| -> bool {
317 if !self.visited.contains(&e.target().node_id()) {
318 self.stack.push(e.target());
323 return Some(self.graph.node_data(idx));
330 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where
331 F: FnMut(EdgeIndex) -> bool,
334 let n = max_edge_index.get();
336 if !f(EdgeIndex(i)) {
344 pub fn source(&self) -> NodeIndex {
348 pub fn target(&self) -> NodeIndex {
355 use middle::graph::*;
358 type TestNode = Node<&'static str>;
359 type TestEdge = Edge<&'static str>;
360 type TestGraph = Graph<&'static str, &'static str>;
362 fn create_graph() -> TestGraph {
363 let mut graph = Graph::new();
365 // Create a simple graph
372 let a = graph.add_node("A");
373 let b = graph.add_node("B");
374 let c = graph.add_node("C");
375 let d = graph.add_node("D");
376 let e = graph.add_node("E");
377 let f = graph.add_node("F");
379 graph.add_edge(a, b, "AB");
380 graph.add_edge(b, c, "BC");
381 graph.add_edge(b, d, "BD");
382 graph.add_edge(d, e, "DE");
383 graph.add_edge(e, c, "EC");
384 graph.add_edge(f, b, "FB");
391 let graph = create_graph();
392 let expected = ["A", "B", "C", "D", "E", "F"];
393 graph.each_node(|idx, node| {
394 assert_eq!(&expected[idx.get()], graph.node_data(idx));
395 assert_eq!(expected[idx.get()], node.data);
402 let graph = create_graph();
403 let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
404 graph.each_edge(|idx, edge| {
405 assert_eq!(&expected[idx.get()], graph.edge_data(idx));
406 assert_eq!(expected[idx.get()], edge.data);
411 fn test_adjacent_edges<N:PartialEq+Show,E:PartialEq+Show>(graph: &Graph<N,E>,
412 start_index: NodeIndex,
414 expected_incoming: &[(E,N)],
415 expected_outgoing: &[(E,N)]) {
416 assert!(graph.node_data(start_index) == &start_data);
419 graph.each_incoming_edge(start_index, |edge_index, edge| {
420 assert!(graph.edge_data(edge_index) == &edge.data);
421 assert!(counter < expected_incoming.len());
422 debug!("counter={} expected={} edge_index={} edge={}",
423 counter, expected_incoming[counter], edge_index, edge);
424 match expected_incoming[counter] {
426 assert!(e == &edge.data);
427 assert!(n == graph.node_data(edge.source));
428 assert!(start_index == edge.target);
434 assert_eq!(counter, expected_incoming.len());
437 graph.each_outgoing_edge(start_index, |edge_index, edge| {
438 assert!(graph.edge_data(edge_index) == &edge.data);
439 assert!(counter < expected_outgoing.len());
440 debug!("counter={} expected={} edge_index={} edge={}",
441 counter, expected_outgoing[counter], edge_index, edge);
442 match expected_outgoing[counter] {
444 assert!(e == &edge.data);
445 assert!(start_index == edge.source);
446 assert!(n == graph.node_data(edge.target));
452 assert_eq!(counter, expected_outgoing.len());
456 fn each_adjacent_from_a() {
457 let graph = create_graph();
458 test_adjacent_edges(&graph, NodeIndex(0), "A",
464 fn each_adjacent_from_b() {
465 let graph = create_graph();
466 test_adjacent_edges(&graph, NodeIndex(1), "B",
467 &[("FB", "F"), ("AB", "A"),],
468 &[("BD", "D"), ("BC", "C"),]);
472 fn each_adjacent_from_c() {
473 let graph = create_graph();
474 test_adjacent_edges(&graph, NodeIndex(2), "C",
475 &[("EC", "E"), ("BC", "B")],
480 fn each_adjacent_from_d() {
481 let graph = create_graph();
482 test_adjacent_edges(&graph, NodeIndex(3), "D",