Repository contains demo code(with sample input graphs) to reduce a given graph with Rudrata/Hamiltonian cycles to a Traveling Saleseman(TSP) Problem.
Transforming an instance of the Rudrata/ Hamiltonian cycle problem into an instance of the TSP problem, demonstrates that if a polynomial-time algorithm exists for the TSP, then one exists for the Rudata/ Hamiltonian cycle problem. This reduction is crucial in showing the NP-completeness of the TSP, as the Rudrata/Hamiltonian cycle problem is known to be NP-complete. To better understand the concepts involved, the graphs are visualized using a simple interface built using 3D-Force-Directed graphs.
Rudrata/Hamiltonian Cycle: A cycle in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. It's essentially a closed path that covers all the nodes of the graph without repeating any node (except the starting and ending vertex).
The Traveling Salesman(TSP) Problem: finding the shortest possible route that visits a set of locations (cities) exactly once and returns to the starting location. This problem is NP-hard, meaning the computational time to find the shortest path increases exponentially with the number of locations.
NP (Nondeterministic Polynomial-time) problems: A class of problems where a potential solution can be verified quickly, but finding the solution itself might take a long time or be computationally complex. In simpler terms, it is easy to check if a solution to the problem is correct, but it might be difficult or impossible to find the correct one efficiently.
NP-hard: problems that are at least as hard as the hardest problems in NP, meaning any problem in NP can be reduced to them. NP-hard problems are not restricted to being in NP. They can be outside of NP as well, i.e, their verification might not be possible in polynomial time.
NP-complete: A problem is NP-complete if it's both in NP and NP-hard (A hard problem in NP that can be used to solve any other problem in NP)
A CSV file consists of a first row of node names (vertex IDs) followed by an adjacency matrix representing the undirected edges. The matrix should be an N times N matrix where N is the number of nodes contained in the graph. This adjacency matrix would consist of either a 1 or a 0 at a particular index where 1 implies an existing edge and 0 implies none. The provided edges should be undirected and self edges should be set to 0. The minimum number of vertices to be provided is at least 3 and the maximum vertices should not exceed 16.
Sample valid and invalid csv input formats can be found in the test_graphs/ directory.
Alternatively users can use a clickable grid matrix that creates the csv file with numbered vertices as the file header.
The transformation algorithm from RUDRATA to TSP involves creating a complete weighted undirected graph G' from the given input graph G. Existing edges are assigned a weight of 1, and missing edges are added with a weight of 1 + alpha, where alpha is the number of vertices in G.
- Graph Completion: Adds missing edges with weight 1 + alpha to make the input graph complete.
- Edge Weight Adjustment: Maintains existing edges with a weight of 1.
- Backtracking Algorithm: A simple backtracking algorithm is used to find tours within a specified budget (number of vertices in G).
- Tour Verification: Checks if a tour can be completed within the budget without using any added edges.
The python script rudrata\hamiltonian_visualization.py transforms the input graph csv file present at the given file path to a complete graph and employs logic to detect the existance of a rudrata/hamiltonian cycle.
The python script rudrata\graph_visualization.py contains the logic to convert pandas dataframe objects to valid json format. The json files are then visualized using 3D Force-Directed Graph repository
Clone the repository to your local machine and run the following commands,
#Install Flask and other dependencies
pip install Flask
# Change to the appropriate directory
cd rudrata
# Start the Flask application
python app.py- BROWSER (Prefereed) - Microsoft Edge(Version 123.0.+)
- Python 3.11
- JavaScript ES 6
- Pandas 1.5.3
- Flask 2.2.2
The HTML rudrata\templates\initial.html contains a template to the homepage that accepts user input, and rudrata\templates\rudrataviz.html contains a template to visualize the transformations. These templates can be manipulated to edit the webapp elements as per the requirement/preference.
- You are welcome to use and modify this code.
Note: Repository also uses code files from a external library https://github.com/vasturiano/3d-force-graph to visualize graphs. Please use proper refernces/citations for the same.
3D-Force-Directed-Graphs by Vasco Asturiano: Author Github - https://github.com/vasturiano