001: /**
002: * Copyright (c) 2004-2006 Regents of the University of California.
003: * See "license-prefuse.txt" for licensing terms.
004: */package prefuse.data;
005:
006: import java.util.BitSet;
007: import java.util.Iterator;
008: import java.util.LinkedList;
009:
010: import prefuse.data.tuple.TupleManager;
011: import prefuse.visual.tuple.TableEdgeItem;
012:
013: /**
014: * Special tree instance for storing a spanning tree over a graph
015: * instance. The spanning tree ensures that only Node and Edge instances
016: * from the backing Graph are returned, so requesting nodes, edges, or
017: * iterators over this spanning tree will return the desired Node or
018: * Edge tuples from the backing graph this tree spans.
019: *
020: * @author <a href="http://jheer.org">jeffrey heer</a>
021: */
022: public class SpanningTree extends Tree {
023:
024: /** Extra edge table data field recording the id of the source edge
025: * a tree edge represents. */
026: public static final String SOURCE_EDGE = "source";
027: /** Edge table schema used by the spanning tree. */
028: protected static final Schema EDGE_SCHEMA = new Schema();
029: static {
030: EDGE_SCHEMA.addColumn(DEFAULT_SOURCE_KEY, int.class,
031: new Integer(-1));
032: EDGE_SCHEMA.addColumn(DEFAULT_TARGET_KEY, int.class,
033: new Integer(-1));
034: EDGE_SCHEMA.addColumn(SOURCE_EDGE, int.class);
035: }
036:
037: /** A reference to the backing graph that this tree spans. */
038: protected Graph m_backing;
039:
040: /**
041: * Create a new SpanningTree.
042: * @param g the backing Graph to span
043: * @param root the Node to use as the root of the spanning tree
044: */
045: public SpanningTree(Graph g, Node root) {
046: super (g.getNodeTable(), EDGE_SCHEMA.instantiate());
047: m_backing = g;
048: TupleManager etm = new TupleManager(getEdgeTable(), null,
049: TableEdgeItem.class) {
050: public Tuple getTuple(int row) {
051: return m_backing.getEdge(m_table.getInt(row,
052: SOURCE_EDGE));
053: }
054: };
055: getEdgeTable().setTupleManager(etm);
056: super .setTupleManagers(g.m_nodeTuples, etm);
057: buildSpanningTree(root);
058: }
059:
060: /**
061: * Build the spanning tree, starting at the given root. Uses an
062: * unweighted breadth first traversal to build the spanning tree.
063: * @param root the root node of the spanning tree
064: */
065: public void buildSpanningTree(Node root) {
066: // re-use a previously allocated tree if possible
067: super .clearEdges();
068: super .setRoot(root);
069:
070: // build unweighted spanning tree by BFS
071: LinkedList q = new LinkedList();
072: BitSet visit = new BitSet();
073: q.add(root);
074: visit.set(root.getRow());
075: Table edges = getEdgeTable();
076:
077: while (!q.isEmpty()) {
078: Node p = (Node) q.removeFirst();
079: for (Iterator iter = p.edges(); iter.hasNext();) {
080: Edge e = (Edge) iter.next();
081: Node n = e.getAdjacentNode(p);
082: if (!visit.get(n.getRow())) {
083: q.add(n);
084: visit.set(n.getRow());
085: int er = super .addChildEdge(p.getRow(), n.getRow());
086: edges.setInt(er, SOURCE_EDGE, e.getRow());
087: }
088: }
089: }
090: }
091:
092: // ------------------------------------------------------------------------
093: // Disallow most mutator methods
094:
095: /**
096: * Unsupported operation. Spanning trees should not be edited.
097: * @see prefuse.data.Tree#addChild(int)
098: */
099: public int addChild(int parent) {
100: throw new UnsupportedOperationException(
101: "Changes to tree structure not allowed for spanning trees.");
102: }
103:
104: /**
105: * Unsupported operation. Spanning trees should not be edited.
106: * @see prefuse.data.Tree#addChild(prefuse.data.Node)
107: */
108: public Node addChild(Node parent) {
109: throw new UnsupportedOperationException(
110: "Changes to tree structure not allowed for spanning trees.");
111: }
112:
113: /**
114: * Unsupported operation. Spanning trees should not be edited.
115: * @see prefuse.data.Tree#addChildEdge(int, int)
116: */
117: public int addChildEdge(int parent, int child) {
118: throw new UnsupportedOperationException(
119: "Changes to tree structure not allowed for spanning trees.");
120: }
121:
122: /**
123: * Unsupported operation. Spanning trees should not be edited.
124: * @see prefuse.data.Tree#addChildEdge(prefuse.data.Node, prefuse.data.Node)
125: */
126: public Edge addChildEdge(Node parent, Node child) {
127: throw new UnsupportedOperationException(
128: "Changes to tree structure not allowed for spanning trees.");
129: }
130:
131: /**
132: * Unsupported operation. Spanning trees should not be edited.
133: * @see prefuse.data.Tree#addRoot()
134: */
135: public Node addRoot() {
136: throw new UnsupportedOperationException(
137: "Changes to tree structure not allowed for spanning trees.");
138: }
139:
140: /**
141: * Unsupported operation. Spanning trees should not be edited.
142: * @see prefuse.data.Tree#addRootRow()
143: */
144: public int addRootRow() {
145: throw new UnsupportedOperationException(
146: "Changes to tree structure not allowed for spanning trees.");
147: }
148:
149: /**
150: * Unsupported operation. Spanning trees should not be edited.
151: * @see prefuse.data.Tree#removeChild(int)
152: */
153: public boolean removeChild(int node) {
154: throw new UnsupportedOperationException(
155: "Changes to tree structure not allowed for spanning trees.");
156: }
157:
158: /**
159: * Unsupported operation. Spanning trees should not be edited.
160: * @see prefuse.data.Tree#removeChild(prefuse.data.Node)
161: */
162: public boolean removeChild(Node n) {
163: throw new UnsupportedOperationException(
164: "Changes to tree structure not allowed for spanning trees.");
165: }
166:
167: /**
168: * Unsupported operation. Spanning trees should not be edited.
169: * @see prefuse.data.Tree#removeChildEdge(prefuse.data.Edge)
170: */
171: public boolean removeChildEdge(Edge e) {
172: throw new UnsupportedOperationException(
173: "Changes to tree structure not allowed for spanning trees.");
174: }
175:
176: /**
177: * Unsupported operation. Spanning trees should not be edited.
178: * @see prefuse.data.Tree#removeChildEdge(int)
179: */
180: public boolean removeChildEdge(int edge) {
181: throw new UnsupportedOperationException(
182: "Changes to tree structure not allowed for spanning trees.");
183: }
184:
185: /**
186: * Unsupported operation. Spanning trees should not be edited.
187: * @see prefuse.data.Tree#setRoot(prefuse.data.Node)
188: */
189: void setRoot(Node root) {
190: throw new UnsupportedOperationException(
191: "Changes to tree structure not allowed for spanning trees.");
192: }
193:
194: /**
195: * Unsupported operation. Spanning trees should not be edited.
196: * @see prefuse.data.Graph#addEdge(int, int)
197: */
198: public int addEdge(int s, int t) {
199: throw new UnsupportedOperationException(
200: "Changes to graph structure not allowed for spanning trees.");
201: }
202:
203: /**
204: * Unsupported operation. Spanning trees should not be edited.
205: * @see prefuse.data.Graph#addEdge(prefuse.data.Node, prefuse.data.Node)
206: */
207: public Edge addEdge(Node s, Node t) {
208: throw new UnsupportedOperationException(
209: "Changes to graph structure not allowed for spanning trees.");
210: }
211:
212: /**
213: * Unsupported operation. Spanning trees should not be edited.
214: * @see prefuse.data.Graph#addNode()
215: */
216: public Node addNode() {
217: throw new UnsupportedOperationException(
218: "Changes to graph structure not allowed for spanning trees.");
219: }
220:
221: /**
222: * Unsupported operation. Spanning trees should not be edited.
223: * @see prefuse.data.Graph#addNodeRow()
224: */
225: public int addNodeRow() {
226: throw new UnsupportedOperationException(
227: "Changes to graph structure not allowed for spanning trees.");
228: }
229:
230: /**
231: * Unsupported operation. Spanning trees should not be edited.
232: * @see prefuse.data.tuple.TupleSet#clear()
233: */
234: public void clear() {
235: throw new UnsupportedOperationException(
236: "Changes to graph structure not allowed for spanning trees.");
237: }
238:
239: /**
240: * Unsupported operation. Spanning trees should not be edited.
241: * @see prefuse.data.Graph#removeEdge(prefuse.data.Edge)
242: */
243: public boolean removeEdge(Edge e) {
244: throw new UnsupportedOperationException(
245: "Changes to graph structure not allowed for spanning trees.");
246: }
247:
248: /**
249: * Unsupported operation. Spanning trees should not be edited.
250: * @see prefuse.data.Graph#removeEdge(int)
251: */
252: public boolean removeEdge(int edge) {
253: throw new UnsupportedOperationException(
254: "Changes to graph structure not allowed for spanning trees.");
255: }
256:
257: /**
258: * Unsupported operation. Spanning trees should not be edited.
259: * @see prefuse.data.Graph#removeNode(int)
260: */
261: public boolean removeNode(int node) {
262: throw new UnsupportedOperationException(
263: "Changes to graph structure not allowed for spanning trees.");
264: }
265:
266: /**
267: * Unsupported operation. Spanning trees should not be edited.
268: * @see prefuse.data.Graph#removeNode(prefuse.data.Node)
269: */
270: public boolean removeNode(Node n) {
271: throw new UnsupportedOperationException(
272: "Changes to graph structure not allowed for spanning trees.");
273: }
274:
275: /**
276: * Unsupported operation. Spanning trees should not be edited.
277: * @see prefuse.data.tuple.TupleSet#removeTuple(prefuse.data.Tuple)
278: */
279: public boolean removeTuple(Tuple t) {
280: throw new UnsupportedOperationException(
281: "Changes to graph structure not allowed for spanning trees.");
282: }
283:
284: /**
285: * Unsupported operation. Spanning trees should not be edited.
286: * @see prefuse.data.Graph#setEdgeTable(prefuse.data.Table)
287: */
288: public void setEdgeTable(Table edges) {
289: throw new UnsupportedOperationException(
290: "Changes to graph structure not allowed for spanning trees.");
291: }
292:
293: /**
294: * Unsupported operation. Spanning trees should not be edited.
295: * @see prefuse.data.Graph#setTupleManagers(prefuse.data.tuple.TupleManager, prefuse.data.tuple.TupleManager)
296: */
297: public void setTupleManagers(TupleManager ntm, TupleManager etm) {
298: throw new UnsupportedOperationException(
299: "Changes to graph structure not allowed for spanning trees.");
300: }
301:
302: } // end of class SpanningTree
|