package prefuse.data; import java.util.Iterator; import prefuse.data.column.Column; import prefuse.data.event.ColumnListener; import prefuse.data.event.EventConstants; import prefuse.data.event.GraphListener; import prefuse.data.event.TableListener; import prefuse.data.expression.Predicate; import prefuse.data.tuple.CompositeTupleSet; import prefuse.data.tuple.TableEdge; import prefuse.data.tuple.TableNode; import prefuse.data.tuple.TupleManager; import prefuse.data.tuple.TupleSet; import prefuse.data.util.Index; import prefuse.data.util.NeighborIterator; import prefuse.util.PrefuseConfig; import prefuse.util.collections.CompositeIntIterator; import prefuse.util.collections.CompositeIterator; import prefuse.util.collections.CopyOnWriteArrayList; import prefuse.util.collections.IntArrayIterator; import prefuse.util.collections.IntIterator; /** *
A Graph models a network of nodes connected by a collection of edges. * Both nodes and edges can have any number of associated data fields. * Additionally, edges are either directed or undirected, indicating a * possible directionality of the connection. Each edge has both a source * node and a target node, for a directed edge this indicates the * directionality, for an undirected edge this is just an artifact * of the order in which the nodes were specified when added to the graph. *
* *Both nodes and edges are represented by backing data {@link Table} * instances storing the data attributes. For edges, this table must * also contain a source node field and a target node field. The default * column name for these fields are {@link #DEFAULT_SOURCE_KEY} and * {@link #DEFAULT_TARGET_KEY}, but these can be configured by the graph * constructor. These columns should be integer valued, and contain * either the row number for a corresponding node in the node table, * or another unique identifier for a node. In this second case, the * unique identifier must be included as a data field in the node * table. This name of this column can be configured using the appropriate * graph constructor. The default column name for this field is * {@link #DEFAULT_NODE_KEY}, which by default evaluates to null, * indicating that no special node key should be used, just the direct * node table row numbers. Though the source, target, and node key * values completely specify the graph linkage structure, to make * graph operations more efficient an additional table is maintained * internally by the Graph class, storing node indegree and outdegree * counts and adjacency lists for the inlinks and outlinks for all nodes.
* *Graph nodes and edges can be accessed by application code by either * using the row numbers of the node and edge tables, which provide unique ids * for each, or using the {@link prefuse.data.Node} and * {@link prefuse.data.Edge} classes -- * {@link prefuse.data.Tuple} instances that provide * object-oriented access to both node or edge data values and the * backing graph structure. Node and Edge tuples are maintained by * special TupleManager instances contained within this Graph. By default, they * are not accessible from the backing node or edge tables directly. The reason * for this is that these tables might be used in multiple graphs * simultaneously. For example, a node data table could be used in a number of * different graphs, exploring different possible linkages between those node. * In short, use this Graph instance to request iterators over Node or * Edge tuples, not the backing data tables.
* *All Graph instances also support an internally generated * spanning tree, provided by the {@link #getSpanningTree()} or * {@link #getSpanningTree(Node)} methods. This is particularly * useful in visualization contexts that use an underlying tree structure * to compute a graph layout.
* * @author jeffrey heer */ public class Graph extends CompositeTupleSet { /** Indicates incoming edges (inlinks) */ public static final int INEDGES = 0; /** Indicates outgoing edges (outlinks) */ public static final int OUTEDGES = 1; /** Indicates all edges, regardless of direction */ public static final int UNDIRECTED = 2; /** Default data field used to uniquely identify a node */ public static final String DEFAULT_NODE_KEY = PrefuseConfig.get("data.graph.nodeKey"); /** Default data field used to denote the source node in an edge table */ public static final String DEFAULT_SOURCE_KEY = PrefuseConfig.get("data.graph.sourceKey"); /** Default data field used to denote the target node in an edge table */ public static final String DEFAULT_TARGET_KEY = PrefuseConfig.get("data.graph.targetKey"); /** Data group name to identify the nodes of this graph */ public static final String NODES = PrefuseConfig.get("data.graph.nodeGroup"); /** Data group name to identify the edges of this graph */ public static final String EDGES = PrefuseConfig.get("data.graph.edgeGroup"); // -- auxiliary data structures ----- /** Table containing the adjacency lists for the graph */ protected Table m_links; /** TupleManager for managing Node tuple instances */ protected TupleManager m_nodeTuples; /** TupleManager for managing Edge tuple instances */ protected TupleManager m_edgeTuples; /** Indicates if this graph is directed or undirected */ protected boolean m_directed = false; /** The spanning tree over this graph */ protected SpanningTree m_spanning = null; /** The node key field (for the Node table) */ protected String m_nkey; /** The source node key field (for the Edge table) */ protected String m_skey; /** The target node key field (for the Edge table) */ protected String m_tkey; /** Reference to an index over the node key field */ protected Index m_nidx; /** Update listener */ private Listener m_listener; /** Listener list */ private CopyOnWriteArrayList m_listeners = new CopyOnWriteArrayList(); // ------------------------------------------------------------------------ // Constructors /** * Creates a new, empty undirected Graph. */ public Graph() { this(false); } /** * Creates a new, empty Graph. * @param directed true for directed edges, false for undirected */ public Graph(boolean directed) { this(new Table(), directed); } /** * Create a new Graph using the provided table of node data and * an empty set of edges. * @param nodes the backing table to use for node data. * Node instances of this graph will get their data from this table. * @param directed true for directed edges, false for undirected */ public Graph(Table nodes, boolean directed) { this(nodes, directed, DEFAULT_NODE_KEY, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY); } /** * Create a new Graph using the provided table of node data and * an empty set of edges. * @param nodes the backing table to use for node data. * Node instances of this graph will get their data from this table. * @param directed true for directed edges, false for undirected * @param nodeKey data field used to uniquely identify a node. If this * field is null, the node table row numbers will be used * @param sourceKey data field used to denote the source node in an edge * table * @param targetKey data field used to denote the target node in an edge * table */ public Graph(Table nodes, boolean directed, String nodeKey, String sourceKey, String targetKey) { Table edges = new Table(); edges.addColumn(sourceKey, int.class, new Integer(-1)); edges.addColumn(targetKey, int.class, new Integer(-1)); init(nodes, edges, directed, nodeKey, sourceKey, targetKey); } /** * Create a new Graph, using node table row numbers to uniquely * identify nodes in the edge table's source and target fields. * @param nodes the backing table to use for node data. * Node instances of this graph will get their data from this table. * @param edges the backing table to use for edge data. * Edge instances of this graph will get their data from this table. * @param directed true for directed edges, false for undirected */ public Graph(Table nodes, Table edges, boolean directed) { this(nodes, edges, directed, DEFAULT_NODE_KEY, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY); } /** * Create a new Graph, using node table row numbers to uniquely * identify nodes in the edge table's source and target fields. * @param nodes the backing table to use for node data. * Node instances of this graph will get their data from this table. * @param edges the backing table to use for edge data. * Edge instances of this graph will get their data from this table. * @param directed true for directed edges, false for undirected * @param sourceKey data field used to denote the source node in an edge * table * @param targetKey data field used to denote the target node in an edge * table */ public Graph(Table nodes, Table edges, boolean directed, String sourceKey, String targetKey) { init(nodes, edges, directed, DEFAULT_NODE_KEY, sourceKey, targetKey); } /** * Create a new Graph. * @param nodes the backing table to use for node data. * Node instances of this graph will get their data from this table. * @param edges the backing table to use for edge data. * Edge instances of this graph will get their data from this table. * @param directed true for directed edges, false for undirected * @param nodeKey data field used to uniquely identify a node. If this * field is null, the node table row numbers will be used * @param sourceKey data field used to denote the source node in an edge * table * @param targetKey data field used to denote the target node in an edge * table */ public Graph(Table nodes, Table edges, boolean directed, String nodeKey, String sourceKey, String targetKey) { init(nodes, edges, directed, nodeKey, sourceKey, targetKey); } // ------------------------------------------------------------------------ // Initialization /** * Initialize this Graph instance. * @param nodes the node table * @param edges the edge table * @param directed the edge directionality * @param nodeKey data field used to uniquely identify a node * @param sourceKey data field used to denote the source node in an edge * table * @param targetKey data field used to denote the target node in an edge * table */ protected void init(Table nodes, Table edges, boolean directed, String nodeKey, String sourceKey, String targetKey) { // sanity check if ( (nodeKey!=null && nodes.getColumnType(nodeKey) != int.class) || edges.getColumnType(sourceKey) != int.class || edges.getColumnType(targetKey) != int.class ) { throw new IllegalArgumentException( "Incompatible column types for graph keys"); } removeAllSets(); super.addSet(EDGES, edges); super.addSet(NODES, nodes); m_directed = directed; // INVARIANT: these three should all reference the same type // currently limited to int m_nkey = nodeKey; m_skey = sourceKey; m_tkey = targetKey; // set up indices if ( nodeKey != null ) { nodes.index(nodeKey); m_nidx = nodes.getIndex(nodeKey); } // set up tuple manager if ( m_nodeTuples == null ) m_nodeTuples = new TupleManager(nodes, this, TableNode.class); m_edgeTuples = new TupleManager(edges, this, TableEdge.class); // set up node attribute optimization initLinkTable(); // set up listening if ( m_listener == null ) m_listener = new Listener(); nodes.addTableListener(m_listener); edges.addTableListener(m_listener); m_listener.setEdgeTable(edges); } /** * Set the tuple managers used to manage the Node and Edge tuples of this * Graph. * @param ntm the TupleManager to use for nodes * @param etm the TupleManager to use for edges */ public void setTupleManagers(TupleManager ntm, TupleManager etm) { if ( !Node.class.isAssignableFrom(ntm.getTupleType()) ) throw new IllegalArgumentException("The provided node " + "TupleManager must generate tuples that implement " + "the Node interface."); if ( !Edge.class.isAssignableFrom(etm.getTupleType()) ) throw new IllegalArgumentException("The provided edge " + "TupleManager must generate tuples that implement " + "the Edge interface."); m_nodeTuples = ntm; m_edgeTuples = etm; } /** * Dispose of this graph. Unregisters this graph as a listener to its * included tables. */ public void dispose() { getNodeTable().removeTableListener(m_listener); getEdgeTable().removeTableListener(m_listener); } /** * Updates this graph to use a different edge structure for the same nodes. * All other settings will remain the same (e.g., directionality, keys) * @param edges the new edge table. */ public void setEdgeTable(Table edges) { Table oldEdges = getEdgeTable(); oldEdges.removeTableListener(m_listener); m_edgeTuples.invalidateAll(); m_links.clear(); init(getNodeTable(), edges, m_directed, m_nkey, m_skey, m_tkey); } // ------------------------------------------------------------------------ // Data Access Optimization /** * Initialize the link table, which holds adjacency lists for this graph. */ protected void initLinkTable() { // set up cache of node data m_links = createLinkTable(); IntIterator edges = getEdgeTable().rows(); while ( edges.hasNext() ) { updateDegrees(edges.nextInt(), 1); } } /** * Instantiate and return the link table. * @return the created link table */ protected Table createLinkTable() { return LINKS_SCHEMA.instantiate(getNodeTable().getMaximumRow()+1); } /** * Internal method for updating the linkage of this graph. * @param e the edge id for the updated link * @param incr the increment value, 1 for an added link, * -1 for a removed link */ protected void updateDegrees(int e, int incr) { if ( !getEdgeTable().isValidRow(e) ) return; int s = getSourceNode(e); int t = getTargetNode(e); if ( s < 0 || t < 0 ) return; updateDegrees(e, s, t, incr); if ( incr < 0 ) { m_edgeTuples.invalidate(e); } } /** * Internal method for updating the linkage of this graph. * @param e the edge id for the updated link * @param s the source node id for the updated link * @param t the target node id for the updated link * @param incr the increment value, 1 for an added link, * -1 for a removed link */ protected void updateDegrees(int e, int s, int t, int incr) { int od = m_links.getInt(s, OUTDEGREE); int id = m_links.getInt(t, INDEGREE); // update adjacency lists if ( incr > 0 ) { // add links addLink(OUTLINKS, od, s, e); addLink(INLINKS, id, t, e); } else if ( incr < 0 ) { // remove links remLink(OUTLINKS, od, s, e); remLink(INLINKS, id, t, e); } // update degree counts m_links.setInt(s, OUTDEGREE, od+incr); m_links.setInt(t, INDEGREE, id+incr); // link structure changed, invalidate spanning tree m_spanning = null; } /** * Internal method for adding a link to an adjacency list * @param field which adjacency list (inlinks or outlinks) to use * @param len the length of the adjacency list * @param n the node id of the adjacency list to use * @param e the edge to add to the list */ protected void addLink(String field, int len, int n, int e) { int[] array = (int[])m_links.get(n, field); if ( array == null ) { array = new int[] {e}; m_links.set(n, field, array); return; } else if ( len == array.length ) { int[] narray = new int[Math.max(3*array.length/2, len+1)]; System.arraycopy(array, 0, narray, 0, array.length); array = narray; m_links.set(n, field, array); } array[len] = e; } /** * Internal method for removing a link from an adjacency list * @param field which adjacency list (inlinks or outlinks) to use * @param len the length of the adjacency list * @param n the node id of the adjacency list to use * @param e the edge to remove from the list * @return true if the link was removed successfully, false otherwise */ protected boolean remLink(String field, int len, int n, int e) { int[] array = (int[])m_links.get(n, field); for ( int i=0; i