BreadthFirstIterator


1   package prefuse.data.util;
2   
3   import java.util.Iterator  ;
4   
5   import prefuse.Constants;
6   import prefuse.data.Edge;
7   import prefuse.data.Node;
8   import prefuse.data.Tuple;
9   import prefuse.util.collections.Queue;
10  
11  /**
12   * Provides a distance-limited breadth first traversal over nodes, edges,
13   * or both, using any number of traversal "roots".
14   *  
15   * @author <a HREF="http://jheer.org">jeffrey heer</a>
16   */
17  public class BreadthFirstIterator implements Iterator   {
18  
19      protected Queue m_queue = new Queue();
20      protected int   m_depth;
21      protected int   m_traversal;
22      protected boolean m_includeNodes;
23      protected boolean m_includeEdges;
24      
25      /**
26       * Create an uninitialized BreadthFirstIterator. Use the
27       * {@link #init(Object, int, int)} method to initialize the iterator.
28       */
29      public BreadthFirstIterator() {
30          // do nothing, requires init call
31      }
32      
33      /**
34       * Create a new BreadthFirstIterator starting from the given source node.
35       * @param n the source node from which to begin the traversal
36       * @param depth the maximum graph distance to traverse
37       * @param traversal the traversal type, one of
38       * {@link prefuse.Constants#NODE_TRAVERSAL},
39       * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
40       * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
41       */
42      public BreadthFirstIterator(Node n, int depth, int traversal) {
43          init(new Node[] {n}, depth, traversal);
44      }
45      
46      /**
47       * Create a new BreadthFirstIterator starting from the given source nodes.
48       * @param it an Iterator over the source nodes from which to begin the
49       * traversal
50       * @param depth the maximum graph distance to traverse
51       * @param traversal the traversal type, one of
52       * {@link prefuse.Constants#NODE_TRAVERSAL},
53       * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
54       * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
55       */
56      public BreadthFirstIterator(Iterator   it, int depth, int traversal) {
57          init(it, depth, traversal);
58      }
59      
60      /**
61       * Initialize (or re-initialize) this iterator.
62       * @param o Either a source node or iterator over source nodes
63       * @param depth the maximum graph distance to traverse
64       * @param traversal the traversal type, one of
65       * {@link prefuse.Constants#NODE_TRAVERSAL},
66       * {@link prefuse.Constants#EDGE_TRAVERSAL}, or
67       * {@link prefuse.Constants#NODE_AND_EDGE_TRAVERSAL}
68       */
69      public void init(Object   o, int depth, int traversal) {
70          // initialize the member variables
71          m_queue.clear();
72          m_depth = depth;
73          if ( traversal < 0 || traversal >= Constants.TRAVERSAL_COUNT )
74              throw new IllegalArgumentException  (
75                      "Unrecognized traversal type: "+traversal);
76          m_traversal = traversal;
77          m_includeNodes = (traversal == Constants.NODE_TRAVERSAL || 
78                  traversal == Constants.NODE_AND_EDGE_TRAVERSAL);
79          m_includeEdges = (traversal == Constants.EDGE_TRAVERSAL ||
80                  traversal == Constants.NODE_AND_EDGE_TRAVERSAL);
81          
82          // seed the queue
83          // TODO: clean this up? (use generalized iterator?)
84          if ( m_includeNodes ) {
85              if ( o instanceof Node ) {
86                  m_queue.add(o, 0);
87              } else {
88                  Iterator   tuples = (Iterator  )o;
89                  while ( tuples.hasNext() )
90                      m_queue.add(tuples.next(), 0);
91              }
92          } else {
93              if ( o instanceof Node ) {
94                  Node n = (Node)o;
95                  m_queue.visit(n, 0);
96                  Iterator   edges = getEdges(n);
97                  while ( edges.hasNext() ) {
98                      Edge e = (Edge)edges.next();
99                      Node nn = e.getAdjacentNode(n);
100                     m_queue.visit(nn, 1);
101                     if ( m_queue.getDepth(e) < 0 )
102                         m_queue.add(e, 1);
103                 }
104             } else {
105                 Iterator   tuples = (Iterator  )o;
106                 while ( tuples.hasNext() ) {
107                     // TODO: graceful error handling when non-node in set?
108                     Node n = (Node)tuples.next();
109                     m_queue.visit(n, 0);
110                     Iterator   edges = getEdges(n);
111                     while ( edges.hasNext() ) {
112                         Edge e = (Edge)edges.next();
113                         Node nn = e.getAdjacentNode(n);
114                         m_queue.visit(nn, 1);
115                         if ( m_queue.getDepth(e) < 0 )
116                             m_queue.add(e, 1);
117                     }
118                 }
119             }
120         }
121     }
122     
123     // ------------------------------------------------------------------------
124     
125     /**
126      * @see java.util.Iterator#remove()
127      */
128     public void remove() {
129         throw new UnsupportedOperationException  ();
130     }
131 
132     /**
133      * @see java.util.Iterator#hasNext()
134      */
135     public boolean hasNext() {
136         return !m_queue.isEmpty();
137     }
138 
139     /**
140      * Determines which edges are traversed for a given node.
141      * @param n a node
142      * @return an iterator over edges incident on the node
143      */
144     protected Iterator   getEdges(Node n) {
145         return n.edges(); // TODO: add support for all edges, in links only, out links only
146     }
147     
148     /**
149      * Get the traversal depth at which a particular tuple was encountered.
150      * @param t the tuple to lookup
151      * @return the traversal depth of the tuple, or -1 if the tuple has not
152      * been visited by the traversal.
153      */
154     public int getDepth(Tuple t) {
155         return m_queue.getDepth(t);
156     }
157     
158     /**
159      * @see java.util.Iterator#next()
160      */
161     public Object   next() {        
162         Tuple t = (Tuple)m_queue.removeFirst();
163 
164         switch ( m_traversal ) {
165         
166         case Constants.NODE_TRAVERSAL:
167         case Constants.NODE_AND_EDGE_TRAVERSAL:
168             for ( ; true; t = (Tuple)m_queue.removeFirst() ) {
169                 if ( t instanceof Edge ) {
170                     return t;
171                 } else {
172                     Node n = (Node)t;
173                     int d = m_queue.getDepth(n);
174                     
175                     if ( d < m_depth ) {
176                         int dd = d+1;
177                         Iterator   edges = getEdges(n);
178                         while ( edges.hasNext() ) {
179                             Edge e = (Edge)edges.next();
180                             Node v = e.getAdjacentNode(n);
181                         
182                             if ( m_includeEdges && m_queue.getDepth(e) < 0 )
183                                 m_queue.add(e, dd);
184                             if ( m_queue.getDepth(v) < 0 )
185                                 m_queue.add(v, dd);
186                         }
187                     }
188                     else if ( m_includeEdges && d == m_depth )
189                     {
190                         Iterator   edges = getEdges(n);
191                         while ( edges.hasNext() ) {
192                             Edge e = (Edge)edges.next();
193                             Node v = e.getAdjacentNode(n);
194                             int dv = m_queue.getDepth(v);
195                             if ( dv > 0 && m_queue.getDepth(e) < 0 ) {
196                                 m_queue.add(e, Math.min(d,dv));
197                             }
198                         }
199                     }
200                     return n;
201                 }
202             }
203                 
204         case Constants.EDGE_TRAVERSAL:
205             Edge e = (Edge)t;
206             Node u = e.getSourceNode();
207             Node v = e.getTargetNode();
208             int du = m_queue.getDepth(u);
209             int dv = m_queue.getDepth(v);
210 
211             if ( du != dv ) {
212                 Node n = (dv > du ? v : u);
213                 int  d = Math.max(du, dv);
214             
215                 if ( d < m_depth ) {
216                     int dd = d+1;
217                     Iterator   edges = getEdges(n);
218                     while ( edges.hasNext() ) {
219                         Edge ee = (Edge)edges.next();
220                         if ( m_queue.getDepth(ee) >= 0 )
221                             continue; // already visited
222             
223                         Node nn = ee.getAdjacentNode(n);
224                         m_queue.visit(nn, dd);
225                         m_queue.add(ee, dd);
226                     }
227                 }
228             }
229             return e;
230         
231         default:
232             throw new IllegalStateException  ();
233         }
234     }
235 
236 } // end of class BreadthFirstIterator
237
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags