### 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**|![A visualization of the BFS algorithm output by this project.](./algorithms/BFS/bfs.gif)|
|**Kruskal's Minimum Spanning Tree Algorithm**|![A visualization of Kruskal's algorithm output by this project.](./algorithms/Kruskal/kruskal.gif)|
|**Dijkstra's Single-Source Shortest Path Algorithm**|![A visualization of Dijkstra's algorithm output by this project.](./algorithms/Dijkstra/dijkstra.gif)|

### 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](https://www.cs.cmu.edu/afs/cs/user/glmiller/public/Scientific-Computing/F-11/RelatedWork/Spielman/SpectTut.pdf).


### 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
```