KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > GraphLib


1 package prefuse.util;
2
3 import java.util.ArrayList JavaDoc;
4
5 import prefuse.data.Graph;
6 import prefuse.data.Node;
7 import prefuse.data.Schema;
8 import prefuse.data.Tree;
9
10 /**
11  * Library routines for creating various Graph structures. All Graphs
12  * generated by methods of this class include a String-valued
13  * "label" field.
14  *
15  * @author <a HREF="http://jheer.org">jeffrey heer</a>
16  */

17 public class GraphLib {
18
19     private GraphLib() {
20         // prevent instantiation
21
}
22     
23     // ------------------------------------------------------------------------
24
// Graph Creation Routines
25

26     /**
27      * Builds a completely unconnected (edge-free) graph with the given
28      * number of nodes
29      * @param n the number of nodes
30      * @return a graph with n nodes and no edges
31      */

32     public static Graph getNodes(int n) {
33         Graph g = new Graph();
34         g.getNodeTable().addColumns(LABEL_SCHEMA);
35         
36         for ( int i=0; i < n; i++ ) {
37             Node node = g.addNode();
38             node.setString(LABEL, String.valueOf(i));
39         }
40         return g;
41     }
42     
43     /**
44      * Builds a "star" graph with one central hub connected to the given
45      * number of satellite nodes.
46      * @param n the number of points of the star
47      * @return a "star" graph with n points, for a total of n+1 nodes
48      */

49     public static Graph getStar(int n) {
50         Graph g = new Graph();
51         g.getNodeTable().addColumns(LABEL_SCHEMA);
52         
53         Node r = g.addNode();
54         r.setString(LABEL, "0");
55         
56         for ( int i=1; i <= n; ++i ) {
57             Node nn = g.addNode();
58             nn.setString(LABEL, String.valueOf(i));
59             g.addEdge(r, nn);
60         }
61         return g;
62     }
63     
64     /**
65      * Returns a clique of given size. A clique is a graph in which every node
66      * is a neighbor of every other node.
67      * @param n the number of nodes in the graph
68      * @return a clique of size n
69      */

70     public static Graph getClique(int n) {
71         Graph g = new Graph();
72         g.getNodeTable().addColumns(LABEL_SCHEMA);
73         
74         Node nodes[] = new Node[n];
75         for ( int i = 0; i < n; ++i ) {
76             nodes[i] = g.addNode();
77             nodes[i].setString(LABEL, String.valueOf(i));
78         }
79         for ( int i = 0; i < n; ++i ) {
80             for ( int j = i; j < n; ++j )
81                 if ( i != j )
82                     g.addEdge(nodes[i], nodes[j]);
83         }
84         return g;
85     }
86     
87     /**
88      * Returns a graph structured as an m-by-n grid.
89      * @param m the number of rows of the grid
90      * @param n the number of columns of the grid
91      * @return an m-by-n grid structured graph
92      */

93     public static Graph getGrid(int m, int n) {
94         Graph g = new Graph();
95         g.getNodeTable().addColumns(LABEL_SCHEMA);
96         
97         Node[] nodes = new Node[m*n];
98         for ( int i = 0; i < m*n; ++i ) {
99             nodes[i] = g.addNode();
100             nodes[i].setString(LABEL, String.valueOf(i));
101             
102             if ( i >= n )
103                 g.addEdge(nodes[i-n], nodes[i]);
104             if ( i % n != 0 )
105                 g.addEdge(nodes[i-1], nodes[i]);
106         }
107         return g;
108     }
109     
110     public static Graph getHoneycomb(int levels) {
111         Graph g = new Graph();
112         g.getNodeTable().addColumns(LABEL_SCHEMA);
113         ArrayList JavaDoc layer1 = halfcomb(g, levels);
114         ArrayList JavaDoc layer2 = halfcomb(g, levels);
115         for ( int i=0; i<(levels<<1); ++i ) {
116             Node n1 = (Node)layer1.get(i);
117             Node n2 = (Node)layer2.get(i);
118             g.addEdge(n1, n2);
119         }
120         return g;
121     }
122     
123     private static ArrayList JavaDoc halfcomb(Graph g, int levels) {
124         ArrayList JavaDoc top = new ArrayList JavaDoc();
125         ArrayList JavaDoc layer = new ArrayList JavaDoc();
126         
127         int label = 0;
128         
129         for ( int i=0; i<levels; ++i ) {
130             Node n = g.addNode();
131             n.setString(LABEL, String.valueOf(label++));
132             top.add(n);
133         }
134         for ( int i=0; i<levels; ++i ) {
135             Node n = null;
136             for ( int j=0; j<top.size(); ++j ) {
137                 Node p = (Node)top.get(j);
138                 if ( n == null ) {
139                     n = g.addNode();
140                     n.setString(LABEL, String.valueOf(label++));
141                     layer.add(n);
142                 }
143                 g.addEdge(p, n);
144                 n = g.addNode();
145                 n.setString(LABEL, String.valueOf(label++));
146                 layer.add(n);
147                 g.addEdge(p, n);
148             }
149             if ( i == levels-1 ) {
150                 return layer;
151             }
152             top.clear();
153             for ( int j=0; j<layer.size(); ++j ) {
154                 Node p = (Node)layer.get(j);
155                 n = g.addNode();
156                 n.setString(LABEL, String.valueOf(label++));
157                 top.add(n);
158                 g.addEdge(p, n);
159             }
160             layer.clear();
161         }
162         // should never happen
163
return top;
164     }
165     
166     /**
167      * Returns a balanced tree of the requested breadth and depth.
168      * @param breadth the breadth of each level of the tree
169      * @param depth the depth of the tree
170      * @return a balanced tree
171      */

172     public static Tree getBalancedTree(int breadth, int depth) {
173         Tree t = new Tree();
174         t.getNodeTable().addColumns(LABEL_SCHEMA);
175         
176         Node r = t.addRoot();
177         r.setString(LABEL, "0,0");
178         
179         if ( depth > 0 )
180             balancedHelper(t, r, breadth, depth-1);
181         return t;
182     }
183     
184     private static void balancedHelper(Tree t, Node n,
185             int breadth, int depth)
186     {
187         for ( int i=0; i<breadth; ++i ) {
188             Node c = t.addChild(n);
189             c.setString(LABEL, i+","+c.getDepth());
190             if ( depth > 0 )
191                 balancedHelper(t,c,breadth,depth-1);
192         }
193     }
194     
195     /**
196      * Returns a left deep binary tree
197      * @param depth the depth of the tree
198      * @return the generated tree
199      */

200     public static Tree getLeftDeepTree(int depth) {
201         Tree t = new Tree();
202         t.getNodeTable().addColumns(LABEL_SCHEMA);
203         
204         Node r = t.addRoot();
205         r.setString(LABEL, "0,0");
206         
207         deepHelper(t, r, 2, depth, true);
208         return t;
209     }
210     
211     /**
212      * Returns a right deep binary tree
213      * @param depth the depth of the tree
214      * @return the generated Tree
215      */

216     public static Tree getRightDeepTree(int depth) {
217         Tree t = new Tree();
218         t.getNodeTable().addColumns(LABEL_SCHEMA);
219         
220         Node r = t.addRoot();
221         r.setString(LABEL, "0,0");
222         
223         deepHelper(t, r, 2, depth, false);
224         return t;
225     }
226     
227     /**
228      * Create a diamond tree, with a given branching factor at
229      * each level, and depth levels for the two main branches.
230      * @param b the number of children of each branch node
231      * @param d1 the length of the first (left) branch
232      * @param d2 the length of the second (right) branch
233      * @return the generated Tree
234      */

235     public static Tree getDiamondTree(int b, int d1, int d2) {
236         Tree t = new Tree();
237         t.getNodeTable().addColumns(LABEL_SCHEMA);
238         
239         Node r = t.addRoot();
240         r.setString(LABEL, "0,0");
241         
242         Node left = t.addChild(r);
243         left.setString(LABEL, "1,0");
244         Node right = t.addChild(r);
245         right.setString(LABEL, "1,1");
246         
247         deepHelper(t, left, b, d1-2, true);
248         deepHelper(t, right, b, d1-2, false);
249         
250         while ( left.getFirstChild() != null )
251             left = left.getFirstChild();
252         while ( right.getLastChild() != null )
253             right = right.getLastChild();
254         
255         deepHelper(t, left, b, d2-1, false);
256         deepHelper(t, right, b, d2-1, true);
257         
258         return t;
259     }
260     
261     private static void deepHelper(Tree t, Node n,
262             int breadth, int depth, boolean left)
263     {
264         Node c = t.addChild(n);
265         c.setString(LABEL, "0,"+c.getDepth());
266         if ( left && depth > 0 )
267             deepHelper(t, c, breadth, depth-1, left);
268         
269         for ( int i=1; i<breadth; ++i ) {
270             c = t.addChild(n);
271             c.setString(LABEL, i+","+c.getDepth());
272         }
273         if ( !left && depth > 0 )
274             deepHelper(t, c, breadth, depth-1, left);
275     }
276     
277     
278     // ------------------------------------------------------------------------
279

280     /** Label data field included in generated Graphs */
281     public static final String JavaDoc LABEL = "label";
282     /** Node table schema used for generated Graphs */
283     public static final Schema LABEL_SCHEMA = new Schema();
284     static {
285         LABEL_SCHEMA.addColumn(LABEL, String JavaDoc.class, "");
286     }
287     
288 } // end of class GraphLib
289
Popular Tags