0001: package prefuse.data;
0002:
0003: import java.util.Iterator;
0004:
0005: import prefuse.data.column.Column;
0006: import prefuse.data.event.ColumnListener;
0007: import prefuse.data.event.EventConstants;
0008: import prefuse.data.event.GraphListener;
0009: import prefuse.data.event.TableListener;
0010: import prefuse.data.expression.Predicate;
0011: import prefuse.data.tuple.CompositeTupleSet;
0012: import prefuse.data.tuple.TableEdge;
0013: import prefuse.data.tuple.TableNode;
0014: import prefuse.data.tuple.TupleManager;
0015: import prefuse.data.tuple.TupleSet;
0016: import prefuse.data.util.Index;
0017: import prefuse.data.util.NeighborIterator;
0018: import prefuse.util.PrefuseConfig;
0019: import prefuse.util.TypeLib;
0020: import prefuse.util.collections.CompositeIntIterator;
0021: import prefuse.util.collections.CompositeIterator;
0022: import prefuse.util.collections.CopyOnWriteArrayList;
0023: import prefuse.util.collections.IntArrayIterator;
0024: import prefuse.util.collections.IntIterator;
0025:
0026: /**
0027: * <p>A Graph models a network of nodes connected by a collection of edges.
0028: * Both nodes and edges can have any number of associated data fields.
0029: * Additionally, edges are either directed or undirected, indicating a
0030: * possible directionality of the connection. Each edge has both a source
0031: * node and a target node, for a directed edge this indicates the
0032: * directionality, for an undirected edge this is just an artifact
0033: * of the order in which the nodes were specified when added to the graph.
0034: * </p>
0035: *
0036: * <p>Both nodes and edges are represented by backing data {@link Table}
0037: * instances storing the data attributes. For edges, this table must
0038: * also contain a source node field and a target node field. The default
0039: * column name for these fields are {@link #DEFAULT_SOURCE_KEY} and
0040: * {@link #DEFAULT_TARGET_KEY}, but these can be configured by the graph
0041: * constructor. These columns should be integer valued, and contain
0042: * either the row number for a corresponding node in the node table,
0043: * or another unique identifier for a node. In this second case, the
0044: * unique identifier must be included as a data field in the node
0045: * table. This name of this column can be configured using the appropriate
0046: * graph constructor. The default column name for this field is
0047: * {@link #DEFAULT_NODE_KEY}, which by default evaluates to null,
0048: * indicating that no special node key should be used, just the direct
0049: * node table row numbers. Though the source, target, and node key
0050: * values completely specify the graph linkage structure, to make
0051: * graph operations more efficient an additional table is maintained
0052: * internally by the Graph class, storing node indegree and outdegree
0053: * counts and adjacency lists for the inlinks and outlinks for all nodes.</p>
0054: *
0055: * <p>Graph nodes and edges can be accessed by application code by either
0056: * using the row numbers of the node and edge tables, which provide unique ids
0057: * for each, or using the {@link prefuse.data.Node} and
0058: * {@link prefuse.data.Edge} classes --
0059: * {@link prefuse.data.Tuple} instances that provide
0060: * object-oriented access to both node or edge data values and the
0061: * backing graph structure. Node and Edge tuples are maintained by
0062: * special TupleManager instances contained within this Graph. By default, they
0063: * are not accessible from the backing node or edge tables directly. The reason
0064: * for this is that these tables might be used in multiple graphs
0065: * simultaneously. For example, a node data table could be used in a number of
0066: * different graphs, exploring different possible linkages between those node.
0067: * In short, use this Graph instance to request iterators over Node or
0068: * Edge tuples, not the backing data tables.</p>
0069: *
0070: * <p>All Graph instances also support an internally generated
0071: * spanning tree, provided by the {@link #getSpanningTree()} or
0072: * {@link #getSpanningTree(Node)} methods. This is particularly
0073: * useful in visualization contexts that use an underlying tree structure
0074: * to compute a graph layout.</p>
0075: *
0076: * @author <a href="http://jheer.org">jeffrey heer</a>
0077: */
0078: public class Graph extends CompositeTupleSet {
0079:
0080: /** Indicates incoming edges (inlinks) */
0081: public static final int INEDGES = 0;
0082: /** Indicates outgoing edges (outlinks) */
0083: public static final int OUTEDGES = 1;
0084: /** Indicates all edges, regardless of direction */
0085: public static final int UNDIRECTED = 2;
0086:
0087: /** Default data field used to uniquely identify a node */
0088: public static final String DEFAULT_NODE_KEY = PrefuseConfig
0089: .get("data.graph.nodeKey");
0090: /** Default data field used to denote the source node in an edge table */
0091: public static final String DEFAULT_SOURCE_KEY = PrefuseConfig
0092: .get("data.graph.sourceKey");
0093: /** Default data field used to denote the target node in an edge table */
0094: public static final String DEFAULT_TARGET_KEY = PrefuseConfig
0095: .get("data.graph.targetKey");
0096: /** Data group name to identify the nodes of this graph */
0097: public static final String NODES = PrefuseConfig
0098: .get("data.graph.nodeGroup");
0099: /** Data group name to identify the edges of this graph */
0100: public static final String EDGES = PrefuseConfig
0101: .get("data.graph.edgeGroup");
0102:
0103: // -- auxiliary data structures -----
0104:
0105: /** Table containing the adjacency lists for the graph */
0106: protected Table m_links;
0107: /** TupleManager for managing Node tuple instances */
0108: protected TupleManager m_nodeTuples;
0109: /** TupleManager for managing Edge tuple instances */
0110: protected TupleManager m_edgeTuples;
0111:
0112: /** Indicates if this graph is directed or undirected */
0113: protected boolean m_directed = false;
0114: /** The spanning tree over this graph */
0115: protected SpanningTree m_spanning = null;
0116:
0117: /** The node key field (for the Node table) */
0118: protected String m_nkey;
0119: /** The source node key field (for the Edge table) */
0120: protected String m_skey;
0121: /** The target node key field (for the Edge table) */
0122: protected String m_tkey;
0123: /** Reference to an index over the node key field */
0124: protected Index m_nidx;
0125: /** Indicates if the key values are of type long */
0126: protected boolean m_longKey = false;
0127: /** Update listener */
0128: private Listener m_listener;
0129: /** Listener list */
0130: private CopyOnWriteArrayList m_listeners = new CopyOnWriteArrayList();
0131:
0132: // ------------------------------------------------------------------------
0133: // Constructors
0134:
0135: /**
0136: * Creates a new, empty undirected Graph.
0137: */
0138: public Graph() {
0139: this (false);
0140: }
0141:
0142: /**
0143: * Creates a new, empty Graph.
0144: * @param directed true for directed edges, false for undirected
0145: */
0146: public Graph(boolean directed) {
0147: this (new Table(), directed);
0148: }
0149:
0150: /**
0151: * Create a new Graph using the provided table of node data and
0152: * an empty set of edges.
0153: * @param nodes the backing table to use for node data.
0154: * Node instances of this graph will get their data from this table.
0155: * @param directed true for directed edges, false for undirected
0156: */
0157: public Graph(Table nodes, boolean directed) {
0158: this (nodes, directed, DEFAULT_NODE_KEY, DEFAULT_SOURCE_KEY,
0159: DEFAULT_TARGET_KEY);
0160: }
0161:
0162: /**
0163: * Create a new Graph using the provided table of node data and
0164: * an empty set of edges.
0165: * @param nodes the backing table to use for node data.
0166: * Node instances of this graph will get their data from this table.
0167: * @param directed true for directed edges, false for undirected
0168: * @param nodeKey data field used to uniquely identify a node. If this
0169: * field is null, the node table row numbers will be used
0170: * @param sourceKey data field used to denote the source node in an edge
0171: * table
0172: * @param targetKey data field used to denote the target node in an edge
0173: * table
0174: */
0175: public Graph(Table nodes, boolean directed, String nodeKey,
0176: String sourceKey, String targetKey) {
0177: Table edges = new Table();
0178: edges.addColumn(sourceKey, int.class, new Integer(-1));
0179: edges.addColumn(targetKey, int.class, new Integer(-1));
0180: init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
0181: }
0182:
0183: /**
0184: * Create a new Graph, using node table row numbers to uniquely
0185: * identify nodes in the edge table's source and target fields.
0186: * @param nodes the backing table to use for node data.
0187: * Node instances of this graph will get their data from this table.
0188: * @param edges the backing table to use for edge data.
0189: * Edge instances of this graph will get their data from this table.
0190: * @param directed true for directed edges, false for undirected
0191: */
0192: public Graph(Table nodes, Table edges, boolean directed) {
0193: this (nodes, edges, directed, DEFAULT_NODE_KEY,
0194: DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
0195: }
0196:
0197: /**
0198: * Create a new Graph, using node table row numbers to uniquely
0199: * identify nodes in the edge table's source and target fields.
0200: * @param nodes the backing table to use for node data.
0201: * Node instances of this graph will get their data from this table.
0202: * @param edges the backing table to use for edge data.
0203: * Edge instances of this graph will get their data from this table.
0204: * @param directed true for directed edges, false for undirected
0205: * @param sourceKey data field used to denote the source node in an edge
0206: * table
0207: * @param targetKey data field used to denote the target node in an edge
0208: * table
0209: */
0210: public Graph(Table nodes, Table edges, boolean directed,
0211: String sourceKey, String targetKey) {
0212: init(nodes, edges, directed, DEFAULT_NODE_KEY, sourceKey,
0213: targetKey);
0214: }
0215:
0216: /**
0217: * Create a new Graph.
0218: * @param nodes the backing table to use for node data.
0219: * Node instances of this graph will get their data from this table.
0220: * @param edges the backing table to use for edge data.
0221: * Edge instances of this graph will get their data from this table.
0222: * @param directed true for directed edges, false for undirected
0223: * @param nodeKey data field used to uniquely identify a node. If this
0224: * field is null, the node table row numbers will be used
0225: * @param sourceKey data field used to denote the source node in an edge
0226: * table
0227: * @param targetKey data field used to denote the target node in an edge
0228: * table
0229: */
0230: public Graph(Table nodes, Table edges, boolean directed,
0231: String nodeKey, String sourceKey, String targetKey) {
0232: init(nodes, edges, directed, nodeKey, sourceKey, targetKey);
0233: }
0234:
0235: // ------------------------------------------------------------------------
0236: // Initialization
0237:
0238: /**
0239: * Initialize this Graph instance.
0240: * @param nodes the node table
0241: * @param edges the edge table
0242: * @param directed the edge directionality
0243: * @param nodeKey data field used to uniquely identify a node
0244: * @param sourceKey data field used to denote the source node in an edge
0245: * table
0246: * @param targetKey data field used to denote the target node in an edge
0247: * table
0248: */
0249: protected void init(Table nodes, Table edges, boolean directed,
0250: String nodeKey, String sourceKey, String targetKey) {
0251: // sanity check
0252: if ((nodeKey != null && !TypeLib.isIntegerType(nodes
0253: .getColumnType(nodeKey)))
0254: || !TypeLib.isIntegerType(edges
0255: .getColumnType(sourceKey))
0256: || !TypeLib.isIntegerType(edges
0257: .getColumnType(targetKey))) {
0258: throw new IllegalArgumentException(
0259: "Incompatible column types for graph keys");
0260: }
0261:
0262: removeAllSets();
0263: super .addSet(EDGES, edges);
0264: super .addSet(NODES, nodes);
0265:
0266: m_directed = directed;
0267:
0268: // INVARIANT: these three should all reference the same type
0269: // currently limited to int
0270: m_nkey = nodeKey;
0271: m_skey = sourceKey;
0272: m_tkey = targetKey;
0273:
0274: // set up indices
0275: if (nodeKey != null) {
0276: if (nodes.getColumnType(nodeKey) == long.class)
0277: m_longKey = true;
0278: nodes.index(nodeKey);
0279: m_nidx = nodes.getIndex(nodeKey);
0280: }
0281:
0282: // set up tuple manager
0283: if (m_nodeTuples == null)
0284: m_nodeTuples = new TupleManager(nodes, this ,
0285: TableNode.class);
0286: m_edgeTuples = new TupleManager(edges, this , TableEdge.class);
0287:
0288: // set up node attribute optimization
0289: initLinkTable();
0290:
0291: // set up listening
0292: if (m_listener == null)
0293: m_listener = new Listener();
0294: nodes.addTableListener(m_listener);
0295: edges.addTableListener(m_listener);
0296: m_listener.setEdgeTable(edges);
0297: }
0298:
0299: /**
0300: * Set the tuple managers used to manage the Node and Edge tuples of this
0301: * Graph.
0302: * @param ntm the TupleManager to use for nodes
0303: * @param etm the TupleManager to use for edges
0304: */
0305: public void setTupleManagers(TupleManager ntm, TupleManager etm) {
0306: if (!Node.class.isAssignableFrom(ntm.getTupleType()))
0307: throw new IllegalArgumentException(
0308: "The provided node "
0309: + "TupleManager must generate tuples that implement "
0310: + "the Node interface.");
0311: if (!Edge.class.isAssignableFrom(etm.getTupleType()))
0312: throw new IllegalArgumentException(
0313: "The provided edge "
0314: + "TupleManager must generate tuples that implement "
0315: + "the Edge interface.");
0316: m_nodeTuples = ntm;
0317: m_edgeTuples = etm;
0318: }
0319:
0320: /**
0321: * Dispose of this graph. Unregisters this graph as a listener to its
0322: * included tables.
0323: */
0324: public void dispose() {
0325: getNodeTable().removeTableListener(m_listener);
0326: getEdgeTable().removeTableListener(m_listener);
0327: }
0328:
0329: /**
0330: * Updates this graph to use a different edge structure for the same nodes.
0331: * All other settings will remain the same (e.g., directionality, keys)
0332: * @param edges the new edge table.
0333: */
0334: public void setEdgeTable(Table edges) {
0335: Table oldEdges = getEdgeTable();
0336: oldEdges.removeTableListener(m_listener);
0337: m_edgeTuples.invalidateAll();
0338: m_links.clear();
0339:
0340: init(getNodeTable(), edges, m_directed, m_nkey, m_skey, m_tkey);
0341: }
0342:
0343: // ------------------------------------------------------------------------
0344: // Data Access Optimization
0345:
0346: /**
0347: * Initialize the link table, which holds adjacency lists for this graph.
0348: */
0349: protected void initLinkTable() {
0350: // set up cache of node data
0351: m_links = createLinkTable();
0352:
0353: IntIterator edges = getEdgeTable().rows();
0354: while (edges.hasNext()) {
0355: updateDegrees(edges.nextInt(), 1);
0356: }
0357: }
0358:
0359: /**
0360: * Instantiate and return the link table.
0361: * @return the created link table
0362: */
0363: protected Table createLinkTable() {
0364: return LINKS_SCHEMA
0365: .instantiate(getNodeTable().getMaximumRow() + 1);
0366: }
0367:
0368: /**
0369: * Internal method for updating the linkage of this graph.
0370: * @param e the edge id for the updated link
0371: * @param incr the increment value, 1 for an added link,
0372: * -1 for a removed link
0373: */
0374: protected void updateDegrees(int e, int incr) {
0375: if (!getEdgeTable().isValidRow(e))
0376: return;
0377: int s = getSourceNode(e);
0378: int t = getTargetNode(e);
0379: if (s < 0 || t < 0)
0380: return;
0381: updateDegrees(e, s, t, incr);
0382: if (incr < 0) {
0383: m_edgeTuples.invalidate(e);
0384: }
0385: }
0386:
0387: /**
0388: * Internal method for updating the linkage of this graph.
0389: * @param e the edge id for the updated link
0390: * @param s the source node id for the updated link
0391: * @param t the target node id for the updated link
0392: * @param incr the increment value, 1 for an added link,
0393: * -1 for a removed link
0394: */
0395: protected void updateDegrees(int e, int s, int t, int incr) {
0396: int od = m_links.getInt(s, OUTDEGREE);
0397: int id = m_links.getInt(t, INDEGREE);
0398: // update adjacency lists
0399: if (incr > 0) {
0400: // add links
0401: addLink(OUTLINKS, od, s, e);
0402: addLink(INLINKS, id, t, e);
0403: } else if (incr < 0) {
0404: // remove links
0405: remLink(OUTLINKS, od, s, e);
0406: remLink(INLINKS, id, t, e);
0407: }
0408: // update degree counts
0409: m_links.setInt(s, OUTDEGREE, od + incr);
0410: m_links.setInt(t, INDEGREE, id + incr);
0411: // link structure changed, invalidate spanning tree
0412: m_spanning = null;
0413: }
0414:
0415: /**
0416: * Internal method for adding a link to an adjacency list
0417: * @param field which adjacency list (inlinks or outlinks) to use
0418: * @param len the length of the adjacency list
0419: * @param n the node id of the adjacency list to use
0420: * @param e the edge to add to the list
0421: */
0422: protected void addLink(String field, int len, int n, int e) {
0423: int[] array = (int[]) m_links.get(n, field);
0424: if (array == null) {
0425: array = new int[] { e };
0426: m_links.set(n, field, array);
0427: return;
0428: } else if (len == array.length) {
0429: int[] narray = new int[Math.max(3 * array.length / 2,
0430: len + 1)];
0431: System.arraycopy(array, 0, narray, 0, array.length);
0432: array = narray;
0433: m_links.set(n, field, array);
0434: }
0435: array[len] = e;
0436: }
0437:
0438: /**
0439: * Internal method for removing a link from an adjacency list
0440: * @param field which adjacency list (inlinks or outlinks) to use
0441: * @param len the length of the adjacency list
0442: * @param n the node id of the adjacency list to use
0443: * @param e the edge to remove from the list
0444: * @return true if the link was removed successfully, false otherwise
0445: */
0446: protected boolean remLink(String field, int len, int n, int e) {
0447: int[] array = (int[]) m_links.get(n, field);
0448: for (int i = 0; i < len; ++i) {
0449: if (array[i] == e) {
0450: System.arraycopy(array, i + 1, array, i, len - i - 1);
0451: return true;
0452: }
0453: }
0454: return false;
0455: }
0456:
0457: /**
0458: * Update the link table to accomodate an inserted or deleted node
0459: * @param r the node id, also the row number into the link table
0460: * @param added indicates if a node was added or removed
0461: */
0462: protected void updateNodeData(int r, boolean added) {
0463: if (added) {
0464: m_links.addRow();
0465: } else {
0466: m_nodeTuples.invalidate(r);
0467: m_links.removeRow(r);
0468: }
0469: }
0470:
0471: // ------------------------------------------------------------------------
0472: // Key Transforms
0473:
0474: /**
0475: * Get the data field used to uniquely identify a node
0476: * @return the data field used to uniquely identify a node
0477: */
0478: public String getNodeKeyField() {
0479: return m_nkey;
0480: }
0481:
0482: /**
0483: * Get the data field used to denote the source node in an edge table.
0484: * @return the data field used to denote the source node in an edge table.
0485: */
0486: public String getEdgeSourceField() {
0487: return m_skey;
0488: }
0489:
0490: /**
0491: * Get the data field used to denote the target node in an edge table.
0492: * @return the data field used to denote the target node in an edge table.
0493: */
0494: public String getEdgeTargetField() {
0495: return m_tkey;
0496: }
0497:
0498: /**
0499: * Given a node id (a row number in the node table), get the value of
0500: * the node key field.
0501: * @param node the node id
0502: * @return the value of the node key field for the given node
0503: */
0504: public long getKey(int node) {
0505: return m_nkey == null ? node : getNodeTable().getLong(node,
0506: m_nkey);
0507: }
0508:
0509: /**
0510: * Given a value of the node key field, get the node id (the row number
0511: * in the node table).
0512: * @param key a node key field value
0513: * @return the node id (the row number in the node table)
0514: */
0515: public int getNodeIndex(long key) {
0516: if (m_nidx == null) {
0517: return (int) key;
0518: } else {
0519: int idx = m_longKey ? m_nidx.get(key) : m_nidx
0520: .get((int) key);
0521: return idx < 0 ? -1 : idx;
0522: }
0523: }
0524:
0525: // ------------------------------------------------------------------------
0526: // Graph Mutators
0527:
0528: /**
0529: * Add row to the node table, thereby adding a node to the graph.
0530: * @return the node id (node table row number) of the added node
0531: */
0532: public int addNodeRow() {
0533: return getNodeTable().addRow();
0534: }
0535:
0536: /**
0537: * Add a new node to the graph.
0538: * @return the new Node instance
0539: */
0540: public Node addNode() {
0541: int nrow = addNodeRow();
0542: return (Node) m_nodeTuples.getTuple(nrow);
0543: }
0544:
0545: /**
0546: * Add an edge to the graph. Both multiple edges between two nodes
0547: * and edges from a node to itself are allowed.
0548: * @param s the source node id
0549: * @param t the target node id
0550: * @return the edge id (edge table row number) of the added edge
0551: */
0552: public int addEdge(int s, int t) {
0553: // get keys for the nodes
0554: long key1 = getKey(s);
0555: long key2 = getKey(t);
0556:
0557: // add edge row, set source/target fields
0558: Table edges = getEdgeTable();
0559: int r = edges.addRow();
0560: if (m_longKey) {
0561: edges.setLong(r, m_skey, key1);
0562: edges.setLong(r, m_tkey, key2);
0563: } else {
0564: edges.setInt(r, m_skey, (int) key1);
0565: edges.setInt(r, m_tkey, (int) key2);
0566: }
0567: return r;
0568: }
0569:
0570: /**
0571: * Add an edge to the graph.
0572: * @param s the source Node
0573: * @param t the target Node
0574: * @return the new Edge instance
0575: */
0576: public Edge addEdge(Node s, Node t) {
0577: nodeCheck(s, true);
0578: nodeCheck(t, true);
0579: int e = addEdge(s.getRow(), t.getRow());
0580: return getEdge(e);
0581: }
0582:
0583: /**
0584: * Remove a node from the graph, also removing all incident edges.
0585: * @param node the node id (node table row number) of the node to remove
0586: * @return true if the node was successfully removed, false if the
0587: * node id was not found or was not valid
0588: */
0589: public boolean removeNode(int node) {
0590: Table nodeTable = getNodeTable();
0591: if (nodeTable.isValidRow(node)) {
0592: int id = getInDegree(node);
0593: if (id > 0) {
0594: int[] links = (int[]) m_links.get(node, INLINKS);
0595: for (int i = id; --i >= 0;)
0596: removeEdge(links[i]);
0597: }
0598: int od = getOutDegree(node);
0599: if (od > 0) {
0600: int[] links = (int[]) m_links.get(node, OUTLINKS);
0601: for (int i = od; --i >= 0;)
0602: removeEdge(links[i]);
0603: }
0604: }
0605: return nodeTable.removeRow(node);
0606: }
0607:
0608: /**
0609: * Remove a node from the graph, also removing all incident edges.
0610: * @param n the Node to remove from the graph
0611: * @return true if the node was successfully removed, false if the
0612: * node was not found in this graph
0613: */
0614: public boolean removeNode(Node n) {
0615: nodeCheck(n, true);
0616: return removeNode(n.getRow());
0617: }
0618:
0619: /**
0620: * Remove an edge from the graph.
0621: * @param edge the edge id (edge table row number) of the edge to remove
0622: * @return true if the edge was successfully removed, false if the
0623: * edge was not found or was not valid
0624: */
0625: public boolean removeEdge(int edge) {
0626: return getEdgeTable().removeRow(edge);
0627: }
0628:
0629: /**
0630: * Remove an edge from the graph.
0631: * @param e the Edge to remove from the graph
0632: * @return true if the edge was successfully removed, false if the
0633: * edge was not found in this graph
0634: */
0635: public boolean removeEdge(Edge e) {
0636: edgeCheck(e, true);
0637: return removeEdge(e.getRow());
0638: }
0639:
0640: /**
0641: * Internal method for clearing the edge table, removing all edges.
0642: */
0643: protected void clearEdges() {
0644: getEdgeTable().clear();
0645: }
0646:
0647: // ------------------------------------------------------------------------
0648: // Node Accessor Methods
0649:
0650: /**
0651: * Internal method for checking the validity of a node.
0652: * @param n the Node to check for validity
0653: * @param throwException true if this method should throw an Exception
0654: * when an invalid node is encountered
0655: * @return true is the node is valid, false if invalid
0656: */
0657: protected boolean nodeCheck(Node n, boolean throwException) {
0658: if (!n.isValid()) {
0659: if (throwException) {
0660: throw new IllegalArgumentException(
0661: "Node must be valid.");
0662: }
0663: return false;
0664: }
0665: Graph ng = n.getGraph();
0666: if (ng != this && ng.m_spanning != this ) {
0667: if (throwException) {
0668: throw new IllegalArgumentException(
0669: "Node must be part of this Graph.");
0670: }
0671: return false;
0672: }
0673: return true;
0674: }
0675:
0676: /**
0677: * Get the collection of nodes as a TupleSet. Returns the same result as
0678: * {@link CompositeTupleSet#getSet(String)} using
0679: * {@link #NODES} as the parameter.
0680: * @return the nodes of this graph as a TupleSet instance
0681: */
0682: public TupleSet getNodes() {
0683: return getSet(NODES);
0684: }
0685:
0686: /**
0687: * Get the backing node table.
0688: * @return the table of node values
0689: */
0690: public Table getNodeTable() {
0691: return (Table) getSet(NODES);
0692: }
0693:
0694: /**
0695: * Get the number of nodes in this graph.
0696: * @return the number of nodes
0697: */
0698: public int getNodeCount() {
0699: return getNodeTable().getRowCount();
0700: }
0701:
0702: /**
0703: * Get the Node tuple instance corresponding to a node id.
0704: * @param n a node id (node table row number)
0705: * @return the Node instance corresponding to the node id
0706: */
0707: public Node getNode(int n) {
0708: return (Node) m_nodeTuples.getTuple(n);
0709: }
0710:
0711: /**
0712: * Get the Node tuple corresponding to the input node key field value.
0713: * The node key field is used to find the node id (node table row number),
0714: * which is then used to retrieve the Node tuple.
0715: * @param key a node key field value
0716: * @return the requested Node instance
0717: */
0718: public Node getNodeFromKey(long key) {
0719: int n = getNodeIndex(key);
0720: return (n < 0 ? null : getNode(n));
0721: }
0722:
0723: /**
0724: * Get the in-degree of a node, the number of edges for which the node
0725: * is the target.
0726: * @param node the node id (node table row number)
0727: * @return the in-degree of the node
0728: */
0729: public int getInDegree(int node) {
0730: return m_links.getInt(node, INDEGREE);
0731: }
0732:
0733: /**
0734: * Get the in-degree of a node, the number of edges for which the node
0735: * is the target.
0736: * @param n the Node instance
0737: * @return the in-degree of the node
0738: */
0739: public int getInDegree(Node n) {
0740: nodeCheck(n, true);
0741: return getInDegree(n.getRow());
0742: }
0743:
0744: /**
0745: * Get the out-degree of a node, the number of edges for which the node
0746: * is the source.
0747: * @param node the node id (node table row number)
0748: * @return the out-degree of the node
0749: */
0750: public int getOutDegree(int node) {
0751: return m_links.getInt(node, OUTDEGREE);
0752: }
0753:
0754: /**
0755: * Get the out-degree of a node, the number of edges for which the node
0756: * is the source.
0757: * @param n the Node instance
0758: * @return the out-degree of the node
0759: */
0760: public int getOutDegree(Node n) {
0761: nodeCheck(n, true);
0762: return getOutDegree(n.getRow());
0763: }
0764:
0765: /**
0766: * Get the degree of a node, the number of edges for which a node
0767: * is either the source or the target.
0768: * @param node the node id (node table row number)
0769: * @return the total degree of the node
0770: */
0771: public int getDegree(int node) {
0772: return getInDegree(node) + getOutDegree(node);
0773: }
0774:
0775: /**
0776: * Get the degree of a node, the number of edges for which a node
0777: * is either the source or the target.
0778: * @param n the Node instance
0779: * @return the total degree of the node
0780: */
0781: public int getDegree(Node n) {
0782: nodeCheck(n, true);
0783: return getDegree(n.getRow());
0784: }
0785:
0786: // ------------------------------------------------------------------------
0787: // Edge Accessor Methods
0788:
0789: /**
0790: * Indicates if the edges of this graph are directed or undirected.
0791: * @return true if directed edges, false if undirected edges
0792: */
0793: public boolean isDirected() {
0794: return m_directed;
0795: }
0796:
0797: /**
0798: * Internal method for checking the validity of an edge.
0799: * @param e the Edge to check for validity
0800: * @param throwException true if this method should throw an Exception
0801: * when an invalid node is encountered
0802: * @return true is the edge is valid, false if invalid
0803: */
0804: protected boolean edgeCheck(Edge e, boolean throwException) {
0805: if (!e.isValid()) {
0806: if (throwException) {
0807: throw new IllegalArgumentException(
0808: "Edge must be valid.");
0809: }
0810: return false;
0811: }
0812: if (e.getGraph() != this ) {
0813: if (throwException) {
0814: throw new IllegalArgumentException(
0815: "Edge must be part of this Graph.");
0816: }
0817: return false;
0818: }
0819: return true;
0820: }
0821:
0822: /**
0823: * Get the collection of edges as a TupleSet. Returns the same result as
0824: * {@link CompositeTupleSet#getSet(String)} using
0825: * {@link #EDGES} as the parameter.
0826: * @return the edges of this graph as a TupleSet instance
0827: */
0828: public TupleSet getEdges() {
0829: return getSet(EDGES);
0830: }
0831:
0832: /**
0833: * Get the backing edge table.
0834: * @return the table of edge values
0835: */
0836: public Table getEdgeTable() {
0837: return (Table) getSet(EDGES);
0838: }
0839:
0840: /**
0841: * Get the number of edges in this graph.
0842: * @return the number of edges
0843: */
0844: public int getEdgeCount() {
0845: return getEdgeTable().getRowCount();
0846: }
0847:
0848: /**
0849: * Get the Edge tuple instance corresponding to an edge id.
0850: * @param e an edge id (edge table row number)
0851: * @return the Node instance corresponding to the node id
0852: */
0853: public Edge getEdge(int e) {
0854: return (e < 0 ? null : (Edge) m_edgeTuples.getTuple(e));
0855: }
0856:
0857: /**
0858: * Returns an edge from the source node to the target node. This
0859: * method returns the first such edge found; in the case of multiple
0860: * edges there may be more.
0861: */
0862: public int getEdge(int source, int target) {
0863: int outd = getOutDegree(source);
0864: if (outd > 0) {
0865: int[] edges = (int[]) m_links.get(source, OUTLINKS);
0866: for (int i = 0; i < outd; ++i) {
0867: if (getTargetNode(edges[i]) == target)
0868: return edges[i];
0869: }
0870: }
0871: return -1;
0872: }
0873:
0874: /**
0875: * Get an Edge with given source and target Nodes. There may be times
0876: * where there are multiple edges between two nodes; in those cases
0877: * this method returns the first such edge found.
0878: * @param source the source Node
0879: * @param target the target Node
0880: * @return an Edge with given source and target nodes, or null if no
0881: * such edge is found.
0882: */
0883: public Edge getEdge(Node source, Node target) {
0884: nodeCheck(source, true);
0885: nodeCheck(target, true);
0886: return getEdge(getEdge(source.getRow(), target.getRow()));
0887: }
0888:
0889: /**
0890: * Get the source node id (node table row number) for the given edge
0891: * id (edge table row number).
0892: * @param edge an edge id (edge table row number)
0893: * @return the source node id (node table row number)
0894: */
0895: public int getSourceNode(int edge) {
0896: return getNodeIndex(getEdgeTable().getLong(edge, m_skey));
0897: }
0898:
0899: /**
0900: * Get the source Node for the given Edge instance.
0901: * @param e an Edge instance
0902: * @return the source Node of the edge
0903: */
0904: public Node getSourceNode(Edge e) {
0905: edgeCheck(e, true);
0906: return getNode(getSourceNode(e.getRow()));
0907: }
0908:
0909: /**
0910: * Get the target node id (node table row number) for the given edge
0911: * id (edge table row number).
0912: * @param edge an edge id (edge table row number)
0913: * @return the target node id (node table row number)
0914: */
0915: public int getTargetNode(int edge) {
0916: return getNodeIndex(getEdgeTable().getLong(edge, m_tkey));
0917: }
0918:
0919: /**
0920: * Get the target Node for the given Edge instance.
0921: * @param e an Edge instance
0922: * @return the target Node of the edge
0923: */
0924: public Node getTargetNode(Edge e) {
0925: edgeCheck(e, true);
0926: return getNode(getTargetNode(e.getRow()));
0927: }
0928:
0929: /**
0930: * Given an edge id and an incident node id, return the node id for
0931: * the other node connected to the edge.
0932: * @param edge an edge id (edge table row number)
0933: * @param node a node id (node table row number). This node id must
0934: * be connected to the edge
0935: * @return the adjacent node id
0936: */
0937: public int getAdjacentNode(int edge, int node) {
0938: int s = getSourceNode(edge);
0939: int d = getTargetNode(edge);
0940:
0941: if (s == node) {
0942: return d;
0943: } else if (d == node) {
0944: return s;
0945: } else {
0946: throw new IllegalArgumentException(
0947: "Edge is not incident on the input node.");
0948: }
0949: }
0950:
0951: /**
0952: * Given an Edge and an incident Node, return the other Node
0953: * connected to the edge.
0954: * @param e an Edge instance
0955: * @param n a Node instance. This node must
0956: * be connected to the edge
0957: * @return the adjacent Node
0958: */
0959: public Node getAdjacentNode(Edge e, Node n) {
0960: edgeCheck(e, true);
0961: nodeCheck(n, true);
0962: return getNode(getAdjacentNode(e.getRow(), n.getRow()));
0963: }
0964:
0965: // ------------------------------------------------------------------------
0966: // Iterators
0967:
0968: // -- table row iterators ----
0969:
0970: /**
0971: * Get an iterator over all node ids (node table row numbers).
0972: * @return an iterator over all node ids (node table row numbers)
0973: */
0974: public IntIterator nodeRows() {
0975: return getNodeTable().rows();
0976: }
0977:
0978: /**
0979: * Get an iterator over all edge ids (edge table row numbers).
0980: * @return an iterator over all edge ids (edge table row numbers)
0981: */
0982: public IntIterator edgeRows() {
0983: return getEdgeTable().rows();
0984: }
0985:
0986: /**
0987: * Get an iterator over all edge ids for edges incident on the given node.
0988: * @param node a node id (node table row number)
0989: * @return an iterator over all edge ids for edges incident on the given
0990: * node
0991: */
0992: public IntIterator edgeRows(int node) {
0993: return edgeRows(node, UNDIRECTED);
0994: }
0995:
0996: /**
0997: * Get an iterator edge ids for edges incident on the given node.
0998: * @param node a node id (node table row number)
0999: * @param direction the directionality of the edges to include. One of
1000: * {@link #INEDGES} (for in-linking edges),
1001: * {@link #OUTEDGES} (for out-linking edges), or
1002: * {@link #UNDIRECTED} (for all edges).
1003: * @return an iterator over all edge ids for edges incident on the given
1004: * node
1005: */
1006: public IntIterator edgeRows(int node, int direction) {
1007: if (direction == OUTEDGES) {
1008: int[] outedges = (int[]) m_links.get(node, OUTLINKS);
1009: return new IntArrayIterator(outedges, 0, getOutDegree(node));
1010: } else if (direction == INEDGES) {
1011: int[] inedges = (int[]) m_links.get(node, INLINKS);
1012: return new IntArrayIterator(inedges, 0, getInDegree(node));
1013: } else if (direction == UNDIRECTED) {
1014: return new CompositeIntIterator(edgeRows(node, OUTEDGES),
1015: edgeRows(node, INEDGES));
1016: } else {
1017: throw new IllegalArgumentException(
1018: "Unrecognized edge type: "
1019: + direction
1020: + ". Type should be one of Graph.OUTEDGES, "
1021: + "Graoh.INEDGES, or Graph.ALL");
1022: }
1023: }
1024:
1025: /**
1026: * Get an iterator over all edges that have the given node as a target.
1027: * That is, edges that link into the given target node.
1028: * @param node a node id (node table row number)
1029: * @return an iterator over all edges that have the given node as a target
1030: */
1031: public IntIterator inEdgeRows(int node) {
1032: return edgeRows(node, INEDGES);
1033: }
1034:
1035: /**
1036: * Get an iterator over all edges that have the given node as a source.
1037: * That is, edges that link out from the given source node.
1038: * @param node a node id (node table row number)
1039: * @return an iterator over all edges that have the given node as a source
1040: */
1041: public IntIterator outEdgeRows(int node) {
1042: return edgeRows(node, OUTEDGES);
1043: }
1044:
1045: // -- tuple iterators --
1046:
1047: /**
1048: * Get an iterator over all nodes in the graph.
1049: * @return an iterator over Node instances
1050: */
1051: public Iterator nodes() {
1052: return m_nodeTuples.iterator(nodeRows());
1053: }
1054:
1055: /**
1056: * Get an iterator over all neighbor nodes for the given Node in the graph.
1057: * @param n a Node in the graph
1058: * @return an iterator over all Nodes connected to the input node
1059: */
1060: public Iterator neighbors(Node n) {
1061: return new NeighborIterator(n, edges(n));
1062: }
1063:
1064: /**
1065: * Get an iterator over all in-linking neighbor nodes for the given Node.
1066: * @param n a Node in the graph
1067: * @return an iterator over all Nodes that point to the input target node
1068: */
1069: public Iterator inNeighbors(Node n) {
1070: return new NeighborIterator(n, inEdges(n));
1071: }
1072:
1073: /**
1074: * Get an iterator over all out-linking neighbor nodes for the given Node.
1075: * @param n a Node in the graph
1076: * @return an iterator over all Nodes pointed to by the input source node
1077: */
1078: public Iterator outNeighbors(Node n) {
1079: return new NeighborIterator(n, outEdges(n));
1080: }
1081:
1082: /**
1083: * Get an iterator over all edges in the graph.
1084: * @return an iterator over Edge instances
1085: */
1086: public Iterator edges() {
1087: return m_edgeTuples.iterator(edgeRows());
1088: }
1089:
1090: /**
1091: * Get an iterator over all Edges connected to the given Node in the graph.
1092: * @param node a Node in the graph
1093: * @return an iterator over all Edges connected to the input node
1094: */
1095: public Iterator edges(Node node) {
1096: nodeCheck(node, true);
1097: return m_edgeTuples
1098: .iterator(edgeRows(node.getRow(), UNDIRECTED));
1099: }
1100:
1101: /**
1102: * Get an iterator over all in-linking edges to the given Node.
1103: * @param node a Node in the graph
1104: * @return an iterator over all in-linking edges to the input target node
1105: */
1106: public Iterator inEdges(Node node) {
1107: nodeCheck(node, true);
1108: return m_edgeTuples.iterator(inEdgeRows(node.getRow()));
1109: }
1110:
1111: /**
1112: * Get an iterator over all out-linking edges from the given Node.
1113: * @param node a Node in the graph
1114: * @return an iterator over all out-linking edges from the input source
1115: * node
1116: */
1117: public Iterator outEdges(Node node) {
1118: nodeCheck(node, true);
1119: return m_edgeTuples.iterator(outEdgeRows(node.getRow()));
1120: }
1121:
1122: // ------------------------------------------------------------------------
1123: // TupleSet Interface
1124:
1125: /**
1126: * Clear this graph, removing all nodes and edges.
1127: * @see prefuse.data.tuple.TupleSet#clear()
1128: */
1129: public void clear() {
1130: m_nodeTuples.invalidateAll();
1131: m_edgeTuples.invalidateAll();
1132: super .clear();
1133: m_links.clear();
1134: }
1135:
1136: /**
1137: * If the given tuple is a Node or Edge in this graph, remove it.
1138: * @see prefuse.data.tuple.TupleSet#removeTuple(prefuse.data.Tuple)
1139: */
1140: public boolean removeTuple(Tuple t) {
1141: // TODO: check underlying table tuples as well?
1142: if (t instanceof Node) {
1143: return removeNode((Node) t);
1144: } else if (t instanceof Edge) {
1145: return removeEdge((Edge) t);
1146: } else {
1147: throw new IllegalArgumentException(
1148: "Input tuple must be part of this graph");
1149: }
1150: }
1151:
1152: /**
1153: * Get a filtered iterator over the edges and nodes of this graph.
1154: * @see prefuse.data.tuple.TupleSet#tuples(prefuse.data.expression.Predicate)
1155: */
1156: public Iterator tuples(Predicate filter) {
1157: if (filter == null) {
1158: return tuples();
1159: } else {
1160: return new CompositeIterator(m_edgeTuples
1161: .iterator(getEdgeTable().rows(filter)),
1162: m_nodeTuples.iterator(getNodeTable().rows(filter)));
1163: }
1164: }
1165:
1166: /**
1167: * Get an iterator over all the edges and nodes of this graph. The iterator
1168: * will return all edges first, then all nodes.
1169: * @see prefuse.data.tuple.TupleSet#tuples()
1170: */
1171: public Iterator tuples() {
1172: return new CompositeIterator(edges(), nodes());
1173: }
1174:
1175: // ------------------------------------------------------------------------
1176: // Spanning Tree Methods
1177:
1178: /**
1179: * Return the current spanning tree over this graph. If no spanning tree
1180: * has been constructed, a SpanningTree rooted at the first valid node
1181: * found in the node table will be generated.
1182: *
1183: * Spanning trees are generated using an unweighted breadth first search
1184: * over the graph structure.
1185: *
1186: * @return a spanning tree over this graph
1187: * @see #getSpanningTree(Node)
1188: * @see #clearSpanningTree()
1189: */
1190: public Tree getSpanningTree() {
1191: if (m_spanning == null)
1192: return getSpanningTree((Node) nodes().next());
1193: else
1194: return m_spanning;
1195: }
1196:
1197: /**
1198: * Returns a spanning tree rooted at the specified node. If the current
1199: * spanning tree is alrady rooted at the given node, it is simply
1200: * returned. Otherwise, the tree is reconstructed at the new root and
1201: * made the current spanning tree for this Graph instance.
1202: *
1203: * Spanning trees are generated using an unweighted breadth first search
1204: * over the graph structure.
1205: *
1206: * @param root the node at which to root the spanning tree.
1207: * @return a spanning tree over this graph, rooted at the given root
1208: * @see #getSpanningTree()
1209: * @see #clearSpanningTree()
1210: */
1211: public Tree getSpanningTree(Node root) {
1212: nodeCheck(root, true);
1213: if (m_spanning == null) {
1214: m_spanning = new SpanningTree(this , root);
1215: } else if (m_spanning.getRoot() != root) {
1216: m_spanning.buildSpanningTree(root);
1217: }
1218: return m_spanning;
1219: }
1220:
1221: /**
1222: * Clear the internally stored spanning tree. Any new calls to a
1223: * getSpanningTree() method will generate a new spanning tree
1224: * instance as needed.
1225: *
1226: * This method is primarily useful for subclasses.
1227: * For example, calling this method on a Tree instance will revert the
1228: * state to the original rooted tree such that a sbusequent call to
1229: * getSpanningTree() will return the backing Tree itself.
1230: * @see #getSpanningTree()
1231: * @see #getSpanningTree(Node)
1232: * @see Tree#getSpanningTree(Node)
1233: */
1234: public void clearSpanningTree() {
1235: m_spanning = null;
1236: }
1237:
1238: // ------------------------------------------------------------------------
1239: // Graph Listeners
1240:
1241: /**
1242: * Add a listener to be notified of changes to the graph.
1243: * @param listnr the listener to add
1244: */
1245: public void addGraphModelListener(GraphListener listnr) {
1246: if (!m_listeners.contains(listnr))
1247: m_listeners.add(listnr);
1248: }
1249:
1250: /**
1251: * Remove a listener from this graph.
1252: * @param listnr the listener to remove
1253: */
1254: public void removeGraphModelListener(GraphListener listnr) {
1255: m_listeners.remove(listnr);
1256: }
1257:
1258: /**
1259: * Removes all listeners on this graph
1260: */
1261: public void removeAllGraphModelListeners() {
1262: m_listeners.clear();
1263: }
1264:
1265: /**
1266: * Fire a graph change event
1267: * @param t the backing table where the change occurred (either a
1268: * node table or an edge table)
1269: * @param first the first modified table row
1270: * @param last the last (inclusive) modified table row
1271: * @param col the number of the column modified, or
1272: * {@link prefuse.data.event.EventConstants#ALL_COLUMNS} for operations
1273: * affecting all columns
1274: * @param type the type of modification, one of
1275: * {@link prefuse.data.event.EventConstants#INSERT},
1276: * {@link prefuse.data.event.EventConstants#DELETE}, or
1277: * {@link prefuse.data.event.EventConstants#UPDATE}.
1278: */
1279: protected void fireGraphEvent(Table t, int first, int last,
1280: int col, int type) {
1281: String table = (t == getNodeTable() ? NODES : EDGES);
1282:
1283: if (type != EventConstants.UPDATE) {
1284: // fire event to all tuple set listeners
1285: fireTupleEvent(t, first, last, type);
1286: }
1287:
1288: if (!m_listeners.isEmpty()) {
1289: // fire event to all listeners
1290: Object[] lstnrs = m_listeners.getArray();
1291: for (int i = 0; i < lstnrs.length; ++i) {
1292: ((GraphListener) lstnrs[i]).graphChanged(this , table,
1293: first, last, col, type);
1294: }
1295: }
1296: }
1297:
1298: // ------------------------------------------------------------------------
1299: // Table and Column Listener
1300:
1301: /**
1302: * Listener class for tracking updates from node and edge tables,
1303: * and their columns that determine the graph linkage structure.
1304: */
1305: protected class Listener implements TableListener, ColumnListener {
1306:
1307: private Table m_edges;
1308: private Column m_scol, m_tcol;
1309: private int m_sidx, m_tidx;
1310:
1311: public void setEdgeTable(Table edges) {
1312: // remove any previous listeners
1313: if (m_scol != null)
1314: m_scol.removeColumnListener(this );
1315: if (m_tcol != null)
1316: m_tcol.removeColumnListener(this );
1317: m_scol = m_tcol = null;
1318: m_sidx = m_tidx = -1;
1319:
1320: m_edges = edges;
1321:
1322: // register listeners
1323: if (m_edges != null) {
1324: m_sidx = edges.getColumnNumber(m_skey);
1325: m_tidx = edges.getColumnNumber(m_tkey);
1326: m_scol = edges.getColumn(m_sidx);
1327: m_tcol = edges.getColumn(m_tidx);
1328: m_scol.addColumnListener(this );
1329: m_tcol.addColumnListener(this );
1330: }
1331: }
1332:
1333: public void tableChanged(Table t, int start, int end, int col,
1334: int type) {
1335: if (!containsSet(t))
1336: throw new IllegalStateException(
1337: "Graph shouldn't be listening to an unrelated table");
1338:
1339: if (type != EventConstants.UPDATE) {
1340: if (t == getNodeTable()) {
1341: // update the linkage structure table
1342: if (col == EventConstants.ALL_COLUMNS) {
1343: boolean added = type == EventConstants.INSERT;
1344: for (int r = start; r <= end; ++r)
1345: updateNodeData(r, added);
1346: }
1347: } else {
1348: // update the linkage structure table
1349: if (col == EventConstants.ALL_COLUMNS) {
1350: boolean added = type == EventConstants.INSERT;
1351: for (int r = start; r <= end; ++r)
1352: updateDegrees(start, added ? 1 : -1);
1353: }
1354: }
1355: // clear the spanning tree reference
1356: m_spanning = null;
1357: }
1358: fireGraphEvent(t, start, end, col, type);
1359: }
1360:
1361: public void columnChanged(Column src, int idx, int prev) {
1362: columnChanged(src, idx, (long) prev);
1363: }
1364:
1365: public void columnChanged(Column src, int idx, long prev) {
1366: if (src == m_scol || src == m_tcol) {
1367: boolean isSrc = src == m_scol;
1368: int e = m_edges.getTableRow(idx, isSrc ? m_sidx
1369: : m_tidx);
1370: if (e == -1)
1371: return; // edge not in this graph
1372: int s = getSourceNode(e);
1373: int t = getTargetNode(e);
1374: int p = getNodeIndex(prev);
1375: if (p > -1 && ((isSrc && t > -1) || (!isSrc && s > -1)))
1376: updateDegrees(e, isSrc ? p : s, isSrc ? t : p, -1);
1377: if (s > -1 && t > -1)
1378: updateDegrees(e, s, t, 1);
1379: } else {
1380: throw new IllegalStateException();
1381: }
1382: }
1383:
1384: public void columnChanged(Column src, int type, int start,
1385: int end) {
1386: // should never be called
1387: throw new IllegalStateException();
1388: }
1389:
1390: public void columnChanged(Column src, int idx, float prev) {
1391: // should never be called
1392: throw new IllegalStateException();
1393: }
1394:
1395: public void columnChanged(Column src, int idx, double prev) {
1396: // should never be called
1397: throw new IllegalStateException();
1398: }
1399:
1400: public void columnChanged(Column src, int idx, boolean prev) {
1401: // should never be called
1402: throw new IllegalStateException();
1403: }
1404:
1405: public void columnChanged(Column src, int idx, Object prev) {
1406: // should never be called
1407: throw new IllegalStateException();
1408: }
1409: } // end of inner class Listener
1410:
1411: // ------------------------------------------------------------------------
1412: // Graph Linkage Schema
1413:
1414: /** In-degree data field for the links table */
1415: protected static final String INDEGREE = "_indegree";
1416: /** Out-degree data field for the links table */
1417: protected static final String OUTDEGREE = "_outdegree";
1418: /** In-links adjacency list data field for the links table */
1419: protected static final String INLINKS = "_inlinks";
1420: /** Out-links adjacency list data field for the links table */
1421: protected static final String OUTLINKS = "_outlinks";
1422: /** Schema used for the internal graph linkage table */
1423: protected static final Schema LINKS_SCHEMA = new Schema();
1424: static {
1425: Integer defaultValue = new Integer(0);
1426: LINKS_SCHEMA.addColumn(INDEGREE, int.class, defaultValue);
1427: LINKS_SCHEMA.addColumn(OUTDEGREE, int.class, defaultValue);
1428: LINKS_SCHEMA.addColumn(INLINKS, int[].class);
1429: LINKS_SCHEMA.addColumn(OUTLINKS, int[].class);
1430: LINKS_SCHEMA.lockSchema();
1431: }
1432:
1433: } // end of class Graph
|