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 )