vinal package

vinal.build module

Graph building functions

This module contains various functions used to create graphs from csv files.

vinal.build.create_network(nodes: DataFrame, edges: DataFrame | None = None, directed: bool = False, manhattan: bool = False, **kw) → Graph | DiGraph

Return networkx graph derived from the list of nodes/edges.

If no edges are given, defaults to generating all edges with weight equivalent to the euclidean distance between the nodes.

Parameters:

nodes (pd.DataFrame) – Dataframe of nodes with positional columns (x,y).
edges (pd.DataFrame) – Dataframe of edges (u,v) with weight w.
directed (bool) – True iff graph is directed (defaults to False).
manhattan (bool) – {True: manhattan distance, False : euclidian}.

Returns:

Either an undirected or directed graph.

Return type:

Union[nx.Graph, nx.DiGraph]

vinal.build.distance_matrix(nodes: DataFrame, manhattan: bool = False, x_i: str = 'x', y_i: str = 'y', x_j: str = 'x', y_j: str = 'y') → ndarray

Compute the distance matrix between the nodes.

Returns a distance matrix where entry (i,j) corresponds to the distance from the node i to node j.

Parameters:

nodes (pd.DataFrame) – Dataframe of nodes with at least (x,y) positions.
manhattan (bool) – {True: manhattan distance, False : euclidian}.
x_i (str) – Column with the x coordinate of node i (Defaults to ‘x’).
y_i (str) – Column with the y coordinate of node i (Defaults to ‘y’).
x_j (str) – Column with the x coordinate of node j (Defaults to ‘x’).
y_j (str) – Column with the y coordinate of node j (Defaults to ‘y’).

Returns:

Distance matrix between these nodes.

Return type:

np.ndarray

vinal.build.grid_instance(n: int, m: int, manhattan: bool = False) → Graph

Return a graph G representing an n x m set of nodes.

Parameters:

n (int) – width of the grid.
m (int) – height of the grid.
manhattan (bool) – {True: manhattan distance, False : euclidian}.

Returns:

Graph of n x m inter-connected nodes.

Return type:

nx.Graph

vinal.algorithms module

Graph algorithm functions

This module contains implementations of various graph algorithms.

vinal.algorithms.dijkstras(G: Graph, s: int = 0, iterations: bool = False) → List | Tuple

Run Dijkstra’s algorithm on graph G from source s.

Parameters:

G (nx.Graph) – Networkx graph.
s (int) – Source vertex to run the algorithm from. (Defaults to 0)
iterations (bool) – True iff all iterations should be returned.

Returns:

Shortest path tree edges or iterations.

Return type:

Union[List, Tuple]

vinal.algorithms.furthest_insertion(G: Graph, initial_tour: List[int] | None = None)

Run the furthest insertion heuristic on G from the initial node.

Parameters:

G (nx.Graph) – Networkx graph.
intial (List[int]) – 2-node tour to start from. (Defaults top)

Returns:

List[int] of the graph G

Return type:

List[int]

vinal.algorithms.insertion(G: Graph, initial_tour: List[int] = [0, 1, 0], nearest: bool = True, iterations: bool = False) → List[int] | List[List[int]]

Run an insertion heuristic on G starting with the initial 2-node tour.

Parameters:

G (nx.Graph) – Networkx graph.
initial_tour (List[int]) – Initial 2-node tour. (Defaults to [0,1,0])
nearest (bool) – Run nearest insertion if true. Otherwise, run random.
iterations (bool) – True iff all iterations should be returned.

Returns:

Final tour or iterations.

Return type:

Union[List[int], List[List[int]]]

vinal.algorithms.kruskals(G: Graph, iterations: bool = False) → List[Tuple[int]] | List

Run Kruskal’s algorithm on graph G.

Parameters:

G (nx.Graph) – Networkx graph.
iterations (bool) – True iff all iterations should be returned.

Returns:

Spanning tree or iterations.

Return type:

Union[List[Tuple[int]], List]

vinal.algorithms.nearest_insertion(G: Graph, initial_tour: List[int] = [0, 1, 0]) → List[int]

Run the nearest insertion heuristic on G from the initial node.

Parameters:

G (nx.Graph) – Networkx graph.
intial (List[int]) – 2-node tour to start from. (Defaults to [0,1,0])

Returns:

Tour of the graph G

Return type:

List[int]

vinal.algorithms.nearest_neighbor(G: Graph, i: int = 0) → List[int]

Run the nearest neighbor heuristic on G from the initial node.

Parameters:

G (nx.Graph) – Networkx graph.
i (int) – index of the node to start from. (Defaults to 0)

Returns:

Tour of the graph G

Return type:

List[int]

vinal.algorithms.neighbor(G: Graph, i: int = 0, nearest: bool = True, iterations: bool = False) → List[int] | List[List[int]]

Run a neighbor heuristic on G starting at the given initial node.

Parameters:

G (nx.Graph) – Networkx graph.
i (int) – Index of the node to start from. (Defaults to 0)
nearest (bool) – Run nearest neighbor if true. Otherwise, run random.
iterations (bool) – True iff all iterations should be returned.

Returns:

Final tour or iterations.

Return type:

Union[List[int], List[List[int]]]

vinal.algorithms.prims(G: <networkx.classes.graph.Graph object at 0x7fe780cf1c40>, i: int = 0, iterations: bool = False) → List[Tuple[int]] | List

Run Prim’s algorithm on graph G starting from node i.

Parameters:

G (nx.Graph) – Networkx graph.
i (int) – Index of the node to start from.
iterations (bool) – True iff all iterations should be returned.

Returns:

Spanning tree or iterations.

Return type:

Union[List[Tuple[int]], List]

vinal.algorithms.random_neighbor(G: Graph, i: int = 0) → List[int]

Run the random neighbor heuristic on G from the initial node.

Parameters:

G (nx.Graph) – Networkx graph.
i (int) – index of the node to start from. (Defaults to 0)

Returns:

Tour of the graph G

Return type:

List[int]

vinal.algorithms.reverse_kruskals(G: Graph, iterations: bool = False) → List[Tuple[int]] | List

Run reverse Kruskal’s algorithm on graph G.

Parameters:

G (nx.Graph) – Networkx graph.
iterations (bool) – True iff all iterations should be returned.

Returns:

Spanning tree or iterations.

Return type:

Union[List[Tuple[int]], List]

vinal.algorithms.spanning_tree_cost(G: Graph, tree: List[Tuple[int]]) → float

Return the cost of the given spanning tree.

Parameters:

G (nx.Graph) – Networkx graph.
tree (List[Tuple[int]]) – List of edges in the spanning tree.

Return: float: sum of the edge weights in the spanning tree.

vinal.algorithms.tour_cost(G: Graph, tour: List[int]) → float

Return the cost of the tour on graph G.

Parameters:

G (nx.Graph) – Networkx graph.
tour (List[int]) – List[int] of graph G.

Returns:

Cost of traversing the entire tour.

Return type:

float

vinal.algorithms.two_opt(G: Graph, tour: List[int], iterations: bool = False) → List[int] | Tuple

Run 2-OPT on the initial tour until no improvement can be made.

Parameters:

G (nx.Graph) – Networkx graph.
tour (List[int]) – intial tour to be improved.
iterations (bool) – True iff all iterations should be returned.

Returns:

Improved tour or iterations.

Return type:

Union[List[int], Tuple]

vinal.plot module

Plotting functions

This module contains various functions to plot graphs and algorithms.

vinal.plot.assisted_dijkstras_plot(G, s=0, **kw) → GridBox

Return a plot in which the user creates a shortest path tree from s.

Parameters:

G (nx.Graph) – Networkx graph.
s (int) – The vertex to generate a shortest path tree from.

Returns:

Plot in which the user creates a shortest path tree from s.

Return type:

GridBox

vinal.plot.assisted_mst_algorithm_plot(G: Graph, algorithm: str, **kw) → GridBox

Return a plot in which the user creates an MST with the given algorithm.

Parameters:

G (nx.Graph) – Networkx graph.
algorithm (str) – {‘prims’, ‘kruskals’, ‘reverse_kruskals’}

Returns:

Plot in which the user creates an MST with given algorithm.

Return type:

GridBox

vinal.plot.create_spanning_tree_plot(G: Graph, **kw) → GridBox

Return a plot in which you can create a spanning tree.

Parameters:: G (nx.Graph) – Networkx graph.
Returns:: Plot in which you can create a spanning tree.
Return type:: GridBox

vinal.plot.create_tour_plot(G: Graph, **kw) → GridBox

Return a plot in which you can create a tour.

Parameters:: G (nx.Graph) – Networkx graph.

Rerturns:: GridBox: Plot in which you can create a tour.

vinal.plot.dijkstras_plot(G: Graph, s: int = 0, **kw) → GridBox

Return plot of Dijkstra’s algorithm running on graph G with source s.

Parameters:

G (nx.Graph) – Networkx graph.
s (int) – Source vertex to run the algorithm from. (Defaults to 0)

Returns:

Plot of Dijkstra’s algorithm running on graph G with source s.

Return type:

GridBox

vinal.plot.mst_algorithm_plot(G: Graph, algorithm: str, **kw) → GridBox

Return plot of the given MST algorithm running on the graph G.

Parameters:

G (nx.Graph) – Networkx graph.
algorithm (str) – {‘prims’, ‘kruskals’, ‘reverse_kruskals’}

Returns:

Plot of the given MST algorithm running on the graph G.

Return type:

GridBox

vinal.plot.tour_plot(G: Graph, tour: List[int], **kw) → GridBox

Return a plot of the tour on graph G.

Parameters:

G (nx.Graph) – Networkx graph.
tour (List[int]) – Tour of the graph.

Returns:

Plot of the tour on graph G.

Return type:

GridBox

vinal.plot.tree_plot(G: Graph, tree: List[Tuple[int]], show_cost: bool = False, **kw)

Return a plot of the tree on graph G.

Parameters:

G (nx.Graph) – Networkx graph.
tree (List[int]) – List of edges in the tree.
show_cost (bool) – True if cost of tree should be shown on plot.

Returns:

Plot of the tree on graph G.

Return type:

GridBox

vinal.plot.tsp_heuristic_plot(G: Graph, algorithm: str, **kw) → GridBox

Return a plot of the given TSP heuristic running on G.

Parameters:

G (nx.Graph) – Networkx graph.
algorithm (str) – {‘random_neighbor’, ‘nearest_neighbor’, ‘nearest_insertion’, ‘furthest_insertion’, ‘2-OPT’}

Returns:

Plot of the given TSP heuristic running on G.

Return type:

GridBox