;;;;; ;;;;;;;;; ;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;; ;;;;;;;;;;;;; ;;;;;;;;;;;;; ;;;;;;;;;;;; ;;;;;;;;;;;; ;;;;;;;;;;; ;;;;xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx ;;;;;;;;; xxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxx ;;;;;;; xxxxxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; tttttt xxxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; tttttttttt xxxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; tttttttttttt xxxxxxxxxxxxxxxxxxxxxxx ;;;;;;; tttttttttttttt xxxxxxxxxxxxxxxxxxxxxx ;;;;;;; ttttttttttttt xxxxxxxxxxxxxxxxxxxxxx ;;;;;;; tttttttttttt xxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; tttttttt xxxxxxxxxxxxxxxxxxxxxx ;;;;;; xxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; xxxxxxxxxxxxxxxxxxxxxx ;;;;;;;;; xxxxxxxxxxxxxxxxxxxxxx ;;;;;;; xxxxxxxxxxxxxxxxxxxxxxx ;;;;;;xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx SSSS EEEE EEEE LL AA BBBB xxxxxxxxxxxxxxxxxxxxxxx SSSS EEE EEE LL AAAA B BB xxxxxxxxxxxxxxxxxxxxxxx SSSS EEEE EEEE LLLL AA AA BBBB xxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxx www.cs.utk.edu/~seelab xxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxx xxxxxxxxxxxxxx xxxx xxxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx -------------------------------------------------------------------------------- -------------------------------- Description ----------------------------------- Simple project to interactively generate and query graph-based data Files included: SeeGraph.cpp/h - main application with a ready-made GLUT framework SeeGraphHelper.cpp/h - contains the GLUT-based drawing and logic code axislayout.c/h - multiple algorithms for optimizing PCP axes bintree.c/h - binary tree for quickly searching edgelists bp.c/h - backpropagation neural network for qualitative classification btd.c/h - operates on block-tridiagonalization of a matrix eb*.cpp/h - energy barrier layout from Davidson in Infovis01 globals.h - #define constants and data struct(s) graphProcessing.c/h - graph structure and graph-based code graphio.c/h - optimized input/output of graph(s) graphioEdgeCnt.c, graphioPrintEdgelist.c, graphioPrintMatrixLT.c, graphioReadEdgelist.c, graphioReadMatrixLT.c, graphiofuncs.c - graphio helpers labellist.c/h - binary tree for searching vertex index/label layout.c/h - compute 3D graph layout for weighted, undirected graph mst.cpp/h - calculates a minimal spanning tree for a graph processing.c/h - a few helper math routines seeEdit.c/h - GLUT-base API for mouse-interactive cells in a viewport seeGScript.cpp/h - scripting for saving/loading of automated key-commands seeKaryo.c/h - automatic karyotype generation based on database data splatting.c - VCB splatting but with larger splats for graph backgrounds tabdelimfile.c/h - IO for tab delimited files -------------------------------------------------------------------------------- ------------------------------ Getting Started --------------------------------- I) OpenGL headers/libs/dlls required: OpenGL, GLEW, GLU, and GLUT (included) II) Visual Cookbook (VCB) required, developed at www.cs.utk.edu/~seelab (included) III) Edit/Compile source: text-editor/make; *.dsw (VC6); *.sln (VC7) IV) Start importing and interacting with your own graph data! -------------------------------------------------------------------------------- ------------------------- Getting Started (verbose) ---------------------------- I) Install OpenGL: if you do not have OpenGL, GLEW, GLU, and GLUT already installed on your machine, it has been included for Windows and Linux under ./OpenGL/win -or- lin/GL a) Minimalist - copy the data from your operating system's (OS) folder to the seeGraph directory b) Mediumnalist - copy the data from your OS's folder to a directory in the system path c) Perfectionist (recommended) - copy the data from your operating system's folder into the appropriate location; for Windows VC6 users: *.h --> C:\Program Files\Microsoft Visual Studio\VC98\Include\GL\ *.lib --> C:\Program Files\Microsoft Visual Studio\VC98\Lib\ *.dll --> C:\WINDOWS\system32\ (optional step as *.dll should already be local) for Linux, copy them to /usr/include/GL Note: For setting up OpenGL on other operating systems, refer to http://nehe.gamedev.net/lesson.asp?index=01 II) Install VCB (Visualization CookBook) created by our lab (www.cs.utk.edu/~seelab) Copy ./OpenGL/VCBrelease/ to C:\ or /home/username/VCBrelease/include Note: Linux users with have to edit the makefile to the location copied Windows users will have to edit the Project=>Settings include and lib preprocessor paths III) Open and build your project: Linux users may use their favorite text editor, a makefile is included for compilation; Windows users have been provided with a Visual Studio 6 C++ (VC6) workspace (*.dsw) as well as a VC7 solution (*.sln) IV) Run it For Windows: Run "Command Prompt" cp Debug/SeeGraph.exe ./ SeeGraph.exe data/demo1.wel For Linux: ./SeeGraph ./data/demo1.wel -------------------------------------------------------------------------------- ------------------------------ Version History --------------------------------- 0.1-0.5 - Received graph IO library from Jon – made significant changes to allow for ease of use; successfully tested reading in and writing out an identical edgelist file Partial development of 2D edge-length heuristic for graph layout 0.6 - Development of all pairs shortest path algorithm (1.5hr runtime on 1.5 Ghz) 0.7 - Partial development (85%) of 3D/dimensionless edge-length heuristic for graph layout 0.8 - Partial development (40%) of 3D spring embedder algorithm 0.9 - Partial development (70%) of 3D spring embedder using temperature 1.0 - Development of non-splatting renderer visualization for 7443 vertices (using quadrics) 1.1 - Odd crash with splatting on initialization of transfer function (has to be simple) 1.2 - Get splatting working (74fps) with on-screen fps display and switch-between for quadrics using random vertices (15fps) Partial development (85%) of 3D/dimensionless edge-length heuristic for graph layout Partial development (40%) of 3D spring embedder algorithm – uses only spring forces to calculate ideal distances between nodes based on the graph theoretic distances. Their algorithm involves an all pairs shortest path (implemented) and then solves linear equations for node positioning. It is not strictly a Force-Directed Particle (FDP) approach and involves a higher complexity of mathematics than most layout algorithms. 1.3 - Full development of 3D spring embedder using temperature, based on GEM – this algorithm follows Eades system of moving each node as its displacement was calculated, but introduces the concept of having an individual ‘temperature’ and cooling schedule for each node. This algorithm uses probabilistic methods and knowledge of each node’s history in order to determine future movement. It also utilizes attraction to a center of gravity or ‘barycenter’ in addition to the spring and repulsive forces. This is faster than Fruchterman and Rengold’s “Graph Drawing by Force Directed Placement” algorithm and Kamada and Kawai’s “An Algorithm for Drawing General Undirected Graphs” algorithm (option C) but is still of time complexity O(n3). 1.4 – Normalization of vertex list to range for displaying 1.5 – Graph Vertex Lists (*.gvl) IO for reading in a vertex layout and displaying 1.6 – The same edgelist (*.wel, *.uel) can be read in using multiple parameters so the program was rewritten to read in the correct vertex list for the given parameters 1.7 – Simple zoom implemented 1.8 – Linux changes made, was crashing passing character array to a function that required a character pointer (odd) – now runs on the PowerWall 1.9a,b – fail in camera-directed normals attempts: use VCB to invert ArcBall matrix for setting the direction correctly (hairy splats), ArcBall inverse transpose, modelview matrix for object space transition/normalization/vector tracing and normalization all before and after translation. 1.9c – Small program created for testing crashing on windows splatting – splatting is more tolerant of splats located outside the dimensions on Linux than on Windows. 2.0 – Fully working version for node visualization using randomized normals; fix normalization error that caused 0 values to terminate the normalization process, eliminated the Windows crashing error for some datasets – now works on all. 2.1 – Remove unconnected vertices, add view structure. Notice that parameters –3.0, 0 don’t give the same information as 0.85, 1. Some glitch with Jon’s IO routines using floating points where nodes with only one edge of size equal to the inclusive threshold are eliminated. 2.2 – add graph structure and start graph processing file. Real-time edge removal algorithm implemented for immediate update without edge counting. 2.3a,b – find bug with floating point precision loss, lose .8500s but keep .8501, program pair down looking for bug but can’t isolate; modify graph structure that stores all relevant data and is used throughout the program, introduce vcbdebug style comments. 2.4 – loads and allows the left/right arrow keys to change the precision from .85 to .95 in steps of .01, the number of vertices are calculated each time and the only data being stored is the vertex locations for each threshold setting (from the spring embedder) 2.5 – fix Jon’s IO routines’ floating point precision errors; add initialization, calculation, and display of current threshold & #edges using a robust edge counter (~ 4 secs). 2.6 – selection of display options with command-line parameters. Can view a single data setting or multiple threshold settings (provided the *.gvls exist). Usage: ./Seegraph viewOption[1-2] filename.wel threshold[0.0-1.0] absValFlag[0,1] Typical Usage: ./Seegraph 1 rma_pearsons.85.wel -3.0 0 Usage: ./Seegraph viewOption[1-2] filename.wel threshold[0.0-1.0] startThresh[0.0-1.0] endThresh[0.0-1.0] stepThresh[0.0-1.0] absValFlag[0,1] Typical Usage: ./Seegraph 2 rma_pearsons.85.wel 0.85 0.95 0.01 1 2.7 – functions renamed more appropriately and a few efficiency tweaks 2.8 – add color-coded edge visualization 2.8b – allow normalization of colors (so not all high/low 0.85-1.0) 2.8c – allow reflection of negative colors (negative blue, positive red) 2.8d – optimize edge drawing…still at 5 fps with 696,668 edges in 800x600, but can still speed this up once query filtering is introduced 2.9 – add LCC algorithm that gives the seemingly correct values for the number of vertices at different threshold settings (shown in figure 1 below) 2.9b – integrate the viewing of the LCC with the other viewing options, everything correct but the edges for only the LCC 3.0 – vertex list based manipulation for voxel initialization 3.1a,b,c – edge list based algorithm to show only edges for visible vertices; 1D edge list with function problems for defining vertices in 2D; working 2D function with correctly colored and existent edges (now disconnected and LCC show appropriate edges) 3.2a,b – create viewIndex 2 for viewing multiple spring-embedded layouts; create viewIndex 3 for viewing a single spring-embedded layout and operating only on the provided vertex locations (viewing the “induced subgraph”); vertex and edge list operations fully functional 3.3 – change vertex and edge list processing to be straightforward, add options for viewing edges (now can view all edges for existent vertices) 3.4a – incorporates full use of edge/vertex lists and sets up the tree for querying 3.4b – setup support for vertex query but need to make more general (with pointers); smart hypothesis initialization based upon the min/max of each feature 3.4c – editable vertex equation with display in the main window 3.4d – full use of vertex querying 3.4e – combine arbitrary querying with disco and edge algorithms 3.4f – combine arbitrary querying with LCC, change to viewMode with macro options, now fully functional vertex querying on 0.85’s degree 3.5a – organize project for better readability, discover memory error during optimization, create smaller project which has the same error (worked around it) 3.5b – project restructure with functions in alphabetized logical/temporal groups 3.6a – add debugging code for printing runtimes for targeting optimization 3.6b – compute degree of each node for each user-specified thresholding step, reduces 2-sec vertex querying to 0-ms by paying an up-front 35=>18-sec cost 3.7a – add IO for vertex and edge information that is currently being displayed, fix very rare but luckily evident floating point precision error 3.7b – eliminate line-lighting artifacts on rotation, add view options and view modes for support across all options 3.7c – change red/blue coloring scheme for psychovisual attentive-direction and contrast, allow toggle option to view/hide disconnected 3.7d – verify that the querying works well in combination with all other options, allow view of disconnected vertices when querying 3.7d – fix one-byte non-terminal string free error thanks to Dr. Huang 3.7e – generic multi-query support for floating point hypotheses and equation strings using the new non-static string allocation approach 3.7f – change a few naming conventions and make more dynamic/memory efficient 3.8a – begin edge list querying to take away 250+ms delay upon query change but can’t proceed due to absolute value, need new querying functionality 3.8b – local append query for absolute value, assumes 2 results are disjoint but can add to VCB if desired (possible append and remove query types) 3.8c – edge querying with odd realloc error (doesn’t return null but destroys results) 3.8d – successfully implement edge querying and gives the correct results but takes longer than the non-querying scheme (Kalahari - 313ms vs. 145ms despite different tests of m/n, but home comp gets 218 vs. 219-235) 3.9a – settle on no edge querying, but can insert by uncommenting a few lines; fix a few machine states for robust performance with different combinations of runtime parameters 3.9b – add ability to stop active querying and fix quads to behave exactly like splats 3.9c – add ability to change the coloring scheme for edges while maintaining node colors 3.9d – consistent red/blue color for nodes, finishing touches before delivery 4.0 – stable version delivered to Dr. Elissa Chesler at ORNL for evaluation and use 4.1 - inclusion of defaults and warnings for more robust handling of bad data 4.2 - lower triangular matrix format for more efficient file storage 4.3 - lower triangular matrix format as input verified and save output picture of graph 4.4 – made more robust to handle integer weights (though this should never happen now) 4.5a,b – stack overwrite, support the new *.gvl format from laymeout1.2b 4.6 - code for picking nodes but not implemented yet 4.7a – implementation of picking not working correctly 4.7b – simpler version of just picking a sphere, all unnecessary detail removed 4.7c – rewrite all functions to load identity and work from there rather than assuming a previous matrix, simplifies glut main loop, picking supported for quadrics, splats (not accurate for picking since primitive triangles extend beyond visible splat), and sphere 4.7d – picking working, colors selected nodes green but only works for quads (no glNames in splat code) 4.8a – selection and deselection of examples (green) and counterexamples (yellow) with normal vertices being red (traffic light cognitive model) 4.8b – neural network integrated, colors all vertices based on degree either green or yellow and does so correctly and quickly (though some memory issues on larger graphs, need to gdb/efence/valgrind it) 4.8c – run Valgrind on SeeGraph and eliminate any small memory leaks 4.8d – code readability and more user-friendly; change neural network to filter rather than color-code; add interactive multiquery capability 4.8e – map query results to red, green, blue; somewhat different data struct (no voxel hack) 4.9 – key “t” to hide text, key “v” to take a 360-degree video (ppm files) in arbitrary degree-step increments, fix image-write memory leak 5.0 – stable multi-color querying 5.1 – conversion to row-major matrix order (for small and medium graphs to be used in the Yihua Bai’s block tri-diagonalization code) 5.2 – customizable size of a texture with loading of PGM 5.2b – red/blue coloring of a texture with preservation of state 5.2c – fix hot/cold texturing of PGM with multiTexCoord (Dr. Huang’s help) 5.2.5 – attempt and fail to use paletted texture using COLOR_INDEX for 1/12 space 5.2.6 – attempt and fail to print out and read in permutation vector and rearrange for the same PGM as previously generated 5.2.7 – some neural network API investigation and refinement 5.2.8 – start integration of SeeEdit 5.3 – seeEdit integrated but problem with OpenGL state when drawn 5.4 – nice import of BTD from PGM or PV but problem reconstructing from PV Using floats for texture since GL_UNSIGNED_BYTE, GL_BYTE, GL_SHORT, and GL_INT don’t work 5.4b – try reconstruction using row swap, column swap, row-then-col swap, all rows then all columns swap, finally learn I have to change indices and now can successfully reconstruct the BTD matrix from the permutation vector (saves lots of PGM space) *should* be implemented soon 5.4b – try unsuccessfully to reconstruct BTD matrix from the permutation vector (saves lots of PGM space) 5.4c – use Bai’s permut.f90 code as a basis for the reconstruction and get it working, removing the large, now unnecessary PGM files (though SeeGraph can still import) 5.4d – move all BTD code to separate file with API for creating the data and loading it into a texture unit; header file includes instructions for the entire process for a new dataset 5.5 – show BTD belt using texture 5.6a – selections on BTD Matrix loaded from PGM 5.6b – selections draws for marking BTD matrix from permutation vector 5.7 – use BTD belt selections for LOD (begin) 5.7b – use belt select and create API for it 5.7c – draw BTD with no diagonal 5.7d – working BTD non-belt selections for viewing subgraph (easy math) 5.7e – working BTD belt selections for viewing subgraph (hard math) 5.7f – begin LOD using BTD selections 5.8 – construct LOD graph and handle shallow-copied memory to be efficient 5.8b – more LOD handling of graph memory 5.8c – abstract away vertex position from display vertex position so user can interactively move vertices with keys 5.8d – make drawing routines use the new vertex position location 5.8e – debug vertex drawing position and simply change pointer to draw at original view.loclist computed locations 5.8f – LOD with BTD selections fully working with Boolean between viewing subgraph or as LOD vertex 5.9 – LOD NN in which you can train based on vertices which actually constitute entire subgraphs, immediately displays the classification and new BTD selection goes back to LOD mode 6.0 – label vertices 6.1 – seeEdit callback function for requerying on change 6.2 – coloring options for BTD added 6.3 – splats around vertices 6.4 – splats around subgraphs, local splatting 6.5 – rendering of vertices changed for specular highlights with colored halos – looks awesome 6.6a,b – creations of subgraphs, ability to write BTD to file 6.7a,b,c – modularize subgraph processing, subgraph splat crash inspection, subgraph treatment (positions hard-coded) 6.8 – fix thresholding and color-coded querying 6.9 – BTD color options enhanced and set to good default 7.0 – get new data 7.1 – nearest neighbor subsampling of BTD texture to fit in memory if too large 7.2 – rendering options changed but find slowness is from vertex quadric resolution 7.3a,b – problems with LCC display, unable to import new/combined data from Wes 7.4 – Wes’ new data working, now need query step size fixed and BTD to get paper results; too late for Vis07 so cancel submission 7.5 – fix seeEdit state and now runs properly without interfering with main window 7.6 – major seeEdit revision, dynamically adjusts to windows size making sure the query and all interactive elements fit on screen, tries to align based on longest value, repositions bounding box on move, prints out location elements in formatted fashion 7.7 – hard-coded placement for graphs without data (use vertex degree) and D3 which has 8 features; make each graph rotate about it’s own coordinate system, this fixed splatting so now vertices remain the color they were with subgraph backgrounds being different colors from other graphs 7.8 – fix subsampling for greater than 2 subdivisions, also includes new D3 btd data 7.9 – color BTD by chromosome 8.0 – interactive seeEdit for requery on mouse move or only on mouse release; some specific hacks to get result pictures 8.1 - dynamically compute layout (*.gvl) if none exists 8.1b - add in checks for demo files so that query values are always in correct place 8.1c - allow customizable display of vertex labels 8.2 – add ability for fast querying using hash for combination, reduces computational complexity of list merge after query 8.2b – changes made for compatibility with Linux and integration on server 8.3 – add ability to save file and exit to use as a webtool, fix memory error 8.3b – changes made for compatibility with Linux and integration on server 8.3c – change handling of realloc to allow for greater resize while freeing; create makefile for webserver but no compatible vcb library yet 8.4 – add options to minimize number of input parameters to only filename (at the expense of an additional *.wel file load) 8.5 – ability to reset to original working graph (resets BTD and queries) 8.5b – if no data is available and the graph is fully connected, query by vertex ID instead of degree 8.6 – integrate the R language into SeeGraph via system call, create graph input/output function and file format for easily editing visible graph or weight data; runs O(n^2) 8.7 – create bi-partite graph layout routine (in-place bfs algorithm); inspects any graph without a layout and creates a bipartite layout if the graph is bipartite 8.8b – partial gaggle API, partial LoD from subgraphs, partial bipartite graph detection and layout; several minor fixes including vcbbtree checking for proper building from m and n 8.9 - integrate Wes Kendall's 2d and 3D layout based on Fruchterman and Reingold's algorithm; now dynamically swap between 2d and 3d layouts; also small vertex label for moved graph fix 9.0 - add support for diamond-shaped selections on BTD belt, maintain aspect ratio on btd belt, fix some bugs, add new color tables for BTD 9.1 – correct mathematical mapping from BTD selections to corresponding vertices using an inverse map for O(1) time (screen2btdbelt, belt2btd) though numerical error accumulates when iterating between the forward and inverse mappings 9.2 – additional level-of-detail graph features added along with dynamic layout, automatic calculation based on feature data, and generation from arbitrary graphs rather than BTD selections (bug in new adjacency matrix calculation) 9.3 – add capability of reading in 256-entry RGB colortable which can be used to customize the view for the whole application (vertex colors, edge colors, btd, query colors, etc.) 9.4 – add the ability to color the BTD by a given feature to see the distribution patterns for comparisons with clustering techniques such as paraclique 9.5 - add some colorbar functionalities 9.6 - lots of work on axis layout for parallel coordinate renderings including a naive k-max implementation for highest metric pairs, bestByPairs brute force search for max fitness of pair swapping (O(k|V|^2 + k!)), layout computed from multiple metric files based on maximum sum or average, and comprehensive/brute-force search of axis combinations unfortunately NP-complete, and utility function for computing function of a given layout. 9.7 - added the capability of coloring by an arbitrary feature from the DB, used for distinct coloring by chromosomes. 9.8 - added ability to write a karyotype image based on vertex chromosome&position information with colors assigned according to the vertex color scheme in combination with color-by-feature 9.9 - added borders to karyotype, created c-button custom script/automation for generation of hundreds/thousands of images based on querying and threshold operations 10.0 (1.00) - major revisions and cleanup: seeGScript - Added ability to write scripts so hardcoding is not necessary. Many features (for loops, if, else, ifelse statements) can be executed to reproduce results; ability to record movements into a script file. mst - Added a minimal spanning tree layout eb* - Added an energy-barrier layout seeEdit changes and memory cleanup --Adding support for loading scripts in InitData (Everett) --Scripting Features Complete Control Structures(For,If,IfElse,Else) Loading Data From Directories Change Certain Coded Variables (Coded for easy adding ability) Call Certain Functions(Also Coded for easy ability to add more) --Few Bug Finds Note: Many more were found but need more investigation to fix, since by fixing some, it creates more than were previous. --Record Movements and Action**** This had been implemented, but there are a few bugs I am working out. Therefore this is the previous version before this is implemented. 1.01 - added greedy axis-optimization O(|V|^2+k|V|) in axislayout.c --------------------------------------------------------------------------------