prefuse.data
Class Graph

java.lang.Object
  extended by prefuse.data.tuple.AbstractTupleSet
      extended by prefuse.data.tuple.CompositeTupleSet
          extended by prefuse.data.Graph
All Implemented Interfaces:
TupleSet
Direct Known Subclasses:
Tree, VisualGraph

public class Graph
extends CompositeTupleSet

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 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 DEFAULT_SOURCE_KEY and 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 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 Node and Edge classes -- 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 getSpanningTree() or getSpanningTree(Node) methods. This is particularly useful in visualization contexts that use an underlying tree structure to compute a graph layout.

Author:
jeffrey heer

Nested Class Summary
protected  class Graph.Listener
          Listener class for tracking updates from node and edge tables, and their columns that determine the graph linkage structure.
 
Field Summary
static java.lang.String DEFAULT_NODE_KEY
          Default data field used to uniquely identify a node
static java.lang.String DEFAULT_SOURCE_KEY
          Default data field used to denote the source node in an edge table
static java.lang.String DEFAULT_TARGET_KEY
          Default data field used to denote the target node in an edge table
static java.lang.String EDGES
          Data group name to identify the edges of this graph
protected static java.lang.String INDEGREE
          In-degree data field for the links table
static int INEDGES
          Indicates incoming edges (inlinks)
protected static java.lang.String INLINKS
          In-links adjacency list data field for the links table
protected static Schema LINKS_SCHEMA
          Schema used for the internal graph linkage table
protected  boolean m_directed
          Indicates if this graph is directed or undirected
protected  TupleManager m_edgeTuples
          TupleManager for managing Edge tuple instances
protected  Table m_links
          Table containing the adjacency lists for the graph
protected  boolean m_longKey
          Indicates if the key values are of type long
protected  Index m_nidx
          Reference to an index over the node key field
protected  java.lang.String m_nkey
          The node key field (for the Node table)
protected  TupleManager m_nodeTuples
          TupleManager for managing Node tuple instances
protected  java.lang.String m_skey
          The source node key field (for the Edge table)
protected  SpanningTree m_spanning
          The spanning tree over this graph
protected  java.lang.String m_tkey
          The target node key field (for the Edge table)
static java.lang.String NODES
          Data group name to identify the nodes of this graph
protected static java.lang.String OUTDEGREE
          Out-degree data field for the links table
static int OUTEDGES
          Indicates outgoing edges (outlinks)
protected static java.lang.String OUTLINKS
          Out-links adjacency list data field for the links table
static int UNDIRECTED
          Indicates all edges, regardless of direction
 
Fields inherited from interface prefuse.data.tuple.TupleSet
EMPTY_ARRAY
 
Constructor Summary
Graph()
          Creates a new, empty undirected Graph.
Graph(boolean directed)
          Creates a new, empty Graph.
Graph(Table nodes, boolean directed)
          Create a new Graph using the provided table of node data and an empty set of edges.
