prefuse.data
Class Graph

java.lang.Object
  prefuse.data.tuple.AbstractTupleSet
      prefuse.data.tuple.CompositeTupleSet
          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.