H3Graph.java

// 
// The Walrus Graph Visualization Tool.
// Copyright (C) 2000,2001,2002 The Regents of the University of California.
// 
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// 
// ######END_HEADER######
// 


import java.util.*;
import javax.vecmath.*;

//
// This is the graph representation used and needed by the rendering part
// of Walrus.
// 
// Walrus traverses this graph while rendering the display.  Hence, the
// main requirement on the design of this class is fast read access.
// Also, nothing more need be stored in this class than the bare graph
// topology, coloring information, and coordinates; all other data (such
// as attributes associated with nodes and links) should be stored in a
// backing graph.  Because of these design goals, this class is minimal
// in implementation.
// 
// An additional design goal is the ability to handle large graphs.
// Because there will usually be a backing graph from which this class is
// populated, we want the overhead of construction to be as small as
// possible.  In particular, we want to eliminate the need for
// intermediate data structures during construction.  This goal is
// accomplished by requiring the user to populate links in a disciplined
// manner.  Specifically, links must be populated in batches, with all
// the links of each node populated in a consecutive sequence of
// operations.  That is, rather than allowing the user to add the links
// of all nodes in an arbitrary order, users must add all the links of
// some node A with a sequence of calls, and then all the links of some
// node B, and so on.  The ordering of the nodes themselves, however,
// doesn't matter.
// 
// This ordering requirement lets this class store a graph in a very
// compact way (as a set of parallel primitive arrays) without
// necessitating the use of an intermediate representation, which would
// raise the peak memory usage during graph construction---some graphs
// can take up more than 100 MBs of memory, so eliminating unnecessary
// data structures really is important.
// 
// So, the basic steps the user would take to create and populate an
// H3Graph is as follows, in pseudo-code:
// 
//        Create an H3Graph instance.
//        Iterate over the nodes in the user's data set [backing graph]:
//             If the node has outgoing links:
//                 Call startChildLinks().
//                 For each child link [tree link] (can be zero):
//                     Call addChildLink().
//                 Call startNontreeLinks().
//                 For each nontree link (can be zero):
//                     Call addNontreeLink().
//                 Call endNodeLinks().
// 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// 
// This class refers to nodes and links using internally defined indices.
// Suppose you create an instance with the following:
// 
//     H3Graph graph = new H3Graph(numNodes, numLinks);
// 
// Then, as far as H3Graph is concerned, the nodes are identified with
// the indices 0, ..., numNodes-1, and links with 0, ..., numLinks-1.
// The actual correspondence between these indices and the nodes and
// links in the user's data set (backing graph) is entirely up to the
// user; all that matters to H3Graph is that the user always handles the
// correspondences consistently.  To help the user maintain the
// correspondences, H3Graph can associate an external ID number with each
// node or link.  This facility is provided through the methods
// {get,set}NodeID() and {get,set}LinkID().  Also, addChildLink() and
// addNontreeLink() take a parameter containing the external ID of the
// link being added.  In summary, to use H3Graph, users must have some
// way of mapping between their set of nodes and links and the IDs known
// by H3Graph.
// 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// 
// Be sure to call setRootNode() at some point during construction so
// that the rendering part of Walrus (and any other users of this data)
// knows at which node to start its traversal.
// 

public class H3Graph
{
    ////////////////////////////////////////////////////////////////////////
    // CONSTRUCTORS
    ////////////////////////////////////////////////////////////////////////

    public H3Graph(int numNodes, int numLinks)
    {
	// PRECONDITION: numNodes >= 0
	// PRECONDITION: numLinks >= 0

	m_numNodes = numNodes;
	m_numLinks = numLinks;

	m_nodes = new Nodes(numNodes);
	m_links = new Links(numLinks);
    }

    ////////////////////////////////////////////////////////////////////////
    // PUBLIC ACCESSOR METHODS
    ////////////////////////////////////////////////////////////////////////

    public int getNumNodes()
    {
	return m_numNodes;
    }

    public int getNumTreeLinks()
    {
	return m_numTreeLinks;
    }

    public int getNumNontreeLinks()
    {
	return m_numNontreeLinks;
    }

    public int getTotalNumLinks()
    {
	return m_numLinks;
    }

    public int getRootNode()
    {
	return m_rootNode;
    }

    public int getNodeID(int node)
    {
	return m_nodes.id[node];
    }

    public double getNodeRadius(int node)
    {
	return m_nodes.radius[node];
    }

    public void getNodeCoordinates(int node, Point3d point)
    {
	point.x = m_nodes.x[node];
	point.y = m_nodes.y[node];
	point.z = m_nodes.z[node];
    }

    public void getNodeCoordinates(int node, Point4d point)
    {
	point.x = m_nodes.x[node];
	point.y = m_nodes.y[node];
	point.z = m_nodes.z[node];
	point.w = 1.0;
    }

    public void getNodeLayoutCoordinates(int node, Point3d point)
    {
	double w = m_nodes.layoutW[node];
	point.x = m_nodes.layoutX[node] / w;
	point.y = m_nodes.layoutY[node] / w;
	point.z = m_nodes.layoutZ[node] / w;
    }

    public void getNodeLayoutCoordinates(int node, Point4d point)
    {
	point.x = m_nodes.layoutX[node];
	point.y = m_nodes.layoutY[node];
	point.z = m_nodes.layoutZ[node];
	point.w = m_nodes.layoutW[node];
    }

    public int getNodeParent(int node)
    {
	int i = m_nodes.parent[node];
	return (i == -1 ? -1 : m_links.source[i]);
    }

    public int getNodeParentLink(int node)
    {
	return m_nodes.parent[node];
    }

    public int getNodeNumChildren(int node)
    {
	return getNodeLinksEndIndex(node) - getNodeChildIndex(node);
    }

    // The following methods--getNodeChildIndex(), getNodeNontreeIndex(),
    // and getNodeLinksEndIndex()--provide a way of iterating over all
    // the outgoing links of a node.
    //
    // You would iterate over the outgoing links in the following manner:
    //
    //     int start = graph.getNodeChildIndex(node);
    //     int end = graph.getNodeLinksEndIndex(node);
    //     int nontreeStart = graph.getNodeNontreeIndex(node);
    //
    //     for (int i = start; i < nontreeStart; i++)
    //     {
    //        /* i is the index of an outgoing child link */
    //        graph.setLinkColor(i, Color.black);
    //        /* ... */
    //     }
    //
    //     for (int i = nontreeStart; i < end; i++)
    //     {
    //        /* i is the index of an outgoing nontree link */
    //     }

    public int getNodeChildIndex(int node)
    {
	return m_nodes.treeLinks[node];
    }

    public int getNodeNontreeIndex(int node)
    {
	return m_nodes.nontreeLinks[node];
    }

    public int getNodeLinksEndIndex(int node)
    {
	return m_nodes.linksEnd[node];
    }

    public int getNodeColor(int node)
    {
	return m_nodes.color[node];
    }

    // Returns true iff all nodes are visible.
    public boolean checkNodesVisible()
    {
	return m_nodes.isVisible.check();
    }

    public boolean checkNodeVisible(int node)
    {
	return m_nodes.isVisible.check(node);
    }

    public boolean checkNodeDisplayable(int node)
    {
	return m_nodes.isDisplayable.check(node);
    }

    public boolean checkNodeSelected(int node)
    {
	return m_nodes.isSelected.check(node);
    }

    //======================================================================

    public int getLinkID(int link)
    {
	return m_links.id[link];
    }

    public int getLinkSource(int link)
    {
	return m_links.source[link];
    }

    public int getLinkDestination(int link)
    {
	return m_links.destination[link];
    }

    public int getLinkColor(int link)
    {
	return m_links.color[link];
    }

    public boolean checkTreeLink(int link)
    {
	return m_links.isTreeLink.get(link);
    }

    // Returns true iff all links are visible.
    public boolean checkLinksVisible()
    {
	return m_links.isVisible.check();
    }

    public boolean checkLinkVisible(int link)
    {
	return m_links.isVisible.check(link);
    }

    public boolean checkLinkDisplayable(int link)
    {
	return m_links.isDisplayable.check(link);
    }

    public boolean checkLinkSelected(int link)
    {
	return m_links.isSelected.check(link);
    }

    ////////////////////////////////////////////////////////////////////////
    // PUBLIC MUTATOR METHODS
    ////////////////////////////////////////////////////////////////////////

    // Computes new display coordinates for each node by transforming the
    // layout coordinates of nodes with the supplied matrix.
    public void transformNodes(Matrix4d t)
    {
	Point4d p = new Point4d();
	for (int i = 0; i < m_numNodes; i++)
	{
	    p.x = m_nodes.layoutX[i];
	    p.y = m_nodes.layoutY[i];
	    p.z = m_nodes.layoutZ[i];
	    p.w = m_nodes.layoutW[i];

	    t.transform(p);

	    m_nodes.x[i] = p.x / p.w;
	    m_nodes.y[i] = p.y / p.w;
	    m_nodes.z[i] = p.z / p.w;
	}
    }

    public void setRootNode(int node)
    {
	m_nodes.parent[node] = -1;
	m_rootNode = node;
    }

    public void setNodeID(int node, int id)
    {
	m_nodes.id[node] = id;
    }

    public void setNodeRadius(int node, double radius)
    {
	m_nodes.radius[node] = radius;
    }

    public void setNodeCoordinates(int node, double x, double y, double z)
    {
	m_nodes.x[node] = x;
	m_nodes.y[node] = y;
	m_nodes.z[node] = z;
    }

    public void setNodeCoordinates(int node, Point3d p)
    {
	m_nodes.x[node] = p.x;
	m_nodes.y[node] = p.y;
	m_nodes.z[node] = p.z;
    }

    public void setNodeCoordinates(int node, Point4d p)
    {
	m_nodes.x[node] = p.x / p.w;
	m_nodes.y[node] = p.y / p.w;
	m_nodes.z[node] = p.z / p.w;
    }

    public void setNodeLayoutCoordinates(int node, double x, double y,
					 double z, double w)
    {
	m_nodes.layoutX[node] = x;
	m_nodes.layoutY[node] = y;
	m_nodes.layoutZ[node] = z;
	m_nodes.layoutW[node] = w;
    }

    public void setNodeLayoutCoordinates(int node, Point3d p)
    {
	m_nodes.layoutX[node] = p.x;
	m_nodes.layoutY[node] = p.y;
	m_nodes.layoutZ[node] = p.z;
	m_nodes.layoutW[node] = 1.0;
    }

    public void setNodeLayoutCoordinates(int node, Point4d p)
    {
	m_nodes.layoutX[node] = p.x;
	m_nodes.layoutY[node] = p.y;
	m_nodes.layoutZ[node] = p.z;
	m_nodes.layoutW[node] = p.w;
    }

    // The following two methods, addChildLink() and addNodeNontreeLink(),
    // must be called in a disciplined manner.  The sequence of calls to
    // add the links of one node should never interleave with the sequence
    // of another node.  Additionally, for a particular node, all child links
    // must be added first, followed by all non-tree links.
    // 
    // The required calling sequence for a node is as follows:
    //
    //    startChildLinks()
    //    addChildLink() ... addChildLink()  [zero or more times]
    //    startNontreeLinks()
    //    addNontreeLink() ... addNontreeLink()  [zero or more times]
    //    endNodeLinks()
    //
    // There need not be a sequence of these calls for nodes without any links.

    public void startChildLinks(int node)
    {
	m_nodes.treeLinks[node] = m_links.nextIndex;
    }

    // linkID is the ID of the corresponding link in the backing libsea graph
    // (or whatever backing data store you're using).
    public void addChildLink(int node, int child, int linkID)
    {
	++m_numTreeLinks;

	int link = m_links.nextIndex++;
	m_nodes.parent[child] = link;
	m_links.id[link] = linkID;
	m_links.source[link] = node;
	m_links.destination[link] = child;
	m_links.isTreeLink.set(link);
    }

    public void startNontreeLinks(int node)
    {
	m_nodes.nontreeLinks[node] = m_links.nextIndex;
    }

    // linkID is the ID of the corresponding link in the backing libsea graph
    // (or whatever backing data store you're using).
    public void addNontreeLink(int node, int target, int linkID)
    {
	++m_numNontreeLinks;

	int link = m_links.nextIndex++;
	m_links.id[link] = linkID;
	m_links.source[link] = node;
	m_links.destination[link] = target;
    }

    public void endNodeLinks(int node)
    {
	m_nodes.linksEnd[node] = m_links.nextIndex;
    }

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    public void setNodeColor(int node, int color)
    {
	m_nodes.color[node] = color;
    }

    public void setNodeColor(int node, byte r, byte g, byte b)
    {
	m_nodes.color[node] = (r << 16) | (g << 8) | b;
    }

    public void setNodeDefaultColor(int color)
    {
	Arrays.fill(m_nodes.color, color);
    }

    public void setNodeDefaultColor(byte r, byte g, byte b)
    {
	int color = (r << 16) | (g << 8) | b;
	setNodeDefaultColor(color);
    }

    public void setNodeVisibility(int node, boolean isVisible)
    {
	m_nodes.isVisible.set(node, isVisible);
    }

    public void setNodeDisplayability(int node, boolean isDisplayable)
    {
	m_nodes.isDisplayable.set(node, isDisplayable);
    }

    public void setNodeSelectivity(int node, boolean isSelected)
    {
	m_nodes.isSelected.set(node, isSelected);
    }

    public void setNodeVisibility(boolean isVisible)
    {
	m_nodes.isVisible.set(isVisible);
    }

    public void setNodeDisplayability(boolean isDisplayable)
    {
	m_nodes.isDisplayable.set(isDisplayable);
    }

    public void setNodeSelectivity(boolean isSelected)
    {
	m_nodes.isSelected.set(isSelected);
    }

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    public void setLinkID(int link, int id)
    {
	m_links.id[link] = id;
    }

    public void setLinkColor(int link, int color)
    {
	m_links.color[link] = color;
    }

    public void setLinkColor(int link, byte r, byte g, byte b)
    {
	m_links.color[link] = (r << 16) | (g << 8) | b;
    }

    public void setLinkDefaultColor(int color)
    {
	Arrays.fill(m_links.color, color);
    }

    public void setLinkDefaultColor(byte r, byte g, byte b)
    {
	int color = (r << 16) | (g << 8) | b;
	setLinkDefaultColor(color);
    }

    public void setLinkVisibility(int link, boolean isVisible)
    {
	m_links.isVisible.set(link, isVisible);
    }

    public void setLinkDisplayability(int link, boolean isDisplayable)
    {
	m_links.isDisplayable.set(link, isDisplayable);
    }

    public void setLinkSelectivity(int link, boolean isSelected)
    {
	m_links.isSelected.set(link, isSelected);
    }

    public void setLinkVisibility(boolean isVisible)
    {
	m_links.isVisible.set(isVisible);
    }

    public void setLinkVisibility(boolean treeLink, boolean isVisible)
    {
	m_links.isVisible.set(treeLink, isVisible);
    }

    public void setLinkDisplayability(boolean isDisplayable)
    {
	m_links.isDisplayable.set(isDisplayable);
    }

    public void setLinkDisplayability(boolean treeLink, boolean isDisplayable)
    {
	m_links.isDisplayable.set(treeLink, isDisplayable);
    }

    public void setLinkSelectivity(boolean isSelected)
    {
	m_links.isSelected.set(isSelected);
    }

    public void setLinkSelectivity(boolean treeLink, boolean isSelected)
    {
	m_links.isVisible.set(treeLink, isSelected);
    }

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    public void pruneSubtreeVisibility(int node)
    {
	if (getNodeParent(node) != -1)
	{
	    setLinkDisplayability(getNodeParentLink(node), false);
	}
	setNodeDisplayability(node, false);
	setSubtreeDisplayability(node, false);
	computeVisibility();
    }

    public void pruneVisibilityToNeighborhood(int node, int distance)
    {
	setNeighborhoodDisplayability(node, 0, distance);
	computeVisibility();
    }

    public void narrowVisibility(int node)
    {
	setNodeDisplayability(false);
	setLinkDisplayability(false);

	setNodeDisplayability(node, true);

	// Show nodes & links up to root node from input node.
	int currentNode = node;
	int parent = getNodeParent(currentNode);
	while (parent != -1)
	{
	    int link = getNodeParentLink(currentNode);
	    setLinkDisplayability(link, true);
	    setNodeDisplayability(parent, true);

	    int old = parent;
	    currentNode = parent;
	    parent = getNodeParent(parent);
	}

	setSubtreeDisplayability(node, true);
	computeVisibility();
    }

    public void widenSubtreeVisibility(int node)
    {
	setNodeDisplayability(node, true);
	setSubtreeDisplayability(node, true);
	computeVisibility();
    }

    // Widen visibility to the first ancestor of the given node that
    // has more than one child--that is, to the closest branching point
    // in the path back to the root node.
    //
    // Returns the node to which visibility was widened.
    public int widenVisibilityTowardRoot(int node)
    {
	int currentNode = node;
	int parent = getNodeParent(currentNode);
	boolean found = false;
	while (!found && parent != -1)
	{
	    if (getNodeNumChildren(parent) > 1)
	    {
		found = true;
	    }

	    currentNode = parent;
	    parent = getNodeParent(parent);
	}

	setSubtreeDisplayability(currentNode, true);
	computeVisibility();

	return currentNode;
    }

    // Show all nodes and links, modified only by selectivity.
    public void widenVisibility()
    {
	setNodeDisplayability(true);
	setLinkDisplayability(true);
	computeVisibility();
    }

    public void computeVisibility()
    {
	m_nodes.isVisible.conjunction
	    (m_nodes.isDisplayable, m_nodes.isSelected);

	computeNontreeLinkDisplayability();

	m_links.isVisible.conjunction
	    (m_links.isDisplayable, m_links.isSelected);
    }

    ////////////////////////////////////////////////////////////////////////
    // PRIVATE METHODS
    ////////////////////////////////////////////////////////////////////////

    // Assumes m_nodes.isVisible has been computed from m_nodes.isDisplayable
    // and m_nodes.isSelected.  This adjusts m_links.isDisplayable but neither
    // m_links.isSelected nor m_links.isVisible.  Thus, m_links.isVisible
    // must be computed sometime after calling this method.
    private void computeNontreeLinkDisplayability()
    {
	int node = 0;
	int numNontreeLinksSeen = 0;
	while (numNontreeLinksSeen < m_numNontreeLinks)
	{
	    int nontreeStart = getNodeNontreeIndex(node);
	    int end = getNodeLinksEndIndex(node);

	    if (nontreeStart != end)
	    {
		numNontreeLinksSeen += end - nontreeStart;
		if (checkNodeVisible(node))
		{
		    for (int i = nontreeStart; i < end; i++)
		    {
			int destination = getLinkDestination(i);
			boolean isDisplayable = checkNodeVisible(destination);
			setLinkDisplayability(i, isDisplayable);
		    }
		}
		else
		{
		    for (int i = nontreeStart; i < end; i++)
		    {
			setLinkDisplayability(i, false);
		    }
		}
	    }

	    ++node;
	}
    }

    // The input node itself is assumed to have been taken care of.
    private void setSubtreeDisplayability(int node, boolean isDisplayable)
    {
	int start = getNodeChildIndex(node);
	int end = getNodeLinksEndIndex(node);
	int nontreeStart = getNodeNontreeIndex(node);
    
	for (int i = start; i < nontreeStart; i++)
	{
	    int child = getLinkDestination(i);
            setNodeDisplayability(child, isDisplayable);
            setLinkDisplayability(i, isDisplayable);
	    setSubtreeDisplayability(child, isDisplayable);
	}
    }

    // The input node itself is assumed to have been taken care of.
    private void setNeighborhoodDisplayability
	(int node, int distance, int maxDistance)
    {
	boolean isDisplayable = (distance < maxDistance);

	int start = getNodeChildIndex(node);
	int end = getNodeLinksEndIndex(node);
	int nontreeStart = getNodeNontreeIndex(node);
    
	for (int i = start; i < nontreeStart; i++)
	{
	    int child = getLinkDestination(i);
	    setNodeDisplayability(child, isDisplayable);
	    setLinkDisplayability(i, isDisplayable);
	    setNeighborhoodDisplayability(child, distance + 1, maxDistance);
	}
    }

    ////////////////////////////////////////////////////////////////////////
    // PRIVATE FIELDS
    ////////////////////////////////////////////////////////////////////////

    private int m_numNodes;
    private int m_numLinks;

    private int m_numTreeLinks = 0;
    private int m_numNontreeLinks = 0;

    private int m_rootNode = 0;
    private Nodes m_nodes;
    private Links m_links;

    ////////////////////////////////////////////////////////////////////////
    // PRIVATE CLASSES
    ////////////////////////////////////////////////////////////////////////

    private static class Nodes
    {
	public Nodes(int numNodes)
	{
	    id = new int[numNodes];
	    radius = new double[numNodes];
	    x = new double[numNodes];
	    y = new double[numNodes];
	    z = new double[numNodes];
	    layoutX = new double[numNodes];
	    layoutY = new double[numNodes];
	    layoutZ = new double[numNodes];
	    layoutW = new double[numNodes];
	    parent = new int[numNodes];

	    // The automatic initialization of these arrays to zero is
	    // important in giving consistent values for nodes without
	    // child or non-tree links (e.g., when startChildLinks() et al.
	    // are not called for them).
	    treeLinks = new int[numNodes];
	    nontreeLinks = new int[numNodes];
	    linksEnd = new int[numNodes];

	    color = new int[numNodes];
	    isVisible = new NodeProperty(numNodes);
	    isDisplayable = new NodeProperty(numNodes);
	    isSelected = new NodeProperty(numNodes);
	}

	////////////////////////////////////////////////////////////////////
	// ESSENTIAL NODE ATTRIBUTES
	////////////////////////////////////////////////////////////////////

	// The ID of the node in the backing org.caida.libsea.Graph.
	// This mapping is necessary since the IDs in the backing graph
	// need not form a contiguous block starting at zero.
	public int[] id;

	// The radius of the nodes as determined solely by their position.
	// This is inversely proportional to the distance from the origin to
	// a node as determined with the hyperbolic metric.
	public double[] radius;

	// The coordinates of nodes after hyperbolic view transformation.
	public double[] x;
	public double[] y;
	public double[] z;

	// The coordinates of nodes in initial layout.
	public double[] layoutX;
	public double[] layoutY;
	public double[] layoutZ;
	public double[] layoutW;

	// The parent value of a node gives the index of the link that
	// connects the parent to that node.  Hence the source of the parent
	// link gives the parent node and the destination gives the child node.
	// The root node of the graph has a parent link value of -1.
	public int[] parent;

	// The following arrays give indices into the array of links where
	// the links of a node appear.  All the links of a node appear in
	// a continguous block, with all child links grouped at the beginning
	// and all non-tree links at the end.  For a node i, the values have
	// the following relationship:
	//
	//  0 <= treeLinks[i] <= nontreeLinks[i] <= linksEnd[i] <= m_numLinks
	//
	// Additionally,
	//
	//   nontreeLinks[i] - treeLinks[i] gives the number of child links,
	//   linksEnd[i] - nontreeLinks[i] gives the number of non-tree links,
	// and linksEnd[i] - treeLinks[i] gives the total number of links.
	//
	// If a node has no links, then all the values will equal some
	// arbitrary value.
	public int[] treeLinks;
	public int[] nontreeLinks;
	public int[] linksEnd;

	////////////////////////////////////////////////////////////////////
	// INESSENTIAL NODE ATTRIBUTES
	////////////////////////////////////////////////////////////////////

	// Color in packed RGB format (R, G, and B in the lower three octets).
	public int[] color;

	// Whether a node should be drawn.
	// This is usually the logical AND of isDisplayable and isSelected.
	public NodeProperty isVisible;

	// Whether a node is displayable (that is, potentially visible,
	// depending on isSelected).
	public NodeProperty isDisplayable;

	// Whether a node has been chosen by a selection attribute for display.
	public NodeProperty isSelected;
    }

    ////////////////////////////////////////////////////////////////////////

    public static class Links
    {
	public Links(int numLinks)
	{
	    id = new int[numLinks];
	    source = new int[numLinks];
	    destination = new int[numLinks];
	    isTreeLink = new BitSet(numLinks);
	    color = new int[numLinks];
	    isVisible = new LinkProperty(numLinks, isTreeLink);
	    isDisplayable = new LinkProperty(numLinks, isTreeLink);
	    isSelected = new LinkProperty(numLinks, isTreeLink);
	}

	public int nextIndex = 0;

	////////////////////////////////////////////////////////////////////
	// ESSENTIAL LINK ATTRIBUTES
	////////////////////////////////////////////////////////////////////

	// The ID of the link in the backing org.caida.libsea.Graph.
	// This mapping is necessary since the IDs in the backing graph
	// need not form a contiguous block starting at zero.
	public int[] id;

	// The indices of nodes.
	public int[] source;
	public int[] destination;

	// Whether a link is a tree link or a nontree link.
	public BitSet isTreeLink;

	////////////////////////////////////////////////////////////////////
	// INESSENTIAL LINK ATTRIBUTES
	////////////////////////////////////////////////////////////////////

	// Color in packed RGB format (R, G, and B in the lower three octets).
	public int[] color;

	// Whether a link should be drawn.
	// This is usually the logical AND of isDisplayable and isSelected.
	public LinkProperty isVisible;

	// Whether a link is displayable (that is, potentially visible,
	// depending on isSelected).
	public LinkProperty isDisplayable;

	// Whether a link has been chosen by a selection attribute for display.
	public LinkProperty isSelected;
    }

    ////////////////////////////////////////////////////////////////////////

    // This implementation uses inverted logic because BitSet is created
    // with all its bits cleared.
    private static final class NodeProperty
    {
	public NodeProperty(int numNodes)
	{
	    m_numNodes = numNodes;
	}

	public int count()
	{
	    int retval = m_numNodes;
	    if (m_property != null)
	    {
		int length = m_property.length();
		for (int i = 0; i < length; i++)
		{
		    if (m_property.get(i))
		    {
			--retval;
		    }
		}
	    }
	    return retval;
	}

	// Returns true iff all nodes are visible.
	public boolean check()
	{
	    return (m_property == null || m_property.length() == 0);
	}

	public boolean check(int node)
	{
	    return (m_property == null || !m_property.get(node));
	}

	public void set(int node, boolean value)
	{
	    if (value)
	    {
		if (m_property != null)
		{
		    m_property.clear(node);
		}
	    }
	    else
	    {
		ensureAllocated();
		m_property.set(node);
	    }
	}

	// Set value for all nodes.
	public void set(boolean value)
	{
	    if (value)
	    {
		m_property = null;
	    }
	    else
	    {
		ensureAllocated();
		for (int i = 0; i < m_numNodes; i++)
		{
		    m_property.set(i);
		}
	    }
	}

	// Sets this to a logical AND of np1 and np2.
	// Because this implementation uses inverted logic, the logical
	// AND is carried out with a logical OR of the negated parameters
	// (that is, ~R = ~P | ~Q implies R = P & Q).
	public void conjunction(NodeProperty p1, NodeProperty p2)
	{
	    if (p1.m_property == null && p2.m_property == null)
	    {
		m_property = null;
	    }
	    else if (p1.m_property == null && p2.m_property != null)
	    {
		m_property = (BitSet)p2.m_property.clone();
	    }
	    else if (p1.m_property != null && p2.m_property == null)
	    {
		m_property = (BitSet)p1.m_property.clone();
	    }
	    else
	    {
		m_property = (BitSet)p1.m_property.clone();
		m_property.or(p2.m_property);
	    }
	}

	private void ensureAllocated()
	{
	    if (m_property == null)
	    {
		m_property = new BitSet(m_numNodes);
	    }
	}

	private int m_numNodes;
	private BitSet m_property;
    }

    ////////////////////////////////////////////////////////////////////////

    // This implementation uses inverted logic because BitSet is created
    // with all its bits cleared.
    private static final class LinkProperty
    {
	public LinkProperty(int numLinks, BitSet isTreeLink)
	{
	    m_numLinks = numLinks;
	    m_isTreeLink = isTreeLink;
	}

	public int count()
	{
	    int retval = m_numLinks;
	    if (m_property != null)
	    {
		int length = m_property.length();
		for (int i = 0; i < length; i++)
		{
		    if (m_property.get(i))
		    {
			--retval;
		    }
		}
	    }
	    return retval;
	}

	// Returns true iff all links are visible.
	public boolean check()
	{
	    return (m_property == null || m_property.length() == 0);
	}

	public boolean check(int link)
	{
	    return (m_property == null || !m_property.get(link));
	}

	public void set(int link, boolean value)
	{
	    if (value)
	    {
		if (m_property != null)
		{
		    m_property.clear(link);
		}
	    }
	    else
	    {
		ensureAllocated();
		m_property.set(link);
	    }
	}

	// Set value for all links.
	public void set(boolean value)
	{
	    if (value)
	    {
		m_property = null;
	    }
	    else
	    {
		ensureAllocated();
		for (int i = 0; i < m_numLinks; i++)
		{
		    m_property.set(i);
		}
	    }
	}

	// Set value for all links of the specified type.
	public void set(boolean treeLink, boolean value)
	{
	    if (value)
	    {
		if (m_property != null)
		{
		    setBits(treeLink, false);
		    if (m_property.length() == 0)
		    {
			m_property = null;
		    }
		}
	    }
	    else
	    {
		ensureAllocated();
		setBits(treeLink, true);
	    }
	}

	// Assumes m_property != null.
	private void setBits(boolean treeLink, boolean value)
	{
	    int length = m_property.length();
	    for (int i = 0; i < length; i++)
	    {
		if (m_isTreeLink.get(i) == treeLink)
		{
		    if (value)
		    {
			m_property.set(i);
		    }
		    else
		    {
			m_property.clear(i);
		    }
		}
	    }
	}

	// Sets this to a logical AND of np1 and np2.
	// Because this implementation uses inverted logic, the logical
	// AND is carried out with a logical OR of the negated parameters
	// (that is, ~R = ~P | ~Q implies R = P & Q).
	public void conjunction(LinkProperty p1, LinkProperty p2)
	{
	    if (p1.m_property == null && p2.m_property == null)
	    {
		m_property = null;
	    }
	    else if (p1.m_property == null && p2.m_property != null)
	    {
		m_property = (BitSet)p2.m_property.clone();
	    }
	    else if (p1.m_property != null && p2.m_property == null)
	    {
		m_property = (BitSet)p1.m_property.clone();
	    }
	    else
	    {
		m_property = (BitSet)p1.m_property.clone();
		m_property.or(p2.m_property);
	    }
	}

	private void ensureAllocated()
	{
	    if (m_property == null)
	    {
		m_property = new BitSet(m_numLinks);
	    }
	}

	private int m_numLinks;
	private BitSet m_isTreeLink;
	private BitSet m_property;
    }

    ////////////////////////////////////////////////////////////////////////
    // TEST METHODS
    ////////////////////////////////////////////////////////////////////////

    // Place nodes with invalid layout coordinates at the origin.
    public void sanitizeLayoutCoordinates()
    {
	Point4d p = new Point4d();
	for (int i = 0; i < m_numNodes; i++)
	{
	    getNodeLayoutCoordinates(i, p);
	    if (!H3Math.isFinite(p))
	    {
		setNodeLayoutCoordinates(i, 0.0, 0.0, 0.0, 1.0);
	    }
	}
    }

    // Returns the number of nodes with valid (not NaN or infinite) layout
    // coordinates.
    public int checkLayoutCoordinates()
    {
	int retval = 0;

	Point4d p = new Point4d();
	for (int i = 0; i < m_numNodes; i++)
	{
	    getNodeLayoutCoordinates(i, p);
	    if (H3Math.isFinite(p))
	    {
		++retval;
	    }
	}

	return retval;
    }

    ////////////////////////////////////////////////////////////////////////

    // Returns the number of nodes reachable in the spanning tree, or -1
    // if some node is visited more than once, indicating a cycle,
    // a parallel edge, or some other problem.  The set of tree links
    // is assumed to define a spanning tree.
    public int checkSpanningTree()
    {
	BitSet visited = new BitSet();
	return checkSpanningTree(visited, m_rootNode);
    }

    private int checkSpanningTree(BitSet visited, int node)
    {
	if (visited.get(node))
	{
	    return -1;
	}
	visited.set(node);

	int start = getNodeChildIndex(node);
	int nontreeStart = getNodeNontreeIndex(node);

	int retval = 1;
	for (int i = start; i < nontreeStart; i++)
	{
	    int child = getLinkDestination(i);
	    int numReachable = checkSpanningTree(visited, child);
	    if (numReachable == -1)
	    {
		return -1;
	    }
	    retval += numReachable;
	}

	return retval;
    }

    public int checkTreeReachability()
    {
	return checkTreeReachability(m_rootNode);
    }

    public int checkTreeReachability(int node)
    {
	BitSet visited = new BitSet();
	int numReachable = checkReachability(visited, node);
	if (numReachable == m_numNodes)
	{
	    String msg =
		"PASSED: All nodes reachable in tree from node " + node;
	    System.out.println(msg);
	}
	else
	{
	    String msg = "FAILED: Only " + numReachable
		+ " nodes of " + m_numNodes
		+ " reachable in tree from node " + node;
	    System.out.println(msg);

	    System.out.println("Unvisited nodes:");
	    for (int i = 0; i < m_numNodes; i++)
	    {
		if (!visited.get(i))
		{
		    System.out.println("\t" + i);
		}
	    }
	}

	return numReachable;
    }

    private int checkReachability(BitSet visited, int node)
    {
	int retval = 1;

	if (visited.get(node))
	{
	    String msg = "ERROR: Encountered node " + node
		+ " more than once in the spanning tree; there could be"
		+ " cycles or parallel links.";
	    System.out.println(msg);
	    return 0;
	}
	visited.set(node);

	int treeLinks = m_nodes.treeLinks[node];
	int nontreeLinks = m_nodes.nontreeLinks[node];

	while (treeLinks < nontreeLinks)
	{
	    int child = m_links.destination[treeLinks++];
	    retval += checkReachability(visited, child);
	}

	return retval;
    }

    public void dumpForTesting()
    {
	System.out.println();
	System.out.println(this + ":");
	System.out.println("\tnumNodes: " + m_numNodes);
	System.out.println("\tnumLinks: " + m_numLinks);
	System.out.println("\tnumTreeLinks: " + m_numTreeLinks);
	System.out.println("\tnumNontreeLinks: " + m_numNontreeLinks);
	System.out.println("\tnextIndex: " + m_links.nextIndex);
	
	System.out.println("\nParent:\n");
	for (int i = 0; i < m_nodes.parent.length; i++)
	{
	    if (i == m_numNodes)
	    {
		System.out.println("- - - - - - - - - - - - - - - - - - - -");
	    }
	    System.out.println(i + " => " + m_nodes.parent[i]);
	}

	System.out.println("\nLinksStart:\n");
	for (int i = 0; i < m_nodes.treeLinks.length; i++)
	{
	    if (i == m_numNodes)
	    {
		System.out.println("- - - - - - - - - - - - - - - - - - - -");
	    }
	    System.out.println(i + " => " + m_nodes.treeLinks[i]);
	}

	System.out.println("\nNontreeLinksStart:\n");
	for (int i = 0; i < m_nodes.nontreeLinks.length; i++)
	{
	    if (i == m_numNodes)
	    {
		System.out.println("- - - - - - - - - - - - - - - - - - - -");
	    }
	    System.out.println(i + " => " + m_nodes.nontreeLinks[i]);
	}

	System.out.println("\nLinksEnd:\n");
	for (int i = 0; i < m_nodes.linksEnd.length; i++)
	{
	    if (i == m_numNodes)
	    {
		System.out.println("- - - - - - - - - - - - - - - - - - - -");
	    }
	    System.out.println(i + " => " + m_nodes.linksEnd[i]);
	}
    }

    public void dumpForTesting2()
    {
	System.out.println();
	System.out.println(this + ":");
	System.out.println("\tnumNodes: " + m_numNodes);
	System.out.println("\tnumLinks: " + m_numLinks);
	System.out.println("\tnumTreeLinks: " + m_numTreeLinks);
	System.out.println("\tnumNontreeLinks: " + m_numNontreeLinks);
	System.out.println("\tnextIndex: " + m_links.nextIndex);
	
	for (int i = 0; i < m_numNodes; i++)
	{
	    System.out.println("Node " + i + ":");
	    System.out.println("\tparent link: " + m_nodes.parent[i]);
	    System.out.println("\tparent node: "
			       + (m_nodes.parent[i] >= 0
				  ? m_links.source[m_nodes.parent[i]] : -1));

	    int treeLinks = m_nodes.treeLinks[i];
	    int nontreeLinks = m_nodes.nontreeLinks[i];
	    int linksEnd = m_nodes.linksEnd[i];

	    System.out.println("\ttreeLinks: " + treeLinks);
	    System.out.println("\tnontreeLinks: " + nontreeLinks);
	    System.out.println("\tlinksEnd: " + linksEnd);

	    for (int j = treeLinks; j < linksEnd; j++)
	    {
		if (j == nontreeLinks)
		{
		    System.out.println("\t\t- - - - - - - - - - - - - - - -");
		}

		System.out.println("\t\t" + j + ": "
				   + m_links.source[j] + " => "
				   + m_links.destination[j]);
	    }
	}
    }
}