vinal is a Python package for visualizing graph/network algorithms. Currently, the following algorithms are implemented:
 Shortest path problem
 Minimum Spanning Tree (MST)

Travelling Salesman Problem (TSP)
 Random neighbor
 Nearest neighbor
 Nearest insertion
 Furthest insertion
 2OPT
NetworkX graphs can be constructed from a single .csv
file of node locations. Alternatively, one can specify edges of the graph by providing an additional .csv
file of edges. The package relies on bokeh to generate standalone HTML files which can be viewed in a Jupyter Notebook inline or in a web browser.
Examples
Installation
The quickest way to get started is with a pip install.
pip install vinal
Usage
First, import the vinal
package (commonly renamed to vl
).
import vinal as vl
# Calling output_notebook() makes show() display plot in a Jupyter Notebook.
# Without it, a new tab with the plot will be opened.
from bokeh.io import output_notebook, show
output_notebook() # only include if you want plot inline
All of the algorithm and plotting functions take a NetworkX graph as input. Thebuild
module provides a way of constructing NetworkX graphs from .csv
files. The standard nodes.csv
and edges.csv
files have the following form:
nodes.csv  x  y 

0  0  0 
1  1  5 
2  7  6 
3  8  6 
4  4  6 
edges.csv  u  v 

0  0  1 
1  1  2 
2  4  3 
3  3  1 
4  2  4 
Use pandas to import these .csv
files as dataframes.
import pandas as pd
nodes = pd.read_csv('nodes.csv', index_col=0)
edges = pd.read_csv('edges.csv', index_col=0)
We can now use vl.create_network()
to create a NetworkX graph.
G = vl.create_network(nodes, edges)
If an edges dataframe is not provided, the graph is assumed to be complete (every pair of nodes is connected) and the weights of each edge are determined by the euclidean distance between the pair of nodes.
G = vl.create_network(nodes)
Here, we give a summary of the various graph algorithms one can run.
#  Shortest path problem 
# Returns: List of edges in the shortest path tree
# s: index of source vertex
tree = vl.dijkstras(G, s=0)
#  Minimum Spanning Tree (MST) 
# Returns: List of edges in the shortest path tree
# i: index of initial vertex
mst = vl.prims(G, i=0)
mst = vl.kruskals(G)
mst = vl.reverse_kruskals(G)
# returns the cost of the minimum spanning tree
vl.spanning_tree_cost(G, mst)
#  Traveling Salesman Problem (TSP) 
# Returns: List of node indices in the order they are visited
# i: index of initial vertex
tour = vl.random_neighbor(G, i=0)
tour = vl.nearest_neighbor(G, i=0)
# intial_tour: initial 2node tour
tour = vl.nearest_insertion(G, intial_tour=[0,1,0])
tour = vl.furthest_insertion(G, intial_tour=[0,4,0])
# tour: initial tour to improve
tour = vl.two_opt(G, tour=tour)
# returns the cost of the tour
vl.tour_cost(G, tour)
There are four types of plots that vinal can generate:
 Static solution plots
 Noniteractive algorithm visualization plots
 Interactive create plots
 Interactive algorithm plots
After genrating a solution via one of the algorithms, a static plot of the solution can be shown. In the following example, a tour is found using nearest insertion and then plotted.
tour = vl.nearest_insertion(G, initial_tour=[0,1,0])
show(vl.tour_plot(G, tour))
If one wishes to see each iteration of the algorithm, a plot with a Previous
and Next
button can be generated. In most cases, the cost of the solution in each iteration is shown and the text "done." will appear on the final iteration. In the following example, a tour is found using random neighbor and then a plot is returned showing each iteration of the 2OPT tour improvement heuristic.
tour = vl.random neighbor(G)
show(vl.tsp_heuristic_plot(G, algorithm='2OPT', tour=tour))
Tours and spanning trees can also be constructed in a pointandclick fashion. When creating a tour, click the next node you wish to visit. When creating a spanning tree, click each edge you want in the tree.
show(vl.create_spanning_tree_plot(G))
show(vl.create_tour_plot(G))
Lastly, an interactive version of Dijkstra's algorithm and the MST algorithms can be plotted. For Dijkstra's algorithm, the user is asked to select the next node from the frontier set to explore. For the MST algorithms, the user is asked to select the next edge to be added/removed from the tree. In all cases, a helpful error message will appear when the user selects incorreclty.
show(vl.assisted_mst_algorithm_plot(G, algorithm='kruskals'))
License
This work is licensed under a
Creative Commons AttributionNonCommercialShareAlike 4.0 International License