SpanningTree


1   /**
2    * Copyright (c) 2004-2006 Regents of the University of California.
3    * See "license-prefuse.txt" for licensing terms.
4    */
5   package prefuse.data;
6   
7   import java.util.BitSet  ;
8   import java.util.Iterator  ;
9   import java.util.LinkedList  ;
10  
11  import prefuse.data.tuple.TupleManager;
12  import prefuse.visual.tuple.TableEdgeItem;
13  
14  /**
15   * Special tree instance for storing a spanning tree over a graph
16   * instance. The spanning tree ensures that only Node and Edge instances
17   * from the backing Graph are returned, so requesting nodes, edges, or
18   * iterators over this spanning tree will return the desired Node or
19   * Edge tuples from the backing graph this tree spans.
20   * 
21   * @author <a HREF="http://jheer.org">jeffrey heer</a>
22   */
23  public class SpanningTree extends Tree {
24  
25      /** Extra edge table data field recording the id of the source edge
26       * a tree edge represents. */
27      public static final String   SOURCE_EDGE = "source";
28      /** Edge table schema used by the spanning tree. */
29      protected static final Schema EDGE_SCHEMA = new Schema();
30      static {
31          EDGE_SCHEMA.addColumn(DEFAULT_SOURCE_KEY, int.class, new Integer  (-1));
32          EDGE_SCHEMA.addColumn(DEFAULT_TARGET_KEY, int.class, new Integer  (-1));
33          EDGE_SCHEMA.addColumn(SOURCE_EDGE, int.class);
34      }
35      
36      /** A reference to the backing graph that this tree spans. */
37      protected Graph m_backing;
38      
39      /**
40       * Create a new SpanningTree.
41       * @param g the backing Graph to span
42       * @param root the Node to use as the root of the spanning tree
43       */
44      public SpanningTree(Graph g, Node root) {
45          super(g.getNodeTable(), EDGE_SCHEMA.instantiate());
46          m_backing = g;
47          TupleManager etm = new TupleManager(getEdgeTable(), null,
48                                              TableEdgeItem.class) {
49              public Tuple getTuple(int row) {
50                  return m_backing.getEdge(m_table.getInt(row, SOURCE_EDGE));
51              }
52          };
53          getEdgeTable().setTupleManager(etm);
54          super.setTupleManagers(g.m_nodeTuples, etm);
55          buildSpanningTree(root);
56      }
57      
58      /**
59       * Build the spanning tree, starting at the given root. Uses an
60       * unweighted breadth first traversal to build the spanning tree.
61       * @param root the root node of the spanning tree
62       */
63      public void buildSpanningTree(Node root) {
64          // re-use a previously allocated tree if possible
65          super.clearEdges();
66          super.setRoot(root);
67              
68          // build unweighted spanning tree by BFS
69          LinkedList   q = new LinkedList  ();
70          BitSet   visit = new BitSet  ();
71          q.add(root); visit.set(root.getRow());
72          Table edges = getEdgeTable();
73          
74          while ( !q.isEmpty() ) {
75              Node p = (Node)q.removeFirst();
76              for ( Iterator   iter = p.edges(); iter.hasNext(); ) {
77                  Edge e = (Edge)iter.next();
78                  Node n = e.getAdjacentNode(p);
79                  if ( !visit.get(n.getRow()) ) {
80                      q.add(n); visit.set(n.getRow());
81                      int er = super.addChildEdge(p.getRow(), n.getRow());
82                      edges.setInt(er, SOURCE_EDGE, e.getRow());
83                  }
84              }
85          }
86      }
87  
88      // ------------------------------------------------------------------------
89      // Disallow most mutator methods
90      
91      /**
92       * Unsupported operation. Spanning trees should not be edited.
93       * @see prefuse.data.Tree#addChild(int)
94       */
95      public int addChild(int parent) {
96          throw new UnsupportedOperationException  (
97              "Changes to tree structure not allowed for spanning trees.");
98      }
99  
100     /**
101      * Unsupported operation. Spanning trees should not be edited.
102      * @see prefuse.data.Tree#addChild(prefuse.data.Node)
103      */
104     public Node addChild(Node parent) {
105         throw new UnsupportedOperationException  (
106             "Changes to tree structure not allowed for spanning trees.");
107     }
108 
109     /**
110      * Unsupported operation. Spanning trees should not be edited.
111      * @see prefuse.data.Tree#addChildEdge(int, int)
112      */
113     public int addChildEdge(int parent, int child) {
114         throw new UnsupportedOperationException  (
115             "Changes to tree structure not allowed for spanning trees.");
116     }
117 
118     /**
119      * Unsupported operation. Spanning trees should not be edited.
120      * @see prefuse.data.Tree#addChildEdge(prefuse.data.Node, prefuse.data.Node)
121      */
122     public Edge addChildEdge(Node parent, Node child) {
123         throw new UnsupportedOperationException  (
124             "Changes to tree structure not allowed for spanning trees.");
125     }
126 
127     /**
128      * Unsupported operation. Spanning trees should not be edited.
129      * @see prefuse.data.Tree#addRoot()
130      */
131     public Node addRoot() {
132         throw new UnsupportedOperationException  (
133             "Changes to tree structure not allowed for spanning trees.");
134     }
135 
136     /**
137      * Unsupported operation. Spanning trees should not be edited.
138      * @see prefuse.data.Tree#addRootRow()
139      */
140     public int addRootRow() {
141         throw new UnsupportedOperationException  (
142             "Changes to tree structure not allowed for spanning trees.");
143     }
144 
145     /**
146      * Unsupported operation. Spanning trees should not be edited.
147      * @see prefuse.data.Tree#removeChild(int)
148      */
149     public boolean removeChild(int node) {
150         throw new UnsupportedOperationException  (
151             "Changes to tree structure not allowed for spanning trees.");
152     }
153 
154     /**
155      * Unsupported operation. Spanning trees should not be edited.
156      * @see prefuse.data.Tree#removeChild(prefuse.data.Node)
157      */
158     public boolean removeChild(Node n) {
159         throw new UnsupportedOperationException  (
160             "Changes to tree structure not allowed for spanning trees.");
161     }
162 
163     /**
164      * Unsupported operation. Spanning trees should not be edited.
165      * @see prefuse.data.Tree#removeChildEdge(prefuse.data.Edge)
166      */
167     public boolean removeChildEdge(Edge e) {
168         throw new UnsupportedOperationException  (
169             "Changes to tree structure not allowed for spanning trees.");
170     }
171 
172     /**
173      * Unsupported operation. Spanning trees should not be edited.
174      * @see prefuse.data.Tree#removeChildEdge(int)
175      */
176     public boolean removeChildEdge(int edge) {
177         throw new UnsupportedOperationException  (
178             "Changes to tree structure not allowed for spanning trees.");
179     }
180 
181     /**
182      * Unsupported operation. Spanning trees should not be edited.
183      * @see prefuse.data.Tree#setRoot(prefuse.data.Node)
184      */
185     void setRoot(Node root) {
186         throw new UnsupportedOperationException  (
187             "Changes to tree structure not allowed for spanning trees.");
188     }
189 
190     /**
191      * Unsupported operation. Spanning trees should not be edited.
192      * @see prefuse.data.Graph#addEdge(int, int)
193      */
194     public int addEdge(int s, int t) {
195         throw new UnsupportedOperationException  (
196             "Changes to graph structure not allowed for spanning trees.");
197     }
198 
199     /**
200      * Unsupported operation. Spanning trees should not be edited.
201      * @see prefuse.data.Graph#addEdge(prefuse.data.Node, prefuse.data.Node)
202      */
203     public Edge addEdge(Node s, Node t) {
204         throw new UnsupportedOperationException  (
205             "Changes to graph structure not allowed for spanning trees.");
206     }
207 
208     /**
209      * Unsupported operation. Spanning trees should not be edited.
210      * @see prefuse.data.Graph#addNode()
211      */
212     public Node addNode() {
213         throw new UnsupportedOperationException  (
214             "Changes to graph structure not allowed for spanning trees.");
215     }
216 
217     /**
218      * Unsupported operation. Spanning trees should not be edited.
219      * @see prefuse.data.Graph#addNodeRow()
220      */
221     public int addNodeRow() {
222         throw new UnsupportedOperationException  (
223             "Changes to graph structure not allowed for spanning trees.");
224     }
225 
226     /**
227      * Unsupported operation. Spanning trees should not be edited.
228      * @see prefuse.data.tuple.TupleSet#clear()
229      */
230     public void clear() {
231         throw new UnsupportedOperationException  (
232             "Changes to graph structure not allowed for spanning trees.");
233     }
234 
235     /**
236      * Unsupported operation. Spanning trees should not be edited.
237      * @see prefuse.data.Graph#removeEdge(prefuse.data.Edge)
238      */
239     public boolean removeEdge(Edge e) {
240         throw new UnsupportedOperationException  (
241             "Changes to graph structure not allowed for spanning trees.");
242     }
243 
244     /**
245      * Unsupported operation. Spanning trees should not be edited.
246      * @see prefuse.data.Graph#removeEdge(int)
247      */
248     public boolean removeEdge(int edge) {
249         throw new UnsupportedOperationException  (
250             "Changes to graph structure not allowed for spanning trees.");
251     }
252 
253     /**
254      * Unsupported operation. Spanning trees should not be edited.
255      * @see prefuse.data.Graph#removeNode(int)
256      */
257     public boolean removeNode(int node) {
258         throw new UnsupportedOperationException  (
259             "Changes to graph structure not allowed for spanning trees.");
260     }
261 
262     /**
263      * Unsupported operation. Spanning trees should not be edited.
264      * @see prefuse.data.Graph#removeNode(prefuse.data.Node)
265      */
266     public boolean removeNode(Node n) {
267         throw new UnsupportedOperationException  (
268             "Changes to graph structure not allowed for spanning trees.");
269     }
270 
271     /**
272      * Unsupported operation. Spanning trees should not be edited.
273      * @see prefuse.data.tuple.TupleSet#removeTuple(prefuse.data.Tuple)
274      */
275     public boolean removeTuple(Tuple t) {
276         throw new UnsupportedOperationException  (
277             "Changes to graph structure not allowed for spanning trees.");
278     }
279 
280     /**
281      * Unsupported operation. Spanning trees should not be edited.
282      * @see prefuse.data.Graph#setEdgeTable(prefuse.data.Table)
283      */
284     public void setEdgeTable(Table edges) {
285         throw new UnsupportedOperationException  (
286             "Changes to graph structure not allowed for spanning trees.");
287     }
288 
289     /**
290      * Unsupported operation. Spanning trees should not be edited.
291      * @see prefuse.data.Graph#setTupleManagers(prefuse.data.tuple.TupleManager, prefuse.data.tuple.TupleManager)
292      */
293     public void setTupleManagers(TupleManager ntm, TupleManager etm) {
294         throw new UnsupportedOperationException  (
295             "Changes to graph structure not allowed for spanning trees.");
296     }
297     
298 } // end of class SpanningTree
299
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags