Repository files navigation

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 onbokeh to generate standalone HTML files which can be viewed in a Jupyter Notebook inline or in a web browser.

The quickest way to get started is with a pip install.

pip install vinal

First, import thevinal package (commonly renamed tovl).

importvinalasvl# Calling output_notebook() makes show() display plot in a Jupyter Notebook.# Without it, a new tab with the plot will be opened.frombokeh.ioimportoutput_notebook,showoutput_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 standardnodes.csv andedges.csv files have the following form:

Use pandas to import these.csv files as dataframes.

importpandasaspdnodes=pd.read_csv('nodes.csv',index_col=0)edges=pd.read_csv('edges.csv',index_col=0)

We can now usevl.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 vertextree=vl.dijkstras(G,s=0)# ----- Minimum Spanning Tree (MST) -----# Returns: List of edges in the shortest path tree# i: index of initial vertexmst=vl.prims(G,i=0)mst=vl.kruskals(G)mst=vl.reverse_kruskals(G)# returns the cost of the minimum spanning treevl.spanning_tree_cost(G,mst)# ----- Traveling Salesman Problem (TSP) -----# Returns: List of node indices in the order they are visited# i: index of initial vertextour=vl.random_neighbor(G,i=0)tour=vl.nearest_neighbor(G,i=0)# intial_tour: initial 2-node tourtour=vl.nearest_insertion(G,intial_tour=[0,1,0])tour=vl.furthest_insertion(G,intial_tour=[0,4,0])# tour: initial tour to improvetour=vl.two_opt(G,tour=tour)# returns the cost of the tourvl.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 aPrevious andNext 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.randomneighbor(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'))

This work is licensed under aCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International License