Dynamic Graph Visualizer Tool

URS Thesis Project by Octavio Almanza

Faculty Advisor: Dr. Nate Veldt

This repository contains the source code for a command line interface to create dynamic graph visualizations, as well as some Julia functions and structures to plot graphs and automate the visualization creation process.

Sample Visualizations of Graph Algorithms

|Algorithm|Visualization| |:---:|:---:| |Breadth-First Search Algorithm|| |Kruskal's Minimum Spanning Tree Algorithm|| |Dijkstra's Single-Source Shortest Path Algorithm||

Visualization Interface Usage and Commands

A visualization is composed of an ordered sequence of $S$ graph states. By modifying the visual attributes of these graph states, users can create their own visualizations.

Traversing Graph States

focus i - Tells the visualizer to display state $i$, where $1\leq i \leq S$, so the user can view or modify the state. nx - Traverses to the next state. Will not work if the user is at state $S$. pr - Traverses to the previous state. Will not work if the user is at state $1$. preview - Shows a preview of the states in the visualization. Users can optionally provide the following commands: - -t INTERVAL - Sets how long each state in the visualization is shown for in the preview, in seconds. INTERVAL must be a floating point number. - -start i - Tells the visualizater to only preview states starting from index $i$. $i$ is an integer where $1\leq i \leq S$. - -end j- Tells the visualizater to stop previewing states after previewing the state at index $j$. $j$ is an integer where $1\leq j \leq S$.

Modifying the Visualization Structure

dup i - Creates a duplicate of the state at index $i$, where $1\leq i \leq S$. The user can provide the following optional arguments. - -n VAL - Tells the visualizer to create VAL copies of state $i$. By default, there will only be one copy made. VAL must be a positive integer. - -dest j - Requests for the duplicate(s) to be inserted at position $j$. By default, the duplicate(s) will be inserted at the index $i+1$.

del i - Deletes the state at index $i$, where $1\leq i \leq S$.

mv i j - Removes a state from position $i$ and inserts the state at position $j$, where $1\leq i,j \leq S$

swap i j - Swaps the states at index $i$ with the state at index $j$, where $1\leq i,j \leq S$.

Modifying Graphs and Visual Attributes

add node - Adds a node to the graph's node array. Users can specify its attributes with the following arguments. - -l LABEL - Specifies the label of the node. LABEL must be a string with no whitespace. If not specified, the label will be a number that cannot already be found in the graph. Node labels are unique, meaning that this command will fail if there is already a node with the same label in the graph. - -s SIZE - Specifies how big the node is in plot units. size must be a positive integer. If not specified, the default value will be 0. - -x x_COORD - The node's x-coordinate in a cartesian plane. X_COORD must be a real, floating point number. - -y y_COORD - The node's y-coordinate in a cartesian plane. Y_COORD must be a real, floating point number. If not specified, the default value will be 0. - -fc FILL_COLOR - The fill color of the node. FILL_COLOR must be a string with no whitespace denoting a supported color. The default background color is white. - -oc OUTLINE_COLOR - The outline color of the background of the node. OUTLINE_COLOR must be a string with no whitespace denoting a supported color. The default outline color is black. - -lc LABEL_COLOR - The font color of the node's label. LABEL_COLOR must be a string with no whitespace denoting a supported color. The default outline color is black.

add edge SOURCE_LABEL DEST_LABEL - Adds an edge between a source node with label SOURCE_LABEL and a destination node with label DEST_LABEL. The other that these labels are specified is not important in the case of undirected graphs. Users can specify other edge attributes with the following arguments. - -w WEIGHT - The corresponding weight of the edge. WEIGHT must be a floating point number. If not specified, the default weight value is 1. - -t THICKNESS - How thick the edge is drawn. THICKNESS must be a positive integer. If not specified the default thickness is 1. - -c COLOR - The color of the edge. COLOR must be a string with no whitespace denoting a supported color. The default color of an edge is black.

rm node LABEL - Removes the node with label LABEL from the graph.

rm edge SOURCE_LABEL DEST_LABEL - Removes the edge connecting a source node with the label SOURCE_LABEL to a destination node with the label DEST_LABEL. Will fail if such an edge does not exist.

set node LABEL - Updates the visual attributes of the node with label LABEL to the values specified via arguments. This command supports the following arguments: - -l LABEL - Provides a new label for the node. LABEL must be a string with no whitespace. Node labels are unique, meaning that this command will fail if there is already a node with the same label in the graph. - -s SIZE - Specifies how big the nodes are in plot units. size must be a positive integer. If not specified, the node's size will remain the same. - -x x_COORD - The x-coordinates in a cartesian plane. X_COORD must be a real, floating point number. If not specified, the x-coordinate will remain the same. - -y y_COORD - The y-coordinates in a cartesian plane. Y_COORD must be a real, floating point number. If not specified, the y-coordinate will remain the same. - -fc FILL_COLOR - The fill color of the node. FILL_COLOR must be a string with no whitespace denoting a supported color. If not specified, the fill color will remain the same. - -oc OUTLINE_COLOR - The outline color of the background of the node. OUTLINE_COLOR must be a string with no whitespace denoting a supported color. If not specified, the outline color will remain the same. - -lc LABEL_COLOR - The font color of the node's label. LABEL_COLOR must be a string with no whitespace denoting a supported color. If not specified, the label color will remain the same.

set edge SOURCE_LABEL DEST_LABEL - Updates the visual attributes of the edge with a source node with the label SOURCE_LABEL and a destination node with the label DEST_LABEL to the specified arguments. The following arguments can be provided: - -w WEIGHT - The corresponding weight of the edge. WEIGHT must be a floating point number. If not specified, the weight will remain the same. - -t THICKNESS - How thick the edge is drawn. THICKNESS must be a positive integer. If not specified the thickness will remain the same. - -c COLOR - The color of the edge. COLOR must be a string with no whitespace denoting a supported color. If not specified, the edge's color will remain the same.

setall nodes - Updates the visual attributes of all of the nodes in the graph. Note: This command overwrites the visual information stored in all nodes, and thus should not be used unless the user desires to make a particular attribute uniform for all nodes. The following arguments can be provided: - -s SIZE - Specifies how big the node is in plot units. size must be a positive integer. If not specified, the node's size will remain the same. - -x x_COORD - The node's x-coordinate in a cartesian plane. X_COORD must be a real, floating point number. If not specified, the x-coordinate will remain the same. - -y y_COORD - The node's y-coordinate in a cartesian plane. Y_COORD must be a real, floating point number. If not specified, the y-coordinate will remain the same. - -fc FILL_COLOR - The fill color of the node. FILL_COLOR must be a string with no whitespace denoting a supported color. If not specified, the fill color will remain the same. - -oc OUTLINE_COLOR - The outline color of the background of the node. OUTLINE_COLOR must be a string with no whitespace denoting a supported color. If not specified, the outline color will remain the same. - -lc LABEL_COLOR - The font color of the node's label. LABEL_COLOR must be a string with no whitespace denoting a supported color. If not specified, the label color will remain the same.

setall edges- Updates the visual attributes of all of the edges in the graph. Note: This command overwrites the visual information stored in all edges, and thus should not be used unless the user desires to make a particular attribute uniform for all edges. The following arguments can be provided: - -w WEIGHT - The corresponding weight of all edges. WEIGHT must be a floating point number. If not specified, the weights will remain the same. - -t THICKNESS - How thick the edges are drawn. THICKNESS must be a positive integer. If not specified the thicknesses of each edge will remain the same. - -c COLOR - The color of the edges. COLOR must be a string with no whitespace denoting a supported color. If not specified, each edge's color will remain the same.

Saving and Loading Graph States

ssave FILENAME.EXT - Used to output data or generate a figure from the current state being focused. - Supports outputting graph information to JLD, VAC, and MTX files. - Note: Only JLD and VAC files store the visual attributes of the graph state. - Supports creating PDF and PNG figures for the current graph plot.

sload FILENAME.EXT - Supports reading-in JLD, VAC, MTX, and compatible MAT files. Overwrites the data of the state that is currently in-focus.

Saving and Loading Visualizations

vsave FILENAME.EXT - Used to output data or generate figure(s) from the current visualization. The extension of the provided filename is used to determine which internal function will create the output file. - Users can use the following arguments to specify a range of states $[i,j]$, where $1\leq i\leq j\leq S$, to output with the following arguments: - -start i - The starting output state index. If not specified, the value is set to $1.$ - -end j - The final output state index. If not specified, the value is set to $S$. - Supports outputting the visualization to JLD and VACA files. - Supports creating a GIF file containing the specified states. Users can customize the GIF file with the following commands: - -dpi DPI - Specifies the resolution of the GIF file via dots-per-inch. DPI must be an integer. If not specified, the output file will have $150$ DPI. - -t INTERVAL - Specifies how long each state is shown in the GIF file, in seconds. INTERVAL must be a floating point number. - Finally, this command also supports outputting a sequence of PDF or PNG files to a specified folder. To do this, users can input, vsave EXT FOLDER_NAME, where EXT is either PNG or PDF. If a folder with the name FOLDER_NAME does not exist in the current working directory, it will be created.

vload FILENAME.EXT - Loads a visualization from the input file. The only supported input file extensions are .VACA and .JLD animation files.

Loading xy-Coordinates and Applying Graph Layouts

loadxy FILENAME.txt - Reads-in a text file containing $|V|$ lines, where the $ith$ line contains two space-separated floating point numbers denoting the cartesian coordinates of the $i$th node. - If there are more than $|V|$ lines in the text file, the remaining lines are discarded. - If there are less than $|V|$ lines in the text file, some nodes will not have their position updated.

layout LAYOUT_ALGO - Users can also derive coordinates for each of their node with one of the supported graph layout algorithms. LAYOUT_ALGO must be one of the following algorithms: - circular - All nodes are placed in a circle centered at the origin. - force - Nodes are given random XY-coordinates and then a force-directed algorithm is applied. Users can specify some parameters of this algorithm, such as: - -iters i - An integer denoting the maximum number of iterations the algorithm will do. The default value is 20. - -e e - A floating point number denoting the magnitude of the minimum force prior to terminating the algorithm. The default value is 0.01. - -rep r - A floating point number denoting the repulsive factor between nodes. The default value is 1.5. - -atr a - A floating point number denoting the attractive factor between adjacent nodes. The default value is 2. - spectral - Nodes are assigned coordinates derived from the graph's respective spectral layout.

Required Dependencies

This project was built on Julia 1.9 and requires the following Julia packages:

• JLD2 - for loading and saving vectors of graph states to the .jld format
• LinearAlgebra - Necessary for eigenvalue computations for spectral layout
• KrylovKit - Necessary for eigenvalue computations for spectral layout
• SparseArrays - Used to represent graphs in an adjacency-matrix form throughout some functions
• Plots - The foundational interface to display graphs. This project uses the GR() backend.
• MAT - Necessary to read-in relevant files of the .mat format.
• DataStructures - Recommended for the visualizations of certain algorithms

Note: Packages can be installed within the Julia REPL by pressing the ] key and typing add PackageName

Custom File Formats

VAC

VAC is a custom text file format used to store a static graph visualization. It is an acronym for Veldt-Almanza-Campbell. The first three lines in this type have the exact same content, specified below:

• Line 1 contains a single integer, corresponding to the version number. This tool only supports VAC version 1, so this number should always be 1.
• Line 2 contains a single character: either d or u, denoting whether the graph is directed or undirected, respectively.
• Line 3 contains a single character: either w or u, denoting whether the graph is weighted or unweighted, respectively.

The remainder of the file should contain $|V| + |E|$ lines. These lines always start with a single character, either n or e, to denote whether the line describes a node or edge in the graph, respectively.

Following the n character, each node line requires the specification of a node label through the use of -l NODE_LABEL, where NODE_LABEL must be a string with no spaces. As long as the label is specified, the node line may contain the following arguments: - -s SIZE - The size of the node. This value must be an integer. If not specified, the default size will be 10 plot units. - -f FILL_COLOR - The main color used for the "fill" of the node. FILL_COLOR must be a string denoting a supported color. If not specified, the default fill color will be white. - -o OUTLINE_COLOR - The color of the circular outline surrounding the fill color of the node. OUTLINE_COLOR must be a string denoting a supported color. If not specified, the default outline color will be black. - -lc LABEL_COLOR - The font color of the label. LABEL_COLOR must be a string denoting a supported color. If not specified, the default font color will be black. - -x X_COORD - The x-coordinate of the node. If not specified, it will use the default value of 0. - -y Y_COORD - The y-coordinate of the node. If not specified, it will use the default value of 0.

Following the e character, each edge line requires the specification of two values: -s SOURCE_LABEL and -d DEST_LABEL. These variables define the source and destination nodes for the respective edge. Edge lines can also contain the following arguments for further customizability: - -w WEIGHT - A floating point value defining the weight of the edge. If not specified, the default value will be 1. - -t THICKNESS - An integer defining the thickness of the line of the edge. If not specified, the default value will be 1. - -c COLOR - The color of the edge. COLOR must be a string denoting a supported color. If not specified, the default color will be black.

VACA

VACA is a custom text file format used to store a dynamic graph visualization. Although not the most space efficient, it contains a simple way of storing dynamic graph visualizations.

The first line in the file contains an integer, $S$, denoting the number of states in the graph visualization. The paper the contains $S$ sections that are essentially an enhanced VAC representation for each state. Each section has the following contents - The beginning of a new section is denoted by a line containing the string "NEXT-STATE". - We follow the "NEXT-STATE" line with the VAC representation of the graph state. - After the last line of the VAC representation, we have a line beginning with the string "LIMITS", followed by four space-separated floating point numbers, denoting $x{min}$, $x{max}$, $y{min}$ and $y{max}$, respectively. - Finally, we insert a description of the graph state with a line with the string DESC-START, followed by the description in one or more lines, which is then followed by a line with the string DESC-END.

The following is a sample of a state's representation in a VACA file. NEXT-STATE u u n -l 9 -x 1.0 -y 1.0 -f lightgrey -o black -lc black -s 20 n -l 1 -x -1.0 -y 1.0 -f lightgrey -o black -lc black -s 20 n -l 2 -x 1.0 -y -1.0 -f lightgrey -o black -lc black -s 20 n -l 3 -x -1.0 -y -1.0 -f lightgrey -o black -lc black -s 20 e -s 3 -d 2 -w 1.0 -c grey -lw 5.0 e -s 2 -d 1 -w 1.0 -c grey -lw 5.0 LIMITS -2 2 -3 3 DESC-START This is a sample state description. We can have multiple lines in the description like this! DESC-END