Graph


1   package prefuse.data;
2   
3   import java.util.Iterator  ;
4   
5   import prefuse.data.column.Column;
6   import prefuse.data.event.ColumnListener;
7   import prefuse.data.event.EventConstants;
8   import prefuse.data.event.GraphListener;
9   import prefuse.data.event.TableListener;
10  import prefuse.data.expression.Predicate;
11  import prefuse.data.tuple.CompositeTupleSet;
12  import prefuse.data.tuple.TableEdge;
13  import prefuse.data.tuple.TableNode;
14  import prefuse.data.tuple.TupleManager;
15  import prefuse.data.tuple.TupleSet;
16  import prefuse.data.util.Index;
17  import prefuse.data.util.NeighborIterator;
18  import prefuse.util.PrefuseConfig;
19  import prefuse.util.TypeLib;
20  import prefuse.util.collections.CompositeIntIterator;
21  import prefuse.util.collections.CompositeIterator;
22  import prefuse.util.collections.CopyOnWriteArrayList;
23  import prefuse.util.collections.IntArrayIterator;
24  import prefuse.util.collections.IntIterator;
25  
26  /**
27   * <p>A Graph models a network of nodes connected by a collection of edges.
28   * Both nodes and edges can have any number of associated data fields.
29   * Additionally, edges are either directed or undirected, indicating a
30   * possible directionality of the connection. Each edge has both a source
31   * node and a target node, for a directed edge this indicates the
32   * directionality, for an undirected edge this is just an artifact
33   * of the order in which the nodes were specified when added to the graph.
34   * </p>
35   * 
36   * <p>Both nodes and edges are represented by backing data {@link Table}
37   * instances storing the data attributes. For edges, this table must
38   * also contain a source node field and a target node field. The default
39   * column name for these fields are {@link #DEFAULT_SOURCE_KEY} and
40   * {@link #DEFAULT_TARGET_KEY}, but these can be configured by the graph
41   * constructor. These columns should be integer valued, and contain
42   * either the row number for a corresponding node in the node table,
43   * or another unique identifier for a node. In this second case, the
44   * unique identifier must be included as a data field in the node
45   * table. This name of this column can be configured using the appropriate
46   * graph constructor. The default column name for this field is
47   * {@link #DEFAULT_NODE_KEY}, which by default evaluates to null,
48   * indicating that no special node key should be used, just the direct
49   * node table row numbers. Though the source, target, and node key
50   * values completely specify the graph linkage structure, to make
51   * graph operations more efficient an additional table is maintained
52   * internally by the Graph class, storing node indegree and outdegree
53   * counts and adjacency lists for the inlinks and outlinks for all nodes.</p>
54   * 
55   * <p>Graph nodes and edges can be accessed by application code by either
56   * using the row numbers of the node and edge tables, which provide unique ids
57   * for each, or using the {@link prefuse.data.Node} and
58   * {@link prefuse.data.Edge} classes --
59   * {@link prefuse.data.Tuple} instances that provide
60   * object-oriented access to both node or edge data values and the
61   * backing graph structure. Node and Edge tuples are maintained by
62   * special TupleManager instances contained within this Graph. By default, they
63   * are not accessible from the backing node or edge tables directly. The reason
64   * for this is that these tables might be used in multiple graphs
65   * simultaneously. For example, a node data table could be used in a number of
66   * different graphs, exploring different possible linkages between those node.
67   * In short, use this Graph instance to request iterators over Node or
68   * Edge tuples, not the backing data tables.</p>
69   * 
70   * <p>All Graph instances also support an internally generated
71   * spanning tree, provided by the {@link #getSpanningTree()} or
72   * {@link #getSpanningTree(Node)} methods. This is particularly
73   * useful in visualization contexts that use an underlying tree structure
74   * to compute a graph layout.</p>
75   * 
76   * @author <a HREF="http://jheer.org">jeffrey heer</a>
77   */
78  public class Graph extends CompositeTupleSet {
79      
80      /** Indicates incoming edges (inlinks) */
81      public static final int INEDGES    = 0;
82      /** Indicates outgoing edges (outlinks) */
83      public static final int OUTEDGES   = 1;
84      /** Indicates all edges, regardless of direction */
85      public static final int UNDIRECTED = 2;
86      
87      /** Default data field used to uniquely identify a node */
88      public static final String   DEFAULT_NODE_KEY 
89          = PrefuseConfig.get("data.graph.nodeKey");
90      /** Default data field used to denote the source node in an edge table */
91      public static final String   DEFAULT_SOURCE_KEY 
92          = PrefuseConfig.get("data.graph.sourceKey");
93      /** Default data field used to denote the target node in an edge table */
94      public static final String   DEFAULT_TARGET_KEY 
95          = PrefuseConfig.get("data.graph.targetKey"); 
96      /** Data group name to identify the nodes of this graph */
97      public static final String   NODES 
98          = PrefuseConfig.get("data.graph.nodeGroup");
99      /** Data group name to identify the edges of this graph */
100     public static final String   EDGES 
101         = PrefuseConfig.get("data.graph.edgeGroup");
102     
103     // -- auxiliary data structures -----
104     
105     /** Table containing the adjacency lists for the graph */
106     protected Table m_links;
107     /** TupleManager for managing Node tuple instances */
108     protected TupleManager m_nodeTuples;
109     /** TupleManager for managing Edge tuple instances */
110     protected TupleManager m_edgeTuples;
111     
112     /** Indicates if this graph is directed or undirected */
113     protected boolean      m_directed = false;
114     /** The spanning tree over this graph */
115     protected SpanningTree m_spanning = null;
116     
117     /** The node key field (for the Node table) */
118     protected String   m_nkey;
119     /** The source node key field (for the Edge table) */
120     protected String   m_skey;
121     /** The target node key field (for the Edge table) */
122     protected String   m_tkey;
123     /** Reference to an index over the node key field */
124     protected Index m_nidx;
125     /** Indicates if the key values are of type long */
126     protected boolean m_longKey = false;
127     /** Update listener */
128     private Listener m_listener;
129     /** Listener list */
130     private CopyOnWriteArrayList m_listeners = new CopyOnWriteArrayList();
131     
132     // ------------------------------------------------------------------------
133     // Constructors
134     
135     /**
136      * Creates a new, empty undirected Graph.
137      */
138     public Graph() {
139         this(false);
140     }
141     
142     /**
143      * Creates a new, empty Graph.
144      * @param directed true for directed edges, false for undirected
145      */
146     public Graph(boolean directed) {
147         this(new Table(), directed);
148     }
149 
150     /**
151      * Create a new Graph using the provided table of node data and
152      * an empty set of edges.
153      * @param nodes the backing table to use for node data.
154      * Node instances of this graph will get their data from this table.
155      * @param directed true for directed edges, false for undirected
156      */
157     public Graph(Table nodes, boolean directed) {
158         this(nodes, directed, DEFAULT_NODE_KEY,
159                 DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
160     }
161  
162     /**
163      * Create a new Graph using the provided table of node data and
164      * an empty set of edges.
165      * @param nodes the backing table to use for node data.
166      * Node instances of this graph will get their data from this table.
167      * @param directed true for directed edges, false for undirected
168      * @param nodeKey data field used to uniquely identify a node. If this
169      * field is null, the node table row numbers will be used
170      * @param sourceKey data field used to denote the source node in an edge
171      * table
172      * @param targetKey data field used to denote the target node in an edge
173      * table
174      */
175     public Graph(Table nodes, boolean directed, String   nodeKey,
176             String   sourceKey, String   targetKey) {
177         Table edges = new Table();
178         edges.addColumn(sourceKey, int.class, new Integer  (-1));
179         edges.addColumn(targetKey, int.class, new Integer  (-1));
180         init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
181     }
182     
183     /**
184      * Create a new Graph, using node table row numbers to uniquely
185      * identify nodes in the edge table's source and target fields.
186      * @param nodes the backing table to use for node data.
187      * Node instances of this graph will get their data from this table.
188      * @param edges the backing table to use for edge data.
189      * Edge instances of this graph will get their data from this table.
190      * @param directed true for directed edges, false for undirected
191      */
192     public Graph(Table nodes, Table edges, boolean directed) {
193         this(nodes, edges, directed,
194             DEFAULT_NODE_KEY, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
195     }
196     
197     /**
198      * Create a new Graph, using node table row numbers to uniquely
199      * identify nodes in the edge table's source and target fields.
200      * @param nodes the backing table to use for node data.
201      * Node instances of this graph will get their data from this table.
202      * @param edges the backing table to use for edge data.
203      * Edge instances of this graph will get their data from this table.
204      * @param directed true for directed edges, false for undirected
205      * @param sourceKey data field used to denote the source node in an edge
206      * table
207      * @param targetKey data field used to denote the target node in an edge
208      * table
209      */
210     public Graph(Table nodes, Table edges, boolean directed,
211             String   sourceKey, String   targetKey)
212     {
213         init(nodes, edges, directed, DEFAULT_NODE_KEY, sourceKey, targetKey);
214     }
215     
216     /**
217      * Create a new Graph.
218      * @param nodes the backing table to use for node data.
219      * Node instances of this graph will get their data from this table.
220      * @param edges the backing table to use for edge data.
221      * Edge instances of this graph will get their data from this table.
222      * @param directed true for directed edges, false for undirected
223      * @param nodeKey data field used to uniquely identify a node. If this
224      * field is null, the node table row numbers will be used
225      * @param sourceKey data field used to denote the source node in an edge
226      * table
227      * @param targetKey data field used to denote the target node in an edge
228      * table
229      */
230     public Graph(Table nodes, Table edges, boolean directed,
231             String   nodeKey, String   sourceKey, String   targetKey)
232     {
233         init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
234     }
235     
236     // ------------------------------------------------------------------------
237     // Initialization
238     
239     /**
240      * Initialize this Graph instance.
241      * @param nodes the node table
242      * @param edges the edge table
243      * @param directed the edge directionality
244      * @param nodeKey data field used to uniquely identify a node
245      * @param sourceKey data field used to denote the source node in an edge
246      * table
247      * @param targetKey data field used to denote the target node in an edge
248      * table
249      */
250     protected void init(Table nodes, Table edges, boolean directed, 
251             String   nodeKey, String   sourceKey, String   targetKey)
252     {
253         // sanity check
254         if ( (nodeKey!=null && 
255               !TypeLib.isIntegerType(nodes.getColumnType(nodeKey)))  ||
256               !TypeLib.isIntegerType(edges.getColumnType(sourceKey)) ||
257               !TypeLib.isIntegerType(edges.getColumnType(targetKey)) )
258         {
259             throw new IllegalArgumentException  (
260                 "Incompatible column types for graph keys");
261         }
262         
263         removeAllSets();
264         super.addSet(EDGES, edges);
265         super.addSet(NODES, nodes);
266         
267         m_directed = directed;
268         
269         // INVARIANT: these three should all reference the same type
270         // currently limited to int
271         m_nkey = nodeKey;
272         m_skey = sourceKey;
273         m_tkey = targetKey;
274         
275         // set up indices
276         if ( nodeKey != null ) {
277             if ( nodes.getColumnType(nodeKey) == long.class )
278                 m_longKey = true;
279             nodes.index(nodeKey);
280             m_nidx = nodes.getIndex(nodeKey);
281         }
282         
283         // set up tuple manager
284         if ( m_nodeTuples == null )
285             m_nodeTuples = new TupleManager(nodes, this, TableNode.class);
286         m_edgeTuples = new TupleManager(edges, this, TableEdge.class);
287         
288         // set up node attribute optimization
289         initLinkTable();
290         
291         // set up listening
292         if ( m_listener == null )
293             m_listener = new Listener();
294         nodes.addTableListener(m_listener);
295         edges.addTableListener(m_listener);
296         m_listener.setEdgeTable(edges);
297     }
298     
299     /**
300      * Set the tuple managers used to manage the Node and Edge tuples of this
301      * Graph.
302      * @param ntm the TupleManager to use for nodes
303      * @param etm the TupleManager to use for edges
304      */
305     public void setTupleManagers(TupleManager ntm, TupleManager etm) {
306         if ( !Node.class.isAssignableFrom(ntm.getTupleType()) )
307             throw new IllegalArgumentException  ("The provided node " +
308                 "TupleManager must generate tuples that implement " +
309                 "the Node interface.");
310         if ( !Edge.class.isAssignableFrom(etm.getTupleType()) )
311             throw new IllegalArgumentException  ("The provided edge " +
312                 "TupleManager must generate tuples that implement " +
313                 "the Edge interface.");
314         m_nodeTuples = ntm;
315         m_edgeTuples = etm;
316     }
317     
318     /**
319      * Dispose of this graph. Unregisters this graph as a listener to its
320      * included tables.
321      */
322     public void dispose() {
323         getNodeTable().removeTableListener(m_listener);
324         getEdgeTable().removeTableListener(m_listener);
325     }
326     
327     /**
328      * Updates this graph to use a different edge structure for the same nodes.
329      * All other settings will remain the same (e.g., directionality, keys)
330      * @param edges the new edge table.
331      */
332     public void setEdgeTable(Table edges) {
333         Table oldEdges = getEdgeTable();
334         oldEdges.removeTableListener(m_listener);
335         m_edgeTuples.invalidateAll();
336         m_links.clear();
337         
338         init(getNodeTable(), edges, m_directed, m_nkey, m_skey, m_tkey);
339     }
340     
341     // ------------------------------------------------------------------------
342     // Data Access Optimization
343     
344     /**
345      * Initialize the link table, which holds adjacency lists for this graph.
346      */
347     protected void initLinkTable() {
348         // set up cache of node data
349         m_links = createLinkTable();
350                 
351         IntIterator edges = getEdgeTable().rows();
352         while ( edges.hasNext() ) {
353             updateDegrees(edges.nextInt(), 1);
354         }
355     }
356     
357     /**
358      * Instantiate and return the link table.
359      * @return the created link table
360      */
361     protected Table createLinkTable() {
362         return LINKS_SCHEMA.instantiate(getNodeTable().getMaximumRow()+1);
363     }
364     
365     /**
366      * Internal method for updating the linkage of this graph.
367      * @param e the edge id for the updated link
368      * @param incr the increment value, 1 for an added link,
369      * -1 for a removed link
370      */
371     protected void updateDegrees(int e, int incr) {
372         if ( !getEdgeTable().isValidRow(e) ) return;
373         int s = getSourceNode(e);
374         int t = getTargetNode(e);
375         if ( s < 0 || t < 0 ) return;
376         updateDegrees(e, s, t, incr);
377         if ( incr < 0 ) {
378             m_edgeTuples.invalidate(e);
379         }
380     }
381     
382     /**
383      * Internal method for updating the linkage of this graph.
384      * @param e the edge id for the updated link
385      * @param s the source node id for the updated link
386      * @param t the target node id for the updated link
387      * @param incr the increment value, 1 for an added link,
388      * -1 for a removed link
389      */
390     protected void updateDegrees(int e, int s, int t, int incr) {
391         int od = m_links.getInt(s, OUTDEGREE);
392         int id = m_links.getInt(t, INDEGREE);
393         // update adjacency lists
394         if ( incr > 0 ) {
395             // add links
396             addLink(OUTLINKS, od, s, e);
397             addLink(INLINKS, id, t, e);
398         } else if ( incr < 0 ) {
399             // remove links
400             remLink(OUTLINKS, od, s, e);
401             remLink(INLINKS, id, t, e);
402         }
403         // update degree counts
404         m_links.setInt(s, OUTDEGREE, od+incr);
405         m_links.setInt(t, INDEGREE, id+incr);
406         // link structure changed, invalidate spanning tree
407         m_spanning = null;
408     }
409     
410     /**
411      * Internal method for adding a link to an adjacency list
412      * @param field which adjacency list (inlinks or outlinks) to use
413      * @param len the length of the adjacency list
414      * @param n the node id of the adjacency list to use
415      * @param e the edge to add to the list
416      */
417     protected void addLink(String   field, int len, int n, int e) {
418         int[] array = (int[])m_links.get(n, field);
419         if ( array == null ) {
420             array = new int[] {e};
421             m_links.set(n, field, array);
422             return;
423         } else if ( len == array.length ) {
424             int[] narray = new int[Math.max(3*array.length/2, len+1)];
425             System.arraycopy(array, 0, narray, 0, array.length);
426             array = narray;
427             m_links.set(n, field, array);
428         }
429         array[len] = e;
430     }
431     
432     /**
433      * Internal method for removing a link from an adjacency list
434      * @param field which adjacency list (inlinks or outlinks) to use
435      * @param len the length of the adjacency list
436      * @param n the node id of the adjacency list to use
437      * @param e the edge to remove from the list
438      * @return true if the link was removed successfully, false otherwise
439      */
440     protected boolean remLink(String   field, int len, int n, int e) {
441         int[] array = (int[])m_links.get(n, field);
442         for ( int i=0; i<len; ++i ) {
443             if ( array[i] == e ) {
444                 System.arraycopy(array, i+1, array, i, len-i-1);
445                 return true;
446             }
447         }
448         return false;
449     }
450     
451     /**
452      * Update the link table to accomodate an inserted or deleted node
453      * @param r the node id, also the row number into the link table
454      * @param added indicates if a node was added or removed
455      */
456     protected void updateNodeData(int r, boolean added) {
457         if ( added ) {
458             m_links.addRow();
459         } else {
460             m_nodeTuples.invalidate(r);
461             m_links.removeRow(r);
462         }
463     }
464     
465     // ------------------------------------------------------------------------
466     // Key Transforms
467     
468     /**
469      * Get the data field used to uniquely identify a node
470      * @return the data field used to uniquely identify a node
471      */
472     public String   getNodeKeyField() {
473         return m_nkey;
474     }
475     
476     /**
477      * Get the data field used to denote the source node in an edge table.
478      * @return the data field used to denote the source node in an edge table.
479      */
480     public String   getEdgeSourceField() {
481         return m_skey;
482     }
483     
484     /**
485      * Get the data field used to denote the target node in an edge table.
486      * @return the data field used to denote the target node in an edge table.
487      */
488     public String   getEdgeTargetField() {
489         return m_tkey;
490     }
491     
492     /**
493      * Given a node id (a row number in the node table), get the value of
494      * the node key field.
495      * @param node the node id
496      * @return the value of the node key field for the given node
497      */
498     public long getKey(int node) {
499         return m_nkey == null ? node : getNodeTable().getLong(node, m_nkey);
500     }
501     
502     /**
503      * Given a value of the node key field, get the node id (the row number
504      * in the node table).
505      * @param key a node key field value
506      * @return the node id (the row number in the node table)
507      */
508     public int getNodeIndex(long key) {
509         if ( m_nidx == null ) {
510             return (int)key;
511         } else {
512             int idx = m_longKey ? m_nidx.get(key) : m_nidx.get((int)key);
513             return idx<0 ? -1 : idx;
514         }
515     }
516     
517     // ------------------------------------------------------------------------
518     // Graph Mutators
519     
520     /**
521      * Add row to the node table, thereby adding a node to the graph.
522      * @return  the node id (node table row number) of the added node
523      */
524     public int addNodeRow() {
525         return getNodeTable().addRow();
526     }
527     
528     /**
529      * Add a new node to the graph.
530      * @return the new Node instance
531      */
532     public Node addNode() {
533         int nrow = addNodeRow();
534         return (Node)m_nodeTuples.getTuple(nrow);
535     }
536     
537     /**
538      * Add an edge to the graph. Both multiple edges between two nodes
539      * and edges from a node to itself are allowed.
540      * @param s the source node id
541      * @param t the target node id
542      * @return the edge id (edge table row number) of the added edge
543      */
544     public int addEdge(int s, int t) {
545         // get keys for the nodes
546         long key1 = getKey(s);
547         long key2 = getKey(t);
548         
549         // add edge row, set source/target fields
550         Table edges = getEdgeTable();
551         int r = edges.addRow();
552         if ( m_longKey ) {
553             edges.setLong(r, m_skey, key1);
554             edges.setLong(r, m_tkey, key2);
555         } else {
556             edges.setInt(r, m_skey, (int)key1);
557             edges.setInt(r, m_tkey, (int)key2);
558         }
559         return r;
560     }
561     
562     /**
563      * Add an edge to the graph.
564      * @param s the source Node
565      * @param t the target Node
566      * @return the new Edge instance
567      */
568     public Edge addEdge(Node s, Node t) {
569         nodeCheck(s, true);
570         nodeCheck(t, true);
571         int e = addEdge(s.getRow(), t.getRow());
572         return getEdge(e);
573     }
574     
575     /**
576      * Remove a node from the graph, also removing all incident edges.
577      * @param node the node id (node table row number) of the node to remove
578      * @return true if the node was successfully removed, false if the
579      * node id was not found or was not valid
580      */
581     public boolean removeNode(int node) {
582         Table nodeTable = getNodeTable();
583         if ( nodeTable.isValidRow(node) ) {
584             int id = getInDegree(node);
585             if ( id > 0 ) {
586                 int[] links = (int[])m_links.get(node, INLINKS);
587                 for ( int i=id; --i>=0; )
588                     removeEdge(links[i]);
589             }
590             int od = getOutDegree(node);
591             if ( od > 0 ) {
592                 int[] links = (int[])m_links.get(node, OUTLINKS);
593                 for ( int i=od; --i>=0; )
594                     removeEdge(links[i]);
595             }
596         }
597         return nodeTable.removeRow(node);
598     }
599     
600     /**
601      * Remove a node from the graph, also removing all incident edges.
602      * @param n the Node to remove from the graph
603      * @return true if the node was successfully removed, false if the
604      * node was not found in this graph
605      */
606     public boolean removeNode(Node n) {
607         nodeCheck(n, true);
608         return removeNode(n.getRow());
609     }
610     
611     /**
612      * Remove an edge from the graph.
613      * @param edge the edge id (edge table row number) of the edge to remove
614      * @return true if the edge was successfully removed, false if the
615      * edge was not found or was not valid
616      */
617     public boolean removeEdge(int edge) {
618         return getEdgeTable().removeRow(edge);
619     }
620     
621     /**
622      * Remove an edge from the graph.
623      * @param e the Edge to remove from the graph
624      * @return true if the edge was successfully removed, false if the
625      * edge was not found in this graph
626      */
627     public boolean removeEdge(Edge e) {
628         edgeCheck(e, true);
629         return removeEdge(e.getRow());
630     }
631     
632     /**
633      * Internal method for clearing the edge table, removing all edges.
634      */
635     protected void clearEdges() {
636         getEdgeTable().clear();
637     }
638     
639     // ------------------------------------------------------------------------
640     // Node Accessor Methods
641     
642     /**
643      * Internal method for checking the validity of a node.
644      * @param n the Node to check for validity
645      * @param throwException true if this method should throw an Exception
646      * when an invalid node is encountered
647      * @return true is the node is valid, false if invalid
648      */
649     protected boolean nodeCheck(Node n, boolean throwException) {
650         if ( !n.isValid() ) {
651             if ( throwException ) {
652                 throw new IllegalArgumentException  (
653                     "Node must be valid.");
654             }
655             return false;
656         }
657         Graph ng = n.getGraph();
658         if ( ng != this && ng.m_spanning != this ) {
659             if ( throwException ) {
660                 throw new IllegalArgumentException  (
661                     "Node must be part of this Graph.");
662             }
663             return false;
664         }
665         return true;
666     }
667     
668     /**
669      * Get the collection of nodes as a TupleSet. Returns the same result as
670      * {@link CompositeTupleSet#getSet(String)} using
671      * {@link #NODES} as the parameter.
672      * @return the nodes of this graph as a TupleSet instance
673      */
674     public TupleSet getNodes() {
675         return getSet(NODES);
676     }
677     
678     /**
679      * Get the backing node table.
680      * @return the table of node values
681      */
682     public Table getNodeTable() {
683         return (Table)getSet(NODES);
684     }
685     
686     /**
687      * Get the number of nodes in this graph.
688      * @return the number of nodes
689      */
690     public int getNodeCount() {
691         return getNodeTable().getRowCount();
692     }
693     
694     /**
695      * Get the Node tuple instance corresponding to a node id.
696      * @param n a node id (node table row number)
697      * @return the Node instance corresponding to the node id
698      */
699     public Node getNode(int n) {
700         return (Node)m_nodeTuples.getTuple(n);
701     }
702     
703     /**
704      * Get the Node tuple corresponding to the input node key field value.
705      * The node key field is used to find the node id (node table row number),
706      * which is then used to retrieve the Node tuple.
707      * @param key a node key field value
708      * @return the requested Node instance
709      */
710     public Node getNodeFromKey(long key) {
711         int n = getNodeIndex(key);
712         return (n<0 ? null : getNode(n) );
713     }
714     
715     /**
716      * Get the in-degree of a node, the number of edges for which the node
717      * is the target.
718      * @param node the node id (node table row number)
719      * @return the in-degree of the node
720      */
721     public int getInDegree(int node) {
722         return m_links.getInt(node, INDEGREE);
723     }
724     
725     /**
726      * Get the in-degree of a node, the number of edges for which the node
727      * is the target.
728      * @param n the Node instance
729      * @return the in-degree of the node
730      */
731     public int getInDegree(Node n) {
732         nodeCheck(n, true);
733         return getInDegree(n.getRow());
734     }
735     
736     /**
737      * Get the out-degree of a node, the number of edges for which the node
738      * is the source.
739      * @param node the node id (node table row number)
740      * @return the out-degree of the node
741      */
742     public int getOutDegree(int node) {
743         return m_links.getInt(node, OUTDEGREE);
744     }
745     
746     /**
747      * Get the out-degree of a node, the number of edges for which the node
748      * is the source.
749      * @param n the Node instance
750      * @return the out-degree of the node
751      */
752     public int getOutDegree(Node n) {
753         nodeCheck(n, true);
754         return getOutDegree(n.getRow());
755     }
756     
757     /**
758      * Get the degree of a node, the number of edges for which a node
759      * is either the source or the target.
760      * @param node the node id (node table row number)
761      * @return the total degree of the node
762      */
763     public int getDegree(int node) {
764         return getInDegree(node) + getOutDegree(node);
765     }
766     
767     /**
768      * Get the degree of a node, the number of edges for which a node
769      * is either the source or the target.
770      * @param n the Node instance
771      * @return the total degree of the node
772      */
773     public int getDegree(Node n) {
774         nodeCheck(n, true);
775         return getDegree(n.getRow());
776     }
777     
778     // ------------------------------------------------------------------------
779     // Edge Accessor Methods
780     
781     /**
782      * Indicates if the edges of this graph are directed or undirected.
783      * @return true if directed edges, false if undirected edges
784      */
785     public boolean isDirected() {
786         return m_directed;
787     }
788     
789     /**
790      * Internal method for checking the validity of an edge.
791      * @param e the Edge to check for validity
792      * @param throwException true if this method should throw an Exception
793      * when an invalid node is encountered
794      * @return true is the edge is valid, false if invalid
795      */
796     protected boolean edgeCheck(Edge e, boolean throwException) {
797         if ( !e.isValid() ) {
798             if ( throwException ) {
799                 throw new IllegalArgumentException  (
800                     "Edge must be valid.");
801             }
802             return false;
803         }
804         if ( e.getGraph() != this ) {
805             if ( throwException ) {
806                 throw new IllegalArgumentException  (
807                     "Edge must be part of this Graph.");
808             }
809             return false;
810         }
811         return true;
812     }
813     
814     /**
815      * Get the collection of edges as a TupleSet. Returns the same result as
816      * {@link CompositeTupleSet#getSet(String)} using
817      * {@link #EDGES} as the parameter.
818      * @return the edges of this graph as a TupleSet instance
819      */
820     public TupleSet getEdges() {
821         return getSet(EDGES);
822     }
823 
824     /**
825      * Get the backing edge table.
826      * @return the table of edge values
827      */
828     public Table getEdgeTable() {
829         return (Table)getSet(EDGES);
830     }
831     /**
832      * Get the number of edges in this graph.
833      * @return the number of edges
834      */
835     public int getEdgeCount() {
836         return getEdgeTable().getRowCount();
837     }
838 
839     /**
840      * Get the Edge tuple instance corresponding to an edge id.
841      * @param e an edge id (edge table row number)
842      * @return the Node instance corresponding to the node id
843      */
844     public Edge getEdge(int e) {
845         return ( e < 0 ? null : (Edge)m_edgeTuples.getTuple(e) );
846     }
847     
848     /**
849      * Returns an edge from the source node to the target node. This
850      * method returns the first such edge found; in the case of multiple
851      * edges there may be more.
852      */
853     public int getEdge(int source, int target) {
854         int outd = getOutDegree(source); 
855         if ( outd > 0 ) {
856             int[] edges = (int[])m_links.get(source, OUTLINKS);
857             for ( int i=0; i<outd; ++i ) {
858                 if ( getTargetNode(edges[i]) == target )
859                     return edges[i];
860             }
861         }
862         return -1;
863     }
864     
865     /**
866      * Get an Edge with given source and target Nodes. There may be times
867      * where there are multiple edges between two nodes; in those cases
868      * this method returns the first such edge found.
869      * @param source the source Node
870      * @param target the target Node
871      * @return an Edge with given source and target nodes, or null if no
872      * such edge is found.
873      */
874     public Edge getEdge(Node source, Node target) {
875         nodeCheck(source, true);
876         nodeCheck(target, true);
877         return getEdge(getEdge(source.getRow(), target.getRow()));
878     }
879     
880     /**
881      * Get the source node id (node table row number) for the given edge
882      * id (edge table row number).
883      * @param edge an edge id (edge table row number)
884      * @return the source node id (node table row number)
885      */
886     public int getSourceNode(int edge) {
887         return getNodeIndex(getEdgeTable().getLong(edge, m_skey));
888     }
889     
890     /**
891      * Get the source Node for the given Edge instance.
892      * @param e an Edge instance
893      * @return the source Node of the edge
894      */
895     public Node getSourceNode(Edge e) {
896         edgeCheck(e, true);
897         return getNode(getSourceNode(e.getRow()));
898     }
899     
900     /**
901      * Get the target node id (node table row number) for the given edge
902      * id (edge table row number).
903      * @param edge an edge id (edge table row number)
904      * @return the target node id (node table row number)
905      */
906     public int getTargetNode(int edge) {
907         return getNodeIndex(getEdgeTable().getLong(edge, m_tkey));
908     }
909     
910     /**
911      * Get the target Node for the given Edge instance.
912      * @param e an Edge instance
913      * @return the target Node of the edge
914      */
915     public Node getTargetNode(Edge e) {
916         edgeCheck(e, true);
917         return getNode(getTargetNode(e.getRow()));
918     }
919     
920     /**
921      * Given an edge id and an incident node id, return the node id for
922      * the other node connected to the edge.
923      * @param edge an edge id (edge table row number)
924      * @param node a node id (node table row number). This node id must
925      * be connected to the edge
926      * @return the adjacent node id
927      */
928     public int getAdjacentNode(int edge, int node) {
929         int s = getSourceNode(edge);
930         int d = getTargetNode(edge);
931         
932         if ( s == node ) {
933             return d;
934         } else if ( d == node ) {
935             return s;
936         } else {
937             throw new IllegalArgumentException  (
938                 "Edge is not incident on the input node.");
939         }
940     }
941     
942     /**
943      * Given an Edge and an incident Node, return the other Node
944      * connected to the edge.
945      * @param e an Edge instance
946      * @param n a Node instance. This node must
947      * be connected to the edge
948      * @return the adjacent Node
949      */
950     public Node getAdjacentNode(Edge e, Node n) {
951         edgeCheck(e, true);
952         nodeCheck(n, true);
953         return getNode(getAdjacentNode(e.getRow(), n.getRow()));
954     }
955 
956     // ------------------------------------------------------------------------
957     // Iterators
958     
959     // -- table row iterators ----
960     
961     /**
962      * Get an iterator over all node ids (node table row numbers).
963      * @return an iterator over all node ids (node table row numbers)
964      */
965     public IntIterator nodeRows() {
966         return getNodeTable().rows();
967     }
968 
969     /**
970      * Get an iterator over all edge ids (edge table row numbers).
971      * @return an iterator over all edge ids (edge table row numbers)
972      */
973     public IntIterator edgeRows() {
974         return getEdgeTable().rows();
975     }
976     
977     /**
978      * Get an iterator over all edge ids for edges incident on the given node.
979      * @param node a node id (node table row number)
980      * @return an iterator over all edge ids for edges incident on the given
981      * node
982      */
983     public IntIterator edgeRows(int node) {
984         return edgeRows(node, UNDIRECTED);
985     }
986     
987     /**
988      * Get an iterator edge ids for edges incident on the given node.
989      * @param node a node id (node table row number)
990      * @param direction the directionality of the edges to include. One of
991      * {@link #INEDGES} (for in-linking edges),
992      * {@link #OUTEDGES} (for out-linking edges), or
993      * {@link #UNDIRECTED} (for all edges).
994      * @return an iterator over all edge ids for edges incident on the given
995      * node
996      */
997     public IntIterator edgeRows(int node, int direction) {
998         if ( direction==OUTEDGES ) {
999             int[] outedges = (int[])m_links.get(node, OUTLINKS);
1000            return new IntArrayIterator(outedges, 0, getOutDegree(node));
1001        } else if ( direction==INEDGES ) {
1002            int[] inedges = (int[])m_links.get(node, INLINKS);
1003            return new IntArrayIterator(inedges, 0, getInDegree(node));
1004        } else if ( direction==UNDIRECTED ) {
1005            return new CompositeIntIterator(
1006                edgeRows(node, OUTEDGES), edgeRows(node, INEDGES));
1007        } else {
1008            throw new IllegalArgumentException  ("Unrecognized edge type: " 
1009                + direction + ". Type should be one of Graph.OUTEDGES, "
1010                + "Graoh.INEDGES, or Graph.ALL");
1011        }
1012    }
1013    
1014    /**
1015     * Get an iterator over all edges that have the given node as a target.
1016     * That is, edges that link into the given target node.
1017     * @param node a node id (node table row number)
1018     * @return an iterator over all edges that have the given node as a target
1019     */
1020    public IntIterator inEdgeRows(int node) {
1021        return edgeRows(node, INEDGES);
1022    }
1023
1024    /**
1025     * Get an iterator over all edges that have the given node as a source.
1026     * That is, edges that link out from the given source node.
1027     * @param node a node id (node table row number)
1028     * @return an iterator over all edges that have the given node as a source
1029     */
1030    public IntIterator outEdgeRows(int node) {
1031        return edgeRows(node, OUTEDGES);
1032    }
1033    
1034    // -- tuple iterators --
1035    
1036    /**
1037     * Get an iterator over all nodes in the graph.
1038     * @return an iterator over Node instances
1039     */
1040    public Iterator   nodes() {
1041        return m_nodeTuples.iterator(nodeRows());
1042    }
1043
1044    /**
1045     * Get an iterator over all neighbor nodes for the given Node in the graph.
1046     * @param n a Node in the graph
1047     * @return an iterator over all Nodes connected to the input node
1048     */
1049    public Iterator   neighbors(Node n) {
1050        return new NeighborIterator(n, edges(n));
1051    }
1052
1053    /**
1054     * Get an iterator over all in-linking neighbor nodes for the given Node.
1055     * @param n a Node in the graph
1056     * @return an iterator over all Nodes that point to the input target node
1057     */
1058    public Iterator   inNeighbors(Node n) {
1059        return new NeighborIterator(n, inEdges(n));
1060    }
1061
1062    /**
1063     * Get an iterator over all out-linking neighbor nodes for the given Node.
1064     * @param n a Node in the graph
1065     * @return an iterator over all Nodes pointed to by the input source node
1066     */
1067    public Iterator   outNeighbors(Node n) {
1068        return new NeighborIterator(n, outEdges(n));
1069    }
1070    
1071    /**
1072     * Get an iterator over all edges in the graph.
1073     * @return an iterator over Edge instances
1074     */
1075    public Iterator   edges() {
1076        return m_edgeTuples.iterator(edgeRows());
1077    }
1078    
1079    /**
1080     * Get an iterator over all Edges connected to the given Node in the graph.
1081     * @param node a Node in the graph
1082     * @return an iterator over all Edges connected to the input node
1083     */
1084    public Iterator   edges(Node node) {
1085        nodeCheck(node, true);
1086        return m_edgeTuples.iterator(edgeRows(node.getRow(), UNDIRECTED)); 
1087    }
1088    
1089    /**
1090     * Get an iterator over all in-linking edges to the given Node.
1091     * @param node a Node in the graph
1092     * @return an iterator over all in-linking edges to the input target node
1093     */
1094    public Iterator   inEdges(Node node) {
1095        nodeCheck(node, true);
1096        return m_edgeTuples.iterator(inEdgeRows(node.getRow()));
1097    }
1098
1099    /**
1100     * Get an iterator over all out-linking edges from the given Node.
1101     * @param node a Node in the graph
1102     * @return an iterator over all out-linking edges from the input source
1103     * node
1104     */
1105    public Iterator   outEdges(Node node) {
1106        nodeCheck(node, true);
1107        return m_edgeTuples.iterator(outEdgeRows(node.getRow()));
1108    }
1109    
1110    // ------------------------------------------------------------------------
1111    // TupleSet Interface
1112
1113    /**
1114     * Clear this graph, removing all nodes and edges.
1115     * @see prefuse.data.tuple.TupleSet#clear()
1116     */
1117    public void clear() {
1118        m_nodeTuples.invalidateAll();
1119        m_edgeTuples.invalidateAll();
1120        super.clear();
1121        m_links.clear();
1122    }
1123    
1124    /**
1125     * If the given tuple is a Node or Edge in this graph, remove it.
1126     * @see prefuse.data.tuple.TupleSet#removeTuple(prefuse.data.Tuple)
1127     */
1128    public boolean removeTuple(Tuple t) {
1129        // TODO: check underlying table tuples as well?
1130        if ( t instanceof Node ) {
1131            return removeNode((Node)t);
1132        } else if ( t instanceof Edge ) {
1133            return removeEdge((Edge)t);
1134        } else {
1135            throw new IllegalArgumentException  (
1136                    "Input tuple must be part of this graph");
1137        }
1138    }
1139
1140    /**
1141     * Get a filtered iterator over the edges and nodes of this graph.
1142     * @see prefuse.data.tuple.TupleSet#tuples(prefuse.data.expression.Predicate)
1143     */
1144    public Iterator   tuples(Predicate filter) {
1145        if ( filter == null ) {
1146            return tuples();
1147        } else {
1148            return new CompositeIterator(
1149                    m_edgeTuples.iterator(getEdgeTable().rows(filter)),
1150                    m_nodeTuples.iterator(getNodeTable().rows(filter)));
1151        }
1152    }
1153    
1154    /**
1155     * Get an iterator over all the edges and nodes of this graph. The iterator
1156     * will return all edges first, then all nodes.
1157     * @see prefuse.data.tuple.TupleSet#tuples()
1158     */
1159    public Iterator   tuples() {
1160        return new CompositeIterator(edges(), nodes());
1161    }    
1162    
1163    // ------------------------------------------------------------------------
1164    // Spanning Tree Methods
1165    
1166    /**
1167     * Return the current spanning tree over this graph. If no spanning tree
1168     * has been constructed, a SpanningTree rooted at the first valid node
1169     * found in the node table will be generated.
1170     * 
1171     * Spanning trees are generated using an unweighted breadth first search
1172     * over the graph structure.
1173     * 
1174     * @return a spanning tree over this graph
1175     * @see #getSpanningTree(Node)
1176     * @see #clearSpanningTree()
1177     */
1178    public Tree getSpanningTree() {
1179        if ( m_spanning == null )
1180            return getSpanningTree((Node)nodes().next());
1181        else
1182            return m_spanning;
1183    }
1184
1185    /**
1186     * Returns a spanning tree rooted at the specified node. If the current
1187     * spanning tree is alrady rooted at the given node, it is simply
1188     * returned. Otherwise, the tree is reconstructed at the new root and
1189     * made the current spanning tree for this Graph instance.
1190     * 
1191     * Spanning trees are generated using an unweighted breadth first search
1192     * over the graph structure.
1193     * 
1194     * @param root the node at which to root the spanning tree.
1195     * @return a spanning tree over this graph, rooted at the given root
1196     * @see #getSpanningTree()
1197     * @see #clearSpanningTree()
1198     */
1199    public Tree getSpanningTree(Node root) {
1200        nodeCheck(root, true);
1201        if ( m_spanning == null ) {
1202            m_spanning = new SpanningTree(this, root);
1203        } else if ( m_spanning.getRoot() != root ) {
1204            m_spanning.buildSpanningTree(root);
1205        }
1206        return m_spanning;
1207    }
1208    
1209    /**
1210     * Clear the internally stored spanning tree. Any new calls to a
1211     * getSpanningTree() method will generate a new spanning tree 
1212     * instance as needed.
1213     * 
1214     * This method is primarily useful for subclasses.
1215     * For example, calling this method on a Tree instance will revert the
1216     * state to the original rooted tree such that a sbusequent call to
1217     * getSpanningTree() will return the backing Tree itself.
1218     * @see #getSpanningTree()
1219     * @see #getSpanningTree(Node)
1220     * @see Tree#getSpanningTree(Node)
1221     */
1222    public void clearSpanningTree() {
1223        m_spanning = null;
1224    }
1225    
1226    // ------------------------------------------------------------------------
1227    // Graph Listeners
1228    
1229    /**
1230     * Add a listener to be notified of changes to the graph.
1231     * @param listnr the listener to add
1232     */
1233    public void addGraphModelListener(GraphListener listnr) {
1234        if ( !m_listeners.contains(listnr) )
1235            m_listeners.add(listnr);
1236    }
1237
1238    /**
1239     * Remove a listener from this graph.
1240     * @param listnr the listener to remove
1241     */
1242    public void removeGraphModelListener(GraphListener listnr) {
1243        m_listeners.remove(listnr);
1244    }
1245    
1246    /**
1247     * Fire a graph change event
1248     * @param t the backing table where the change occurred (either a
1249     * node table or an edge table)
1250     * @param first the first modified table row
1251     * @param last the last (inclusive) modified table row
1252     * @param col the number of the column modified, or
1253     * {@link prefuse.data.event.EventConstants#ALL_COLUMNS} for operations
1254     * affecting all columns
1255     * @param type the type of modification, one of
1256     * {@link prefuse.data.event.EventConstants#INSERT},
1257     * {@link prefuse.data.event.EventConstants#DELETE}, or
1258     * {@link prefuse.data.event.EventConstants#UPDATE}.
1259     */
1260    protected void fireGraphEvent(Table t, 
1261            int first, int last, int col, int type)
1262    {
1263        String   table = (t==getNodeTable() ? NODES : EDGES);
1264        
1265        if ( type != EventConstants.UPDATE ) {
1266            // fire event to all tuple set listeners
1267            fireTupleEvent(t, first, last, type);
1268        }
1269        
1270        if ( !m_listeners.isEmpty() ) {            
1271            // fire event to all listeners
1272            Object  [] lstnrs = m_listeners.getArray();
1273            for ( int i=0; i<lstnrs.length; ++i ) {
1274                ((GraphListener)lstnrs[i]).graphChanged(
1275                        this, table, first, last, col, type);
1276            }
1277        }
1278    }
1279
1280    // ------------------------------------------------------------------------
1281    // Table and Column Listener
1282    
1283    /**
1284     * Listener class for tracking updates from node and edge tables,
1285     * and their columns that determine the graph linkage structure.
1286     */
1287    protected class Listener implements TableListener, ColumnListener {
1288
1289        private Table m_edges;
1290        private Column m_scol, m_tcol;
1291        private int m_sidx, m_tidx;
1292        
1293        public void setEdgeTable(Table edges) {
1294            // remove any previous listeners
1295            if ( m_scol != null ) m_scol.removeColumnListener(this);
1296            if ( m_tcol != null ) m_tcol.removeColumnListener(this);
1297            m_scol = m_tcol = null;
1298            m_sidx = m_tidx = -1;
1299            
1300            m_edges = edges;
1301            
1302            // register listeners
1303            if ( m_edges != null ) {
1304                m_sidx = edges.getColumnNumber(m_skey);
1305                m_tidx = edges.getColumnNumber(m_tkey);
1306                m_scol = edges.getColumn(m_sidx);
1307                m_tcol = edges.getColumn(m_tidx);
1308                m_scol.addColumnListener(this);
1309                m_tcol.addColumnListener(this);
1310            }
1311        }
1312        
1313        public void tableChanged(Table t, int start, int end, int col, int type) {
1314            if ( !containsSet(t) )
1315                throw new IllegalStateException  (
1316                     "Graph shouldn't be listening to an unrelated table");
1317            
1318            if ( type != EventConstants.UPDATE ) {
1319                if ( t == getNodeTable() ) {
1320                    // update the linkage structure table
1321                    if ( col == EventConstants.ALL_COLUMNS ) {
1322                        boolean added = type==EventConstants.INSERT;
1323                        for ( int r=start; r<=end; ++r )
1324                            updateNodeData(r, added);
1325                    }
1326                } else {
1327                    // update the linkage structure table
1328                    if ( col == EventConstants.ALL_COLUMNS ) {
1329                        boolean added = type==EventConstants.INSERT;
1330                        for ( int r=start; r<=end; ++r )
1331                            updateDegrees(start, added?1:-1);
1332                    }
1333                }
1334                // clear the spanning tree reference
1335                m_spanning = null;
1336            }
1337            fireGraphEvent(t, start, end, col, type);
1338        }
1339
1340        public void columnChanged(Column src, int idx, int prev) {
1341            columnChanged(src, idx, (long)prev);
1342        }
1343
1344        public void columnChanged(Column src, int idx, long prev) {
1345            if ( SRC==m_scol || SRC==m_tcol ) {
1346                boolean isSrc = SRC==m_scol;
1347                int e = m_edges.getTableRow(idx, isSrc?m_sidx:m_tidx);
1348                if ( e == -1 )
1349                    return; // edge not in this graph
1350                int s = getSourceNode(e);
1351                int t = getTargetNode(e);
1352                int p = getNodeIndex(prev);
1353                if ( p > -1 && ((isSrc && t > -1) || (!isSrc && s > -1)) )
1354                    updateDegrees(e, isSrc?p:s, isSrc?t:p, -1);
1355                if ( s > -1 && t > -1 )
1356                    updateDegrees(e, s, t, 1);
1357            } else {
1358                throw new IllegalStateException  ();
1359            }
1360        }
1361        
1362        public void columnChanged(Column src, int type, int start, int end) {
1363            // should never be called
1364            throw new IllegalStateException  ();
1365        }
1366        public void columnChanged(Column src, int idx, float prev) {
1367            // should never be called
1368            throw new IllegalStateException  ();
1369        }
1370        public void columnChanged(Column src, int idx, double prev) {
1371            // should never be called
1372            throw new IllegalStateException  ();
1373        }
1374        public void columnChanged(Column src, int idx, boolean prev) {
1375            // should never be called
1376            throw new IllegalStateException  ();
1377        }
1378        public void columnChanged(Column src, int idx, Object   prev) {
1379            // should never be called
1380            throw new IllegalStateException  ();
1381        }   
1382    } // end of inner class Listener
1383    
1384    
1385    // ------------------------------------------------------------------------
1386    // Graph Linkage Schema
1387    
1388    /** In-degree data field for the links table */
1389    protected static final String   INDEGREE  = "_indegree";
1390    /** Out-degree data field for the links table */
1391    protected static final String   OUTDEGREE = "_outdegree";
1392    /** In-links adjacency list data field for the links table */
1393    protected static final String   INLINKS   = "_inlinks";
1394    /** Out-links adjacency list data field for the links table */
1395    protected static final String   OUTLINKS  = "_outlinks";
1396    /** Schema used for the internal graph linkage table */
1397    protected static final Schema LINKS_SCHEMA = new Schema();
1398    static {
1399        Integer   defaultValue = new Integer  (0);
1400        LINKS_SCHEMA.addColumn(INDEGREE,  int.class, defaultValue);
1401        LINKS_SCHEMA.addColumn(OUTDEGREE, int.class, defaultValue);
1402        LINKS_SCHEMA.addColumn(INLINKS,   int[].class);
1403        LINKS_SCHEMA.addColumn(OUTLINKS,  int[].class);
1404        LINKS_SCHEMA.lockSchema();
1405    }
1406    
1407} // end of class Graph
1408
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags