HypView

HypView is the main interface class for the HypViewer library, which provides layout and interactive navigation of node-link graphs in 3D hyperbolic space. The library can handle quite large graphs of up to 100,000 edges quickly and with minimal visual clutter. The hyperbolic view allows the user to see a great deal of the context around the current focus node.

[ HypViewer | Source | Summary | Ancestors | All Members | Descendants ]

Quick Index

OVERVIEW

LAYOUT

DRAWING

INITIALIZATION

INPUT FILE FORMAT

DEPENDENCIES

MAKEFILES

AUTHOR

Class Summary

OVERVIEW

This class is the main interface between the entire library and the application programmer. No get methods are documented - see the corresponding set method.

LAYOUT

The HypView layout algorithm finds a spanning tree from an input graph and then computes a layout of that tree. A spanning tree touches every node in a graph, but only a subset of the links. In a graph a node can have many parents, but in a tree a canonical parent is chosen for each child. Links which appear in the graph but not in the spanning tree are called "non-tree links". These links do not affect the layout computation and are only drawn on demand for a selected node or nodes.

The backbone spanning tree used by the layout and drawing algorithms strongly influences the visual impact on the user. The approach hinges on the idea that there are many graphs for which the right spanning tree can provide a useful mental model of the entire structure. As a fallback, a default spanning tree can always be found using breadth-first search from a root node. However, exploiting a small amount of domain-specific knowledge can allow the library to construct a better spanning tree which provides a more useful mental model. For instance, for a Web site one can use the directory structure encoded in the URL to choose which of the incoming hyperlinks to a site should be chosen as the main parent in the spanning tree. The specific spanning tree policies used by the library are controllable with the clearSpanPolicy() and addSpanPolicy() methods.

DRAWING

The HypView class has a multi layer scheme which preserves window system independence while providing flexibility for the application programmer. First, the mouse(), motion(), and passive() methods are a way for a window system layer to pass event loop information about the mouse into the HypView class. Second, the bindCallback() allows the application programmer to bind the main interaction functions to the desired mouse behavior. The setPickCallback() and setHiliteCallback() functions can be used to return control to application program callbacks when the user moves the mouse over nodes and links. Finally, methods like setSelected() and gotoNode() can be used inside the pick or highlight callbacks in the application program.

The HypView drawing algorithm depends on the number of visible, not total, number of nodes and edges. The projection from hyperbolic to euclidean space guarantees that nodes sufficiently far from the center will project to less than a single pixel. Thus the visual complexity of the scene has a guaranteed bound - only a local neighborhood of nodes in the graph will be visible at any given time.

A guaranteed frame rate is extremely important for a fluid interactive user experience. The HypView adaptive drawing algorithm is designed to always maintain a target frame rate even on low-end graphics systems. A high constant frame rate is maintained by drawing only as much of the neighborhood around a center point as is possible in the allotted time. When the user is idle, the system fills in more of the surrounding scene. A slow graphics system will simply show less of the context surrounding the node of interest during interactive manipulation.

The amount of time devoted to a frame should depend on the activity of the user. The HypView library allows separate control over the drawing frame time, idle frame time, and picking frame time using the setDynamicFrameTime(), setIdleFrameTime(), and setPickFrameTime() methods. The dynamic frame time is simply the time budget in which to draw a single frame during user mouse movement or an animated transition. It is clear that the drawing time should be explicitly bounded instead of increasing as the node/edge count rises. The time spent casting pick rays into the scene must be similarly bounded. When the user and application are idle, the system can fill in more of the surrounding scene. However, the time spent on this, the idle frame time, should still be bounded to eventually free the CPU for other tasks.

INITIALIZATION

Most functions have no effect or return NULL if called after a HypView object is instantiated but before the setGraph member is called. However, the following functions can be successfully called even before the first setGraph() call:

addSpanPolicy(), bindCallback(), clearSpanPolicy(), getDynamicFrameTime(), getIdleFrameTime(), getPickFrameTime(), getSphere(), getEdgeSize(), getLabels(), getLabelSize(), getLabelFont(), getPassiveCull(), getMotionCull(), getAreaFudge(), getLengthFudge(), getLeafRad(), getMaxLength(), getGenerationNodeLimit(), getGenerationLinkLimit(), getCenterShow(), getCenterLargest(), getNegativeHide(), getSpanPolicy(), getGotoStepSize(), getTossEvents(), getWidget(), setCenterLargest(), setCenterShow(), setColorHilite(), setColorSelect(), setColorLabel(), setColorLinkFrom(), setColorLinkTo(). setEdgeSize(), setGenerationNodeLimit(), setGenerationLinkLimit(), setGotoStepSize(), setGroupKey(), setHiliteCallback(), setKeepAspect(), setLabels(), setLabelSize(), setLabelToRight(), setLeafRad(), setLinkPolicy(), setMaxLength(), setNegativeHide(), setMotionCull(), setPassiveCull(), setPickCallback(), setSphere(), setTossEvents(), setDynamicFrameTime(), setIdleFrameTime(), setPassiveFrameTime(),

The following functions cannot be called until after the window is shown, since they depend on having a graphics context: drawFrame(), redraw(), reshape(),

INPUT FILE FORMAT

Each line of the input file is of the form

  depth identifier 1 group1 [group2 ... groupN]

with the following types

  int string int string [string ... string]

Each line corresponds to a node. The order of the lines is meaningful. The integer at the beginning of the line is the depth in the tree. A line with depth one greater than the line above it indicates a link between two nodes from the line above to the line below. The identifier strings are assumed to uniquely specify a node. If an identifier occurs twice that means a node has more than one incoming link, so the file describes a general graph, as opposed to a tree or a directed acyclic graph (DAG). The identifier string is used as an interface between the library and the application program in many methods which have the argument "string & id".

A file with structure like

0       A   [...]
1       B   [...]
2       C   [...]
3       D   [...]
4       A   [...]
3       E   [...]
2       F   [...]
1       G   [...]
1       H   [...]
2       I   [...]
2       J   [...]
1       K   [...]

corresponds to a graph that looks like:

  .-------- A
 /      ____|_______
 |     /   |   \    |
 |    B    G    H   K
 |   / \       / \
 |  C   F     I   J
 \ / \
  D   E

The very first node is the root, the numbers correspond to the number of layers deep in the hierarchy.

The software computes a spanning tree to use as the base for layout and display. The addSpanPolicy() method controls the policies used to create this spanning tree. If the HV_SPANFOREST policy is used, then you can have a forest of distinct subtrees that are not mingled. The other policies, like HV_SPANBFS for breadth-first search, are then applied to each subtree independently. A forest is specified by having a toplevel starting root which has depth < 0. For instance,

-1 top 1 html
 0 subtree1/root 1 html
  1 subtree1/thing1 1 html
  1 subtree1/thing2 1 html
[...]
 0 subtree2/root 1 html
  1 subtree2/thing1 1 html
  1 subtree2/thing2 1 html

Groups and collections are an organizational mechanism for filtering and coloring nodes. A node can belong to exactly one group per collection. In the input file, the collections correspond to columns and groups correspond to the values which are in the columns. A node can also be associated with a group in a collection with the setNodeGroup() method. Collections are designated by a number, starting with 0. There must be at least one collection, and there can be up to 16 different ones. Each collection can have any number of groups. Group names are designated by text strings and can be used in different collections. Any group in a collection can be disabled. A node will be drawn if none of its associated groups have been disabled. Groups are enabled by default and may be explicitly disabled/reenabled by the application program using the setDisableGroup() method. Each group in each collection can have a color assigned to it with the setColorGroup() method. The setGroupKey() method allows the application program to change which of the collections is used for coloring.

For example, the file

 0 http://hyper/ 1 html main
 1 http://hyper/index.html html main
 1 http://hyper/logo.gif image main
 1 http://hyper/old.html html orphan

with the following code in the application

  hv->setColorGroup(0, "image", .42, 0, .48);
  hv->setColorGroup(0, "html", 0, 1, 1);
  hv->setColorGroup(1, "main", 1, 1, 1);
  hv->setColorGroup(1, "orphan", .2, .2, .2);

  hv->setDisbleGroup(1, "orphan", 0);
  hv->setGroupKey(0);

would result in three visible nodes, colored by collection 0: the logo.gif node would be colored purple and the index.html and top-level hyper nodes would be colored cyan. The old.html node would not be drawn since the orphan group is disabled.

Finally, the third item in the input file line must be an integer, which should be set 1 (for historical reasons).

DEPENDENCIES

The HypView libraries are written in C++ and use OpenGL/Mesa and STL. There is a small amount of OS/window system dependent code which is segregated by "ifdef"s. The three main flavors are Unix XWindows and Microsoft Windows, and GLUT. The XWindows version is tagged as "GLX" in the Makefiles and has two flavors: Xt and ViewKit. Xt is probably the most useful version. ViewKit is a library built on top of Xt (so the code is quite similar) which is most popular under Irix, but has been ported to other platforms. The libraries were originally written under ViewKit, so there are a lot of historical "vk" tags still lying around despite the fact that Xt is now the main version.

GLUT is a window-system independent library from Mark Kilgard (formerly of SGI), downloadable from http://reality.sgi.com/opengl/glut3/glut3.html. It should theoretically be able to run under Windows but has only been tested under Irix. The GLUT version is simpler than the Xt one but not as powerful, which unsurprisingly mirrors the relationship of GLUT and Xt/ViewKit.

The Windows version has been tested on Windows NT under Visual C++. The Borland version has not been tested for a while.

MAKEFILES

Select the appropriate flavor of OS and window system by uncommenting the relevant line in Makefile.main, then edit the relevant Makefile for your system to make sure all paths are set correctly for your system.

AUTHOR

 Tamara Munzner
 http://graphics.stanford.edu
 munzner@cs.stanford.edu

HDC getWidget();

NOTE: we now take an istream reference. Hence we can accept an ifstream (for data from disk) or an istrstream (for data from memory). - dwm@caida.org

int initGraph(string & rootId, int rootPriority, string & rootGroup);

Default: HV_LINKLOCAL

void setColorGroup(int i, const string & group, float r, float g, float b);

Default: 1

int setDrawNode(const string & id, bool on);

Default: 1

void setNegativeHide(bool on);

Default: 0

void setNodeGroup(const string & id, int groupkey, const string & group);

The choices for b (mouse events) are HV_LEFT_CLICK, HV_MIDDLE_CLICK, HV_RIGHT_CLICK, HV_LEFT_DRAG, HV_MIDDLE_DRAG, HV_RIGHT_DRAG, and HV_PASSIVE. Passive is the mode when no mouse button is held down. The other modes are obvious from their names. The choices for c (functions) are HV_PICK, HV_HILITE, HV_TRANS, and HV_ROT.

The translate and motion functions will move the structure in accordance with the incremental mouse motion as reported by the drag or passive events. The translate motion function will move the structure in 3D hyperbolic space. The visual effect is to change the center of focus. The rotate motion function will spin the structure around the center of the ball in a familiar 3D euclidean transformation.

The pick and highlight functions both act on the node in the 3D scene directly underneath the mouse cursor in the 2D window. The highlight function will change the color of the node when the mouse is directly over it. If the setHiliteCallback() method has been used to assign a highlight callback function, control will be then passed to the application program along with the name of the node and the status of the shift and control keys. The pick function does not trigger any direct action itself, but if the setPickCallback() function has been used to assign a pick callback control will also be passed to the application along with the node name and shift/control key status.