Graph(Table nodes, boolean directed, java.lang.String nodeKey, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Graph using the provided table of node data and an empty set of edges.
Graph(Table nodes, Table edges, boolean directed)
          Create a new Graph, using node table row numbers to uniquely identify nodes in the edge table's source and target fields.
Graph(Table nodes, Table edges, boolean directed, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Graph, using node table row numbers to uniquely identify nodes in the edge table's source and target fields.
Graph(Table nodes, Table edges, boolean directed, java.lang.String nodeKey, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Graph.
 
Method Summary
 int addEdge(int s, int t)
          Add an edge to the graph.
 Edge addEdge(Node s, Node t)
          Add an edge to the graph.
 void addGraphModelListener(GraphListener listnr)
          Add a listener to be notified of changes to the graph.
protected  void addLink(java.lang.String field, int len, int n, int e)
          Internal method for adding a link to an adjacency list
 Node addNode()
          Add a new node to the graph.
 int addNodeRow()
          Add row to the node table, thereby adding a node to the graph.
 void clear()
          Clear this graph, removing all nodes and edges.
protected  void clearEdges()
          Internal method for clearing the edge table, removing all edges.
 void clearSpanningTree()
          Clear the internally stored spanning tree.
protected  Table createLinkTable()
          Instantiate and return the link table.
 void dispose()
          Dispose of this graph.
protected  boolean edgeCheck(Edge e, boolean throwException)
          Internal method for checking the validity of an edge.
 IntIterator edgeRows()
          Get an iterator over all edge ids (edge table row numbers).
 IntIterator edgeRows(int node)
          Get an iterator over all edge ids for edges incident on the given node.
 IntIterator edgeRows(int node, int direction)
          Get an iterator edge ids for edges incident on the given node.
 java.util.Iterator edges()
          Get an iterator over all edges in the graph.
 java.util.Iterator edges(Node node)
          Get an iterator over all Edges connected to the given Node in the graph.
protected  void fireGraphEvent(Table t, int first, int last, int col, int type)
          Fire a graph change event
 Node getAdjacentNode(Edge e, Node n)
          Given an Edge and an incident Node, return the other Node connected to the edge.
 int getAdjacentNode(int edge, int node)
          Given an edge id and an incident node id, return the node id for the other node connected to the edge.
 int getDegree(int node)
          Get the degree of a node, the number of edges for which a node is either the source or the target.
 int getDegree(Node n)
          Get the degree of a node, the number of edges for which a node is either the source or the target.
 Edge getEdge(int e)
          Get the Edge tuple instance corresponding to an edge id.
 int getEdge(int source, int target)
          Returns an edge from the source node to the target node.
 Edge getEdge(Node source, Node target)
          Get an Edge with given source and target Nodes.
 int getEdgeCount()
          Get the number of edges in this graph.
 TupleSet getEdges()
          Get the collection of edges as a TupleSet.
 java.lang.String getEdgeSourceField()
          Get the data field used to denote the source node in an edge table.
 Table getEdgeTable()
          Get the backing edge table.
 java.lang.String getEdgeTargetField()
          Get the data field used to denote the target node in an edge table.
 int getInDegree(int node)
          Get the in-degree of a node, the number of edges for which the node is the target.
 int getInDegree(Node n)
          Get the in-degree of a node, the number of edges for which the node is the target.
 long getKey(int node)
          Given a node id (a row number in the node table), get the value of the node key field.
 Node getNode(int n)
          Get the Node tuple instance corresponding to a node id.
 int getNodeCount()
          Get the number of nodes in this graph.
 Node getNodeFromKey(long key)
          Get the Node tuple corresponding to the input node key field value.
 int getNodeIndex(long key)
          Given a value of the node key field, get the node id (the row number in the node table).
 java.lang.String getNodeKeyField()
          Get the data field used to uniquely identify a node
 TupleSet getNodes()
          Get the collection of nodes as a TupleSet.
 Table getNodeTable()
          Get the backing node table.
 int getOutDegree(int node)
          Get the out-degree of a node, the number of edges for which the node is the source.
 int getOutDegree(Node n)
          Get the out-degree of a node, the number of edges for which the node is the source.
 Node getSourceNode(Edge e)
          Get the source Node for the given Edge instance.
 int getSourceNode(int edge)
          Get the source node id (node table row number) for the given edge id (edge table row number).
 Tree getSpanningTree()
          Return the current spanning tree over this graph.
 Tree getSpanningTree(Node root)
          Returns a spanning tree rooted at the specified node.
 Node getTargetNode(Edge e)
          Get the target Node for the given Edge instance.
 int getTargetNode(int edge)
          Get the target node id (node table row number) for the given edge id (edge table row number).
 IntIterator inEdgeRows(int node)
          Get an iterator over all edges that have the given node as a target.
 java.util.Iterator inEdges(Node node)
          Get an iterator over all in-linking edges to the given Node.
protected  void init(Table nodes, Table edges, boolean directed, java.lang.String nodeKey, java.lang.String sourceKey, java.lang.String targetKey)
          Initialize this Graph instance.
protected  void initLinkTable()
          Initialize the link table, which holds adjacency lists for this graph.
 java.util.Iterator inNeighbors(Node n)
          Get an iterator over all in-linking neighbor nodes for the given Node.
 boolean isDirected()
          Indicates if the edges of this graph are directed or undirected.
 java.util.Iterator neighbors(Node n)
          Get an iterator over all neighbor nodes for the given Node in the graph.
protected  boolean nodeCheck(Node n, boolean throwException)
          Internal method for checking the validity of a node.
 IntIterator nodeRows()
          Get an iterator over all node ids (node table row numbers).
 java.util.Iterator nodes()
          Get an iterator over all nodes in the graph.
 IntIterator outEdgeRows(int node)
          Get an iterator over all edges that have the given node as a source.
 java.util.Iterator outEdges(Node node)
          Get an iterator over all out-linking edges from the given Node.
 java.util.Iterator outNeighbors(Node n)
          Get an iterator over all out-linking neighbor nodes for the given Node.
protected  boolean remLink(java.lang.String field, int len, int n, int e)
          Internal method for removing a link from an adjacency list
 void removeAllGraphModelListeners()
          Removes all listeners on this graph
 boolean removeEdge(Edge e)
          Remove an edge from the graph.
 boolean removeEdge(int edge)
          Remove an edge from the graph.
 void removeGraphModelListener(GraphListener listnr)
          Remove a listener from this graph.
 boolean removeNode(int node)
          Remove a node from the graph, also removing all incident edges.
 boolean removeNode(Node n)
          Remove a node from the graph, also removing all incident edges.
 boolean removeTuple(Tuple t)
          If the given tuple is a Node or Edge in this graph, remove it.
 void setEdgeTable(Table edges)
          Updates this graph to use a different edge structure for the same nodes.
 void setTupleManagers(TupleManager ntm, TupleManager etm)
          Set the tuple managers used to manage the Node and Edge tuples of this Graph.
 java.util.Iterator tuples()
          Get an iterator over all the edges and nodes of this graph.
 java.util.Iterator tuples(Predicate filter)
          Get a filtered iterator over the edges and nodes of this graph.
protected  void updateDegrees(int e, int incr)
          Internal method for updating the linkage of this graph.
protected  void updateDegrees(int e, int s, int t, int incr)
          Internal method for updating the linkage of this graph.
protected  void updateNodeData(int r, boolean added)
          Update the link table to accomodate an inserted or deleted node
 
Methods inherited from class prefuse.data.tuple.CompositeTupleSet
addColumn, addColumn, addColumn, addColumn, addSet, addTuple, containsSet, containsTuple, getSet, getTupleCount, hasSet, isAddColumnSupported, removeAllSets, removeSet, setNames, sets, setTuple
 
Methods inherited from class prefuse.data.tuple.AbstractTupleSet
addColumns, addPropertyChangeListener, addPropertyChangeListener, addTupleSetListener, fireTupleEvent, fireTupleEvent, fireTupleEvent, getClientProperty, putClientProperty, removePropertyChangeListener, removePropertyChangeListener, removeTupleSetListener, tuples
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

INEDGES

public static final int INEDGES
Indicates incoming edges (inlinks)

See Also:
Constant Field Values

OUTEDGES

public static final int OUTEDGES
Indicates outgoing edges (outlinks)

See Also:
Constant Field Values

UNDIRECTED

public static final int UNDIRECTED
Indicates all edges, regardless of direction

See Also:
Constant Field Values

DEFAULT_NODE_KEY

public static final java.lang.String DEFAULT_NODE_KEY
Default data field used to uniquely identify a node


DEFAULT_SOURCE_KEY

public static final java.lang.String DEFAULT_SOURCE_KEY
Default data field used to denote the source node in an edge table


DEFAULT_TARGET_KEY

public static final java.lang.String DEFAULT_TARGET_KEY
Default data field used to denote the target node in an edge table


NODES

public static final java.lang.String NODES
Data group name to identify the nodes of this graph


EDGES

public static final java.lang.String EDGES
Data group name to identify the edges of this graph


m_links

protected Table m_links
Table containing the adjacency lists for the graph


m_nodeTuples

protected TupleManager m_nodeTuples
TupleManager for managing Node tuple instances


m_edgeTuples

protected TupleManager m_edgeTuples
TupleManager for managing Edge tuple instances


m_directed

protected boolean m_directed
Indicates if this graph is directed or undirected


m_spanning

protected SpanningTree m_spanning
The spanning tree over this graph


m_nkey

protected java.lang.String m_nkey
The node key field (for the Node table)


m_skey

protected java.lang.String m_skey
The source node key field (for the Edge table)


m_tkey

protected java.lang.String m_tkey
The target node key field (for the Edge table)


m_nidx

protected Index m_nidx
Reference to an index over the node key field


m_longKey

protected boolean m_longKey
Indicates if the key values are of type long


INDEGREE

protected static final java.lang.String INDEGREE
In-degree data field for the links table

See Also:
Constant Field Values

OUTDEGREE

protected static final java.lang.String OUTDEGREE
Out-degree data field for the links table

See Also:
Constant Field Values

INLINKS

protected static final java.lang.String INLINKS
In-links adjacency list data field for the links table

See Also:
Constant Field Values

OUTLINKS

protected static final java.lang.String OUTLINKS
Out-links adjacency list data field for the links table

See Also:
Constant Field Values

LINKS_SCHEMA

protected static final Schema LINKS_SCHEMA
Schema used for the internal graph linkage table

Constructor Detail

Graph

public Graph()
Creates a new, empty undirected Graph.


Graph

public Graph(boolean directed)
Creates a new, empty Graph.

Parameters:
directed - true for directed edges, false for undirected

Graph

public Graph(Table nodes,
             boolean directed)
Create a new Graph using the provided table of node data and an empty set of edges.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
directed - true for directed edges, false for undirected

Graph

public Graph(Table nodes,
             boolean directed,
             java.lang.String nodeKey,
             java.lang.String sourceKey,
             java.lang.String targetKey)
Create a new Graph using the provided table of node data and an empty set of edges.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
directed - true for directed edges, false for undirected
nodeKey - data field used to uniquely identify a node. If this field is null, the node table row numbers will be used
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table

Graph

public Graph(Table nodes,
             Table edges,
             boolean directed)
Create a new Graph, using node table row numbers to uniquely identify nodes in the edge table's source and target fields.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.
directed - true for directed edges, false for undirected

Graph

public Graph(Table nodes,
             Table edges,
             boolean directed,
             java.lang.String sourceKey,
             java.lang.String targetKey)
Create a new Graph, using node table row numbers to uniquely identify nodes in the edge table's source and target fields.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.
directed - true for directed edges, false for undirected
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table

Graph

public Graph(Table nodes,
             Table edges,
             boolean directed,
             java.lang.String nodeKey,
             java.lang.String sourceKey,
             java.lang.String targetKey)
Create a new Graph.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.
directed - true for directed edges, false for undirected
nodeKey - data field used to uniquely identify a node. If this field is null, the node table row numbers will be used
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table
Method Detail

init

protected void init(Table nodes,
                    Table edges,
                    boolean directed,
                    java.lang.String nodeKey,
                    java.lang.String sourceKey,
                    java.lang.String targetKey)
Initialize this Graph instance.

Parameters:
nodes - the node table
edges - the edge table
directed - the edge directionality
nodeKey - data field used to uniquely identify a node
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table

setTupleManagers

public void setTupleManagers(TupleManager ntm,
                             TupleManager etm)
Set the tuple managers used to manage the Node and Edge tuples of this Graph.

Parameters:
ntm - the TupleManager to use for nodes
etm - the TupleManager to use for edges

dispose

public void dispose()
Dispose of this graph. Unregisters this graph as a listener to its included tables.


setEdgeTable

public void setEdgeTable(Table edges)
Updates this graph to use a different edge structure for the same nodes. All other settings will remain the same (e.g., directionality, keys)

Parameters:
edges - the new edge table.

initLinkTable

protected void initLinkTable()
Initialize the link table, which holds adjacency lists for this graph.


createLinkTable

protected Table createLinkTable()
Instantiate and return the link table.

Returns:
the created link table

updateDegrees

protected void updateDegrees(int e,
                             int incr)
Internal method for updating the linkage of this graph.

Parameters:
e - the edge id for the updated link
incr - the increment value, 1 for an added link, -1 for a removed link

updateDegrees

protected void updateDegrees(int e,
                             int s,
                             int t,
                             int incr)
Internal method for updating the linkage of this graph.

Parameters:
e - the edge id for the updated link
s - the source node id for the updated link
t - the target node id for the updated link
incr - the increment value, 1 for an added link, -1 for a removed link

addLink

protected void addLink(java.lang.String field,
                       int len,
                       int n,
                       int e)
Internal method for adding a link to an adjacency list

Parameters:
field - which adjacency list (inlinks or outlinks) to use
len - the length of the adjacency list
n - the node id of the adjacency list to use
e - the edge to add to the list

remLink

protected boolean remLink(java.lang.String field,
                          int len,
                          int n,
                          int e)
Internal method for removing a link from an adjacency list

Parameters:
field - which adjacency list (inlinks or outlinks) to use
len - the length of the adjacency list
n - the node id of the adjacency list to use
e - the edge to remove from the list
Returns:
true if the link was removed successfully, false otherwise

updateNodeData

protected void updateNodeData(int r,
                              boolean added)
Update the link table to accomodate an inserted or deleted node

Parameters:
r - the node id, also the row number into the link table
added - indicates if a node was added or removed

getNodeKeyField

public java.lang.String getNodeKeyField()
Get the data field used to uniquely identify a node

Returns:
the data field used to uniquely identify a node

getEdgeSourceField

public java.lang.String getEdgeSourceField()
Get the data field used to denote the source node in an edge table.

Returns:
the data field used to denote the source node in an edge table.

getEdgeTargetField

public java.lang.String getEdgeTargetField()
Get the data field used to denote the target node in an edge table.

Returns:
the data field used to denote the target node in an edge table.

getKey

public long getKey(int node)
Given a node id (a row number in the node table), get the value of the node key field.

Parameters:
node - the node id
Returns:
the value of the node key field for the given node

getNodeIndex

public int getNodeIndex(long key)
Given a value of the node key field, get the node id (the row number in the node table).

Parameters:
key - a node key field value
Returns:
the node id (the row number in the node table)

addNodeRow

public int addNodeRow()
Add row to the node table, thereby adding a node to the graph.

Returns:
the node id (node table row number) of the added node

addNode

public Node addNode()
Add a new node to the graph.

Returns:
the new Node instance

addEdge

public int addEdge(int s,
                   int t)
Add an edge to the graph. Both multiple edges between two nodes and edges from a node to itself are allowed.

Parameters:
s - the source node id
t - the target node id
Returns:
the edge id (edge table row number) of the added edge

addEdge

public Edge addEdge(Node s,
                    Node t)
Add an edge to the graph.

Parameters:
s - the source Node
t - the target Node
Returns:
the new Edge instance

removeNode

public boolean removeNode(int node)
Remove a node from the graph, also removing all incident edges.

Parameters:
node - the node id (node table row number) of the node to remove
Returns:
true if the node was successfully removed, false if the node id was not found or was not valid

removeNode

public boolean removeNode(Node n)
Remove a node from the graph, also removing all incident edges.

Parameters:
n - the Node to remove from the graph
Returns:
true if the node was successfully removed, false if the node was not found in this graph

removeEdge

public boolean removeEdge(int edge)
Remove an edge from the graph.

Parameters:
edge - the edge id (edge table row number) of the edge to remove
Returns:
true if the edge was successfully removed, false if the edge was not found or was not valid

removeEdge

public boolean removeEdge(Edge e)
Remove an edge from the graph.

Parameters:
e - the Edge to remove from the graph
Returns:
true if the edge was successfully removed, false if the edge was not found in this graph

clearEdges

protected void clearEdges()
Internal method for clearing the edge table, removing all edges.


nodeCheck

protected boolean nodeCheck(Node n,
                            boolean throwException)
Internal method for checking the validity of a node.

Parameters:
n - the Node to check for validity
throwException - true if this method should throw an Exception when an invalid node is encountered
Returns:
true is the node is valid, false if invalid

getNodes

public TupleSet getNodes()
Get the collection of nodes as a TupleSet. Returns the same result as CompositeTupleSet.getSet(String) using NODES as the parameter.

Returns:
the nodes of this graph as a TupleSet instance

getNodeTable

public Table getNodeTable()
Get the backing node table.

Returns:
the table of node values

getNodeCount

public int getNodeCount()
Get the number of nodes in this graph.

Returns:
the number of nodes

getNode

public Node getNode(int n)
Get the Node tuple instance corresponding to a node id.

Parameters:
n - a node id (node table row number)
Returns:
the Node instance corresponding to the node id

getNodeFromKey

public Node getNodeFromKey(long key)
Get the Node tuple corresponding to the input node key field value. The node key field is used to find the node id (node table row number), which is then used to retrieve the Node tuple.

Parameters:
key - a node key field value
Returns:
the requested Node instance

getInDegree

public int getInDegree(int node)
Get the in-degree of a node, the number of edges for which the node is the target.

Parameters:
node - the node id (node table row number)
Returns:
the in-degree of the node

getInDegree

public int getInDegree(Node n)
Get the in-degree of a node, the number of edges for which the node is the target.

Parameters:
n - the Node instance
Returns:
the in-degree of the node

getOutDegree

public int getOutDegree(int node)
Get the out-degree of a node, the number of edges for which the node is the source.

Parameters:
node - the node id (node table row number)
Returns:
the out-degree of the node

getOutDegree

public int getOutDegree(Node n)
Get the out-degree of a node, the number of edges for which the node is the source.

Parameters:
n - the Node instance
Returns:
the out-degree of the node

getDegree

public int getDegree(int node)
Get the degree of a node, the number of edges for which a node is either the source or the target.

Parameters:
node - the node id (node table row number)
Returns:
the total degree of the node

getDegree

public int getDegree(Node n)
Get the degree of a node, the number of edges for which a node is either the source or the target.

Parameters:
n - the Node instance
Returns:
the total degree of the node

isDirected

public boolean isDirected()
Indicates if the edges of this graph are directed or undirected.

Returns:
true if directed edges, false if undirected edges

edgeCheck

protected boolean edgeCheck(Edge e,
                            boolean throwException)
Internal method for checking the validity of an edge.

Parameters:
e - the Edge to check for validity
throwException - true if this method should throw an Exception when an invalid node is encountered
Returns:
true is the edge is valid, false if invalid

getEdges

public TupleSet getEdges()
Get the collection of edges as a TupleSet. Returns the same result as CompositeTupleSet.getSet(String) using EDGES as the parameter.

Returns:
the edges of this graph as a TupleSet instance

getEdgeTable

public Table getEdgeTable()
Get the backing edge table.

Returns:
the table of edge values

getEdgeCount

public int getEdgeCount()
Get the number of edges in this graph.

Returns:
the number of edges

getEdge

public Edge getEdge(int e)
Get the Edge tuple instance corresponding to an edge id.

Parameters:
e - an edge id (edge table row number)
Returns:
the Node instance corresponding to the node id

getEdge

public int getEdge(int source,
                   int target)
Returns an edge from the source node to the target node. This method returns the first such edge found; in the case of multiple edges there may be more.


getEdge

public Edge getEdge(Node source,
                    Node target)
Get an Edge with given source and target Nodes. There may be times where there are multiple edges between two nodes; in those cases this method returns the first such edge found.

Parameters:
source - the source Node
target - the target Node
Returns:
an Edge with given source and target nodes, or null if no such edge is found.

getSourceNode

public int getSourceNode(int edge)
Get the source node id (node table row number) for the given edge id (edge table row number).

Parameters:
edge - an edge id (edge table row number)
Returns:
the source node id (node table row number)

getSourceNode

public Node getSourceNode(Edge e)
Get the source Node for the given Edge instance.

Parameters:
e - an Edge instance
Returns:
the source Node of the edge

getTargetNode

public int getTargetNode(int edge)
Get the target node id (node table row number) for the given edge id (edge table row number).

Parameters:
edge - an edge id (edge table row number)
Returns:
the target node id (node table row number)

getTargetNode

public Node getTargetNode(Edge e)
Get the target Node for the given Edge instance.

Parameters:
e - an Edge instance
Returns:
the target Node of the edge

getAdjacentNode

public int getAdjacentNode(int edge,
                           int node)
Given an edge id and an incident node id, return the node id for the other node connected to the edge.

Parameters:
edge - an edge id (edge table row number)
node - a node id (node table row number). This node id must be connected to the edge
Returns:
the adjacent node id

getAdjacentNode

public Node getAdjacentNode(Edge e,
                            Node n)
Given an Edge and an incident Node, return the other Node connected to the edge.

Parameters:
e - an Edge instance
n - a Node instance. This node must be connected to the edge
Returns:
the adjacent Node

nodeRows

public IntIterator nodeRows()
Get an iterator over all node ids (node table row numbers).

Returns:
an iterator over all node ids (node table row numbers)

edgeRows

public IntIterator edgeRows()
Get an iterator over all edge ids (edge table row numbers).

Returns:
an iterator over all edge ids (edge table row numbers)

edgeRows

public IntIterator edgeRows(int node)
Get an iterator over all edge ids for edges incident on the given node.

Parameters:
node - a node id (node table row number)
Returns:
an iterator over all edge ids for edges incident on the given node

edgeRows

public IntIterator edgeRows(int node,
                            int direction)
Get an iterator edge ids for edges incident on the given node.

Parameters:
node - a node id (node table row number)
direction - the directionality of the edges to include. One of INEDGES (for in-linking edges), OUTEDGES (for out-linking edges), or UNDIRECTED (for all edges).
Returns:
an iterator over all edge ids for edges incident on the given node

inEdgeRows

public IntIterator inEdgeRows(int node)
Get an iterator over all edges that have the given node as a target. That is, edges that link into the given target node.

Parameters:
node - a node id (node table row number)
Returns:
an iterator over all edges that have the given node as a target

outEdgeRows

public IntIterator outEdgeRows(int node)
Get an iterator over all edges that have the given node as a source. That is, edges that link out from the given source node.

Parameters:
node - a node id (node table row number)
Returns:
an iterator over all edges that have the given node as a source

nodes

public java.util.Iterator nodes()
Get an iterator over all nodes in the graph.

Returns:
an iterator over Node instances

neighbors

public java.util.Iterator neighbors(Node n)
Get an iterator over all neighbor nodes for the given Node in the graph.

Parameters:
n - a Node in the graph
Returns:
an iterator over all Nodes connected to the input node

inNeighbors

public java.util.Iterator inNeighbors(Node n)
Get an iterator over all in-linking neighbor nodes for the given Node.

Parameters:
n - a Node in the graph
Returns:
an iterator over all Nodes that point to the input target node

outNeighbors

public java.util.Iterator outNeighbors(Node n)
Get an iterator over all out-linking neighbor nodes for the given Node.

Parameters:
n - a Node in the graph
Returns:
an iterator over all Nodes pointed to by the input source node

edges

public java.util.Iterator edges()
Get an iterator over all edges in the graph.

Returns:
an iterator over Edge instances

edges

public java.util.Iterator edges(Node node)
Get an iterator over all Edges connected to the given Node in the graph.

Parameters:
node - a Node in the graph
Returns:
an iterator over all Edges connected to the input node

inEdges

public java.util.Iterator inEdges(Node node)
Get an iterator over all in-linking edges to the given Node.

Parameters:
node - a Node in the graph
Returns:
an iterator over all in-linking edges to the input target node

outEdges

public java.util.Iterator outEdges(Node node)
Get an iterator over all out-linking edges from the given Node.

Parameters:
node - a Node in the graph
Returns:
an iterator over all out-linking edges from the input source node

clear

public void clear()
Clear this graph, removing all nodes and edges.

Specified by:
clear in interface TupleSet
Overrides:
clear in class CompositeTupleSet
See Also:
TupleSet.clear()

removeTuple

public boolean removeTuple(Tuple t)
If the given tuple is a Node or Edge in this graph, remove it.

Specified by:
removeTuple in interface TupleSet
Overrides:
removeTuple in class CompositeTupleSet
Parameters:
t - the Tuple to remove
Returns:
true if the Tuple was found and removed, false otherwise
See Also:
TupleSet.removeTuple(prefuse.data.Tuple)

tuples

public java.util.Iterator tuples(Predicate filter)
Get a filtered iterator over the edges and nodes of this graph.

Specified by:
tuples in interface TupleSet
Overrides:
tuples in class CompositeTupleSet
Parameters:
filter - predicate to apply to tuples in this set, only tuples for which the predicate evaluates to true are included in the iteration
Returns:
a filtered iterator over this set's tuples
See Also:
TupleSet.tuples(prefuse.data.expression.Predicate)

tuples

public java.util.Iterator tuples()
Get an iterator over all the edges and nodes of this graph. The iterator will return all edges first, then all nodes.

Specified by:
tuples in interface TupleSet
Overrides:
tuples in class CompositeTupleSet
Returns:
an iterator over this set's tuples
See Also:
TupleSet.tuples()

getSpanningTree

public Tree getSpanningTree()
Return the current spanning tree over this graph. If no spanning tree has been constructed, a SpanningTree rooted at the first valid node found in the node table will be generated. Spanning trees are generated using an unweighted breadth first search over the graph structure.

Returns:
a spanning tree over this graph
See Also:
getSpanningTree(Node), clearSpanningTree()

getSpanningTree

public Tree getSpanningTree(Node root)
Returns a spanning tree rooted at the specified node. If the current spanning tree is alrady rooted at the given node, it is simply returned. Otherwise, the tree is reconstructed at the new root and made the current spanning tree for this Graph instance. Spanning trees are generated using an unweighted breadth first search over the graph structure.

Parameters:
root - the node at which to root the spanning tree.
Returns:
a spanning tree over this graph, rooted at the given root
See Also:
getSpanningTree(), clearSpanningTree()

clearSpanningTree

public void clearSpanningTree()
Clear the internally stored spanning tree. Any new calls to a getSpanningTree() method will generate a new spanning tree instance as needed. This method is primarily useful for subclasses. For example, calling this method on a Tree instance will revert the state to the original rooted tree such that a sbusequent call to getSpanningTree() will return the backing Tree itself.

See Also:
getSpanningTree(), getSpanningTree(Node), Tree.getSpanningTree(Node)

addGraphModelListener

public void addGraphModelListener(GraphListener listnr)
Add a listener to be notified of changes to the graph.

Parameters:
listnr - the listener to add

removeGraphModelListener

public void removeGraphModelListener(GraphListener listnr)
Remove a listener from this graph.

Parameters:
listnr - the listener to remove

removeAllGraphModelListeners

public void removeAllGraphModelListeners()
Removes all listeners on this graph


fireGraphEvent

protected void fireGraphEvent(Table t,
                              int first,
                              int last,
                              int col,
                              int type)
Fire a graph change event

Parameters:
t - the backing table where the change occurred (either a node table or an edge table)
first - the first modified table row
last - the last (inclusive) modified table row
col - the number of the column modified, or EventConstants.ALL_COLUMNS for operations affecting all columns
type - the type of modification, one of EventConstants.INSERT, EventConstants.DELETE, or EventConstants.UPDATE.


Copyright 2007 Regents of the University of California