View Javadoc

1   /*
2    * TouchGraph LLC. Apache-Style Software License
3    *
4    *
5    * Copyright (c) 2001-2002 Alexander Shapiro. All rights reserved.
6    *
7    * Redistribution and use in source and binary forms, with or without
8    * modification, are permitted provided that the following conditions
9    * are met:
10   *
11   * 1. Redistributions of source code must retain the above copyright
12   *    notice, this list of conditions and the following disclaimer. 
13   *
14   * 2. Redistributions in binary form must reproduce the above copyright
15   *    notice, this list of conditions and the following disclaimer in
16   *    the documentation and/or other materials provided with the
17   *    distribution.
18   *
19   * 3. The end-user documentation included with the redistribution,
20   *    if any, must include the following acknowledgment:  
21   *       "This product includes software developed by 
22   *        TouchGraph LLC (http://www.touchgraph.com/)."
23   *    Alternately, this acknowledgment may appear in the software itself,
24   *    if and wherever such third-party acknowledgments normally appear.
25   *
26   * 4. The names "TouchGraph" or "TouchGraph LLC" must not be used to endorse 
27   *    or promote products derived from this software without prior written 
28   *    permission.  For written permission, please contact 
29   *    alex@touchgraph.com
30   *
31   * 5. Products derived from this software may not be called "TouchGraph",
32   *    nor may "TouchGraph" appear in their name, without prior written
33   *    permission of alex@touchgraph.com.
34   *
35   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38   * DISCLAIMED.  IN NO EVENT SHALL TOUCHGRAPH OR ITS CONTRIBUTORS BE 
39   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
40   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
41   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
42   * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
43   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
44   * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 
45   * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46   * ====================================================================
47   *
48   */
49  
50  package com.touchgraph.graphlayout.graphelements;
51  
52  import java.util.*;
53  
54  import com.touchgraph.graphlayout.*;
55  
56  /***  GraphEltSet contains data about the graph's components. Currently
57    *  the only components are edges and nodes.
58    *
59    * @author   Alexander Shapiro
60    * @author   Murray Altheim (added support for IDs)
61    * @version  1.21  $Id: GraphEltSet.java,v 1.1.1.1 2004/02/06 08:44:07 keesj Exp $
62    */
63  public class GraphEltSet implements ImmutableGraphEltSet {
64  
65      protected Vector nodes;
66      protected Vector edges;
67  
68      /*** The Hashtable containing references to the Node IDs of the current graph.
69        */
70      protected Hashtable nodeIDRegistry = null;
71  
72    // ...........
73  
74      /*** Default constructor. */
75      public GraphEltSet() {
76          nodes = new Vector();
77          edges = new Vector();
78          nodeIDRegistry = new Hashtable(); // registry of Node IDs
79      }
80  
81    // Node manipulation ...........................
82  
83      /*** Return the Node at int <tt>index</tt>, null if none are available. */
84      protected Node nodeAt( int i ) {
85          if ( nodes.size() == 0 ) return null;
86          return (Node)nodes.elementAt(i);
87      }
88  
89      /*** Return the number of Nodes in the cumulative Vector. 
90        * @deprecated        this method has been replaced by the <tt>nodeCount()</tt> method.
91        */
92      public int nodeNum() {
93          return nodes.size(); 
94      }
95  
96      /*** Return the number of Nodes in the cumulative Vector. */
97      public int nodeCount() {
98          return nodes.size(); 
99      }
100 
101     /*** Return an iterator over the Nodes in the cumulative Vector, null if it is empty. */
102     public Iterator getNodes() {
103         if ( nodes.size() == 0 ) return null;
104         return nodes.iterator(); 
105     }
106 
107     /*** Registers the Node <tt>node</tt> via its ID String <tt>id</tt>. 
108       *
109       * @param id the ID of the object.
110       * @param node the Node to be registered.
111       */
112     //protected void registerNode( String id, Node node ) {
113   // FIXME
114     //}
115 
116     /*** Add the Node <tt>node</tt> to the graph, and 
117       * registers the Node via its ID. If no ID exists, no registration occurs. */
118     public void addNode( Node node ) throws TGException {
119         String id = node.getID();
120         if ( id != null ) {
121             if ( findNode(id) == null ) { // doesn't already exist
122                 nodeIDRegistry.put(id,node);
123                 nodes.addElement(node);
124             } else throw new TGException(TGException.NODE_EXISTS,"node ID '"+id+"' already exists.");
125         } else {
126             String label = node.getLabel().trim();
127             if (label == null) label = "";
128             if (!label.equals("") && findNode(node.getLabel()) == null ) {
129                 id = label;
130             } else {
131                 int i;
132                 for( i = 1; findNode( label +"-"+ i ) != null; i++ );
133                 id = label + "-" + i; 
134             } 
135             node.setID(id);
136             nodeIDRegistry.put(id,node);
137             nodes.addElement(node);   
138         }
139         //} else throw new TGException(TGException.NODE_NO_ID,"node has no ID."); // could be ignored?
140     }
141 
142     /*** Returns true if the graph contains the Node <tt>node</tt>. */
143     public boolean contains( Node node ) {
144         return nodes.contains(node);
145     }
146 
147   // Edge manipulation ...........................
148 
149     /*** Return the Edge at int <tt>index</tt>, null if none are available. */
150     protected Edge edgeAt( int index ) {
151         if ( edges.size() == 0 ) return null;
152         return (Edge)edges.elementAt(index);
153     }
154 
155     /*** Return the number of Edges in the cumulative Vector. 
156       * @deprecated        this method has been replaced by the <tt>edgeCount()</tt> method.
157       */
158     public int edgeNum() {
159         return edges.size(); 
160     }
161 
162     /*** Return the number of Edges in the cumulative Vector. */
163     public int edgeCount() {
164         return edges.size(); 
165     }
166 
167     /*** Return an iterator over the Edges in the cumulative Vector, null if it is empty. */
168     public Iterator getEdges() {
169         if ( edges.size() == 0 ) return null;
170         else return edges.iterator(); 
171     }
172 
173     /*** Add the Edge <tt>edge</tt> to the graph. */
174     public void addEdge( Edge edge ) {
175         if ( edge == null ) return;
176         if(!contains(edge)) {
177             edges.addElement(edge);
178             edge.from.addEdge(edge);
179             edge.to.addEdge(edge);
180         }
181     }
182 
183     /*** Add an Edge from Node <tt>from</tt> to Node <tt>to</tt>, 
184       * with tension of int <tt>tension</tt>, returning the Edge.
185       */
186     public Edge addEdge( Node from, Node to, int tension ) {
187         Edge edge = null;
188         if ( from != null && to != null ) {
189              edge = new Edge(from,to,tension);
190              addEdge(edge);
191          }
192          return edge;
193     }
194 
195     /*** Returns true if the graph contains the Edge <tt>edge</tt>. */
196     public boolean contains( Edge edge ) {
197         return edges.contains(edge);
198     }
199 
200     /*** Return the Node whose ID matches the String <tt>id</tt>, null if no match is found. */
201     public Node findNode( String id ) {
202         if ( id == null ) return null; // ignore
203         return (Node)nodeIDRegistry.get(id);
204     }
205 
206    /*** Return a Collection of all Nodes whose label matches the String <tt>label</tt>, 
207      * null if no match is found. */
208     public Collection findNodesByLabel( String label ) {
209         Vector nodelist = new Vector();
210         for ( int i = 0 ; i < nodeCount() ; i++) {
211             if (nodeAt(i)!=null && nodeAt(i).getLabel().equals(label)) {
212                 nodelist.add(nodeAt(i));
213             }
214         }
215         if ( nodelist.size() == 0 ) return null;
216         else return nodelist;
217     }
218 
219    /*** Return the first Nodes whose label contains the String <tt>substring</tt>, 
220      * null if no match is found. */
221     public Node findNodeLabelContaining( String substring ) {
222          for ( int i = 0 ; i < nodeCount() ; i++) {
223             if (nodeAt(i)!=null && nodeAt(i).getLabel().toLowerCase().equals(substring.toLowerCase())) {
224                 return nodeAt(i);
225             }
226         }
227                
228         for ( int i = 0 ; i < nodeCount() ; i++) {
229             if (nodeAt(i)!=null && nodeAt(i).getLabel().toLowerCase().indexOf(
230                                         substring.toLowerCase())>-1) {
231                 return nodeAt(i);
232             }
233         }
234         return null;
235     }
236 
237     /*** Return an Edge spanning Node <tt>from</tt> to Node <tt>to</tt>. */
238     public Edge findEdge( Node from, Node to ) {
239         for ( int i = 0 ; i < from.edgeCount(); i++ ) {
240             Edge e = from.edgeAt(i);
241             if (e.to == to) return e;
242         }
243         return null;
244     }
245 
246     /*** Delete the Edge <tt>edge</tt>. */
247     public boolean deleteEdge( Edge edge ) {
248         synchronized(edges) {
249             if ( edge == null ) return false;
250             if (!edges.removeElement(edge)) return false;
251             edge.from.removeEdge(edge);
252             edge.to.removeEdge(edge);
253             return true;
254         }
255     }
256 
257     /*** Delete the Edges contained within the Vector <tt>edgedToDelete</tt>. */
258     public void deleteEdges( Vector edgesToDelete ) {
259         synchronized(edges) {
260             for (int i=0;i<edgesToDelete.size();i++) {
261                 deleteEdge((Edge) edgesToDelete.elementAt(i));
262             }
263         }
264     }
265 
266    /*** Delete the Edge spanning Node <tt>from</tt> to Node <tt>to</tt>,
267      * returning true if successful. */
268     public boolean deleteEdge( Node from, Node to ) {
269         synchronized(edges) {
270             Edge e = findEdge(from,to);
271             if (e!=null) return deleteEdge(e);
272             return false;
273         }
274     }
275 
276     /*** Delete the Node <tt>node</tt>, returning true if successful. */
277     public boolean deleteNode( Node node ) {
278         synchronized (nodes) {
279             if ( node == null ) return false;
280             if ( !nodes.removeElement(node) ) return false;
281         
282             String id = node.getID();
283             if ( id != null ) nodeIDRegistry.remove(id); // remove from registry
284 
285             for ( int i = 0 ; i < node.edgeCount(); i++ ) {
286                 Edge e = node.edgeAt(i);
287                 if ( e.from == node ) {
288                     edges.removeElement(e); // Delete edge not used, because it would change the node's edges
289                     e.to.removeEdge(e);     // vector which is being iterated on.
290                 } else if ( e.to == node ) {
291                     edges.removeElement(e);
292                     e.from.removeEdge(e);
293                 }
294                 //No edges are deleted from node.  Hopefully garbage collection will pick them up.
295             }
296          }
297          return true;
298     }
299 
300     /*** Delete the Nodes contained within the Vector <tt>nodesToDelete</tt>. */
301     public void deleteNodes( Vector nodesToDelete ) {
302         synchronized (nodes) {
303             for (int i=0;i<nodesToDelete.size();i++) {
304                 deleteNode((Node)nodesToDelete.elementAt(i));
305             }
306         }   
307     }
308 
309     /*** Returns a random node, or null if none exist (for making random graphs). */
310     public Node getRandomNode() {
311         if ( nodes.size() == 0 ) return null;
312         int r=(int) (Math.random()*nodeCount());
313         return nodeAt(r);
314     }
315 
316     /*** Return the first Node, null if none exist. */
317     public Node getFirstNode() {
318         if ( nodes.size() == 0 ) return null;
319         else return nodeAt(0);
320     }
321 
322     /*** Clear all nodes and edges. */
323     public void clearAll() {
324         synchronized(nodes) {
325             synchronized(edges) {
326                 nodes.removeAllElements();
327                 edges.removeAllElements();
328                 nodeIDRegistry.clear();
329             }
330         }
331     }
332 
333    /*** A way of iterating through all the nodes.
334      * Maybe too complex, and should be replaced by iterators.
335      */
336     public void forAllNodes( TGForEachNode fen ) {
337         synchronized(nodes) {
338             for (int i=0;i<nodeCount();i++) {
339                 Node n = nodeAt(i);
340                 fen.forEachNode(n);
341             }
342         }
343     }
344 
345     /*** iterates through pairs of Nodes. */
346     public void forAllNodePairs( TGForEachNodePair fenp ) {
347         synchronized(nodes) {
348             for (int i=0;i<nodeCount();i++) {
349                 Node n1=nodeAt(i);
350                 fenp.beforeInnerLoop(n1);            
351                 for (int j=i+1;j<nodeCount();j++)
352                     fenp.forEachNodePair(n1, nodeAt(j));            
353                 fenp.afterInnerLoop(n1);
354             }
355         }
356     }
357 
358     /*** Iterates through Edges. */
359     public void forAllEdges( TGForEachEdge fee ) {
360         synchronized(edges) {
361             for (int i=0;i<edgeCount();i++) {
362                 Edge e = edgeAt(i);
363                 fee.forEachEdge(e);
364             }
365         }
366     }
367     
368 } // end com.touchgraph.graphlayout.graphelements.GraphEltSet