GraphLib


1   package prefuse.util;
2   
3   import java.util.ArrayList  ;
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   layer1 = halfcomb(g, levels);
114         ArrayList   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   halfcomb(Graph g, int levels) {
124         ArrayList   top   = new ArrayList  ();
125         ArrayList   layer = new ArrayList  ();
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   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  .class, "");
286     }
287     
288 } // end of class GraphLib
289
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags