vinal 0.0.6

A Python package for visualizing graph algorithms.

vinal is a Python package for visualizing graph/network algorithms. Currently, the following algorithms are implemented:

• Shortest path problem
  • Dijkstra's algorithm
• Minimum Spanning Tree (MST)
  • Prim's Algorithm
  • Kruskal's Algorithm
  • Reverse Kruskal's Algorithm
• Travelling Salesman Problem (TSP)
  • Random neighbor
  • Nearest neighbor
  • Nearest insertion
  • Furthest insertion
  • 2-OPT

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 2-node 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
• Non-iteractive 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 2-OPT tour improvement heuristic.

tour = vl.random neighbor(G)
show(vl.tsp_heuristic_plot(G, algorithm='2-OPT', tour=tour))

Tours and spanning trees can also be constructed in a point-and-click 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 Attribution-NonCommercial-ShareAlike 4.0 International License