001: package prefuse.data.util;
002:
003: import java.util.Iterator;
004:
005: import prefuse.Constants;
006: import prefuse.data.Edge;
007: import prefuse.data.Node;
008: import prefuse.data.Tuple;
009: import prefuse.util.collections.Queue;
010:
011: /**
012: * Provides a distance-limited breadth first traversal over nodes, edges,
013: * or both, using any number of traversal "roots".
014: *
015: * @author <a href="http://jheer.org">jeffrey heer</a>
016: */
017: public class BreadthFirstIterator implements Iterator {
018:
019: protected Queue m_queue = new Queue();
020: protected int m_depth;
021: protected int m_traversal;
022: protected boolean m_includeNodes;
023: protected boolean m_includeEdges;
024:
025: /**
026: * Create an uninitialized BreadthFirstIterator. Use the
027: * {@link #init(Object, int, int)} method to initialize the iterator.
028: */
029: public BreadthFirstIterator() {
030: // do nothing, requires init call
031: }
032:
033: /**
034: * Create a new BreadthFirstIterator starting from the given source node.
035: * @param n the source node from which to begin the traversal
036: * @param depth the maximum graph distance to traverse
037: * @param traversal the traversal type, one of
038: * {@link prefuse.Constants#NODE_TRAVERSAL},
039: * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
040: * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
041: */
042: public BreadthFirstIterator(Node n, int depth, int traversal) {
043: init(new Node[] { n }, depth, traversal);
044: }
045:
046: /**
047: * Create a new BreadthFirstIterator starting from the given source nodes.
048: * @param it an Iterator over the source nodes from which to begin the
049: * traversal
050: * @param depth the maximum graph distance to traverse
051: * @param traversal the traversal type, one of
052: * {@link prefuse.Constants#NODE_TRAVERSAL},
053: * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
054: * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
055: */
056: public BreadthFirstIterator(Iterator it, int depth, int traversal) {
057: init(it, depth, traversal);
058: }
059:
060: /**
061: * Initialize (or re-initialize) this iterator.
062: * @param o Either a source node or iterator over source nodes
063: * @param depth the maximum graph distance to traverse
064: * @param traversal the traversal type, one of
065: * {@link prefuse.Constants#NODE_TRAVERSAL},
066: * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
067: * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
068: */
069: public void init(Object o, int depth, int traversal) {
070: // initialize the member variables
071: m_queue.clear();
072: m_depth = depth;
073: if (traversal < 0 || traversal >= Constants.TRAVERSAL_COUNT)
074: throw new IllegalArgumentException(
075: "Unrecognized traversal type: " + traversal);
076: m_traversal = traversal;
077: m_includeNodes = (traversal == Constants.NODE_TRAVERSAL || traversal == Constants.NODE_AND_EDGE_TRAVERSAL);
078: m_includeEdges = (traversal == Constants.EDGE_TRAVERSAL || traversal == Constants.NODE_AND_EDGE_TRAVERSAL);
079:
080: // seed the queue
081: // TODO: clean this up? (use generalized iterator?)
082: if (m_includeNodes) {
083: if (o instanceof Node) {
084: m_queue.add(o, 0);
085: } else {
086: Iterator tuples = (Iterator) o;
087: while (tuples.hasNext())
088: m_queue.add(tuples.next(), 0);
089: }
090: } else {
091: if (o instanceof Node) {
092: Node n = (Node) o;
093: m_queue.visit(n, 0);
094: Iterator edges = getEdges(n);
095: while (edges.hasNext()) {
096: Edge e = (Edge) edges.next();
097: Node nn = e.getAdjacentNode(n);
098: m_queue.visit(nn, 1);
099: if (m_queue.getDepth(e) < 0)
100: m_queue.add(e, 1);
101: }
102: } else {
103: Iterator tuples = (Iterator) o;
104: while (tuples.hasNext()) {
105: // TODO: graceful error handling when non-node in set?
106: Node n = (Node) tuples.next();
107: m_queue.visit(n, 0);
108: Iterator edges = getEdges(n);
109: while (edges.hasNext()) {
110: Edge e = (Edge) edges.next();
111: Node nn = e.getAdjacentNode(n);
112: m_queue.visit(nn, 1);
113: if (m_queue.getDepth(e) < 0)
114: m_queue.add(e, 1);
115: }
116: }
117: }
118: }
119: }
120:
121: // ------------------------------------------------------------------------
122:
123: /**
124: * @see java.util.Iterator#remove()
125: */
126: public void remove() {
127: throw new UnsupportedOperationException();
128: }
129:
130: /**
131: * @see java.util.Iterator#hasNext()
132: */
133: public boolean hasNext() {
134: return !m_queue.isEmpty();
135: }
136:
137: /**
138: * Determines which edges are traversed for a given node.
139: * @param n a node
140: * @return an iterator over edges incident on the node
141: */
142: protected Iterator getEdges(Node n) {
143: return n.edges(); // TODO: add support for all edges, in links only, out links only
144: }
145:
146: /**
147: * Get the traversal depth at which a particular tuple was encountered.
148: * @param t the tuple to lookup
149: * @return the traversal depth of the tuple, or -1 if the tuple has not
150: * been visited by the traversal.
151: */
152: public int getDepth(Tuple t) {
153: return m_queue.getDepth(t);
154: }
155:
156: /**
157: * @see java.util.Iterator#next()
158: */
159: public Object next() {
160: Tuple t = (Tuple) m_queue.removeFirst();
161:
162: switch (m_traversal) {
163:
164: case Constants.NODE_TRAVERSAL:
165: case Constants.NODE_AND_EDGE_TRAVERSAL:
166: for (; true; t = (Tuple) m_queue.removeFirst()) {
167: if (t instanceof Edge) {
168: return t;
169: } else {
170: Node n = (Node) t;
171: int d = m_queue.getDepth(n);
172:
173: if (d < m_depth) {
174: int dd = d + 1;
175: Iterator edges = getEdges(n);
176: while (edges.hasNext()) {
177: Edge e = (Edge) edges.next();
178: Node v = e.getAdjacentNode(n);
179:
180: if (m_includeEdges
181: && m_queue.getDepth(e) < 0)
182: m_queue.add(e, dd);
183: if (m_queue.getDepth(v) < 0)
184: m_queue.add(v, dd);
185: }
186: } else if (m_includeEdges && d == m_depth) {
187: Iterator edges = getEdges(n);
188: while (edges.hasNext()) {
189: Edge e = (Edge) edges.next();
190: Node v = e.getAdjacentNode(n);
191: int dv = m_queue.getDepth(v);
192: if (dv > 0 && m_queue.getDepth(e) < 0) {
193: m_queue.add(e, Math.min(d, dv));
194: }
195: }
196: }
197: return n;
198: }
199: }
200:
201: case Constants.EDGE_TRAVERSAL:
202: Edge e = (Edge) t;
203: Node u = e.getSourceNode();
204: Node v = e.getTargetNode();
205: int du = m_queue.getDepth(u);
206: int dv = m_queue.getDepth(v);
207:
208: if (du != dv) {
209: Node n = (dv > du ? v : u);
210: int d = Math.max(du, dv);
211:
212: if (d < m_depth) {
213: int dd = d + 1;
214: Iterator edges = getEdges(n);
215: while (edges.hasNext()) {
216: Edge ee = (Edge) edges.next();
217: if (m_queue.getDepth(ee) >= 0)
218: continue; // already visited
219:
220: Node nn = ee.getAdjacentNode(n);
221: m_queue.visit(nn, dd);
222: m_queue.add(ee, dd);
223: }
224: }
225: }
226: return e;
227:
228: default:
229: throw new IllegalStateException();
230: }
231: }
232:
233: } // end of class BreadthFirstIterator
|