Although the application programmer is free to bind the pick and highlight functions to any mouse combination, a common use is binding an explicit click to the pick to trigger selection and using passive mouse motion for lightweight actions with the highlight callback.

void drawFrame();

Mainly intended for debugging, definitely not recommended for application programmer use.

int idleCB();

Returns 1 if the idle mode should stay on, 0 if the idle processing is done. Not usually recommended for application programmer use: requires understanding of library internals. The redraw command is usually more appropriate.

void motion(int x, int y, int shift, int control);

The (x,y) position should be given using the X window coordinate system, where the origin is in the upper left corner of the window. The booleans "shift" and "control" are set to 1 if the respective keyboard keys are depressed, or 0 if they are not.

Intended for use by a window system layer above this class as opposed to the application programmer.

void mouse(int b, int s, int x, int y, int shift, int control);

The button boolean "b" is set to 0, 1, or 2 to indicate which button is depressed. The state boolean "s" is set to 0 when the button is pressed down and 1 when the button is released. The (x,y) position should be given using the X window coordinate system, where the origin is in the upper left corner of the window. The booleans "shift" and "control" are set to 1 if the respective keyboard keys are depressed, or 0 if they are not.

Intended for use by a window system layer above this class as opposed to the application programmer.

void passive(int x, int y, int shift, int control);

The (x,y) position should be given using the X window coordinate system, where the origin is in the upper left corner of the window. The booleans "shift" and "control" are set to 1 if the respective keyboard keys are depressed, or 0 if they are not.

Intended for use by a window system layer above this class as opposed to the application programmer.

void redraw();

Default: 0

void setPickCallback(void (*fp)(const string &,int,int));

  struct timeval getDynamicFrameTime();

  struct timeval getIdleFrameTime();

  struct timeval getPickFrameTime();

int getCenterShow();

int getCenterLargest();

float getEdgeSize();

int getGenerationNodeLimit();

int getGenerationLinkLimit();

float getGotoStepSize();

int getLabels();

float getLabelSize();

char* getLabelFont();

float getLeafRad();

float getLengthFudge();

float getMaxLength();

int getMotionCull();

int getNegativeHide();

int getPassiveCull();

int getSphere();

int getSpanPolicy();

int getTossEvents();

void setCenterLargest(bool on);

Default: 0

void setEdgeSize(float s);

Default: 5

void setGenerationNodeLimit(int s);

Default: 30 (i.e. draw as much as possible)

void setGenerationLinkLimit(int s);

Default: 30 (i.e. draw as much as possible)

void setGotoStepSize(float s);

Default: .05 (20 steps)

void setKeepAspect(bool on);

Default: 0

void setLabels(int on);

Default: HV_LABELLONG

void setLabelSize(float s);

Default: 20

ifdef WIN32 void setLabelFont(const string & s, int sz);

Default: .3

void setMaxLength(float s);

Default: 2.7

void setMotionCull(int s);

Default: 5

void setPassiveCull(int s);

Default: 5

void setSphere(bool on);

Default: 0

void setTossEvents(bool on);

Default: 0

void setDynamicFrameTime(struct timeval time);

Default: 0 sec, 50000 usec (20 FPS)

void setIdleFrameTime(struct timeval time);

Default: 1 sec, 0 usec

void setPickFrameTime(struct timeval time);

Default: 0 sec, 100000 usec (10 FPS)

void setColorBackground(float r, float g, float b);

Default: 1,1,1

void setColorHilite(float r, float g, float b);

Default: 0,1,0

void setColorLabel(float r, float g, float b);

Default: 0,0,0

void setColorLinkFrom(float r, float g, float b);

Default: .6, .2, .2

void setColorLinkTo(float r, float g, float b);

Default: .2, .2, .6

void setColorSelect(float r, float g, float b);

Default: 1,1,0

void setColorSphere(float r, float g, float b);

Default: .9, .7, .6

HypGraph *getHypGraph() ;

Function is currently defined inline.

All Members

Ancestors

Descendants