Introduction
Hamiltonian Cycle
is about finding a path in an undirected or directed graph that visits
each node exactly once and cycle back to the source node. All the nodes in
the graph should be visited. Reference
from Wikipedia.
Inside the Hamiltonian Cycle
path, the starting node and destination node are the same; each node inside
the path only occur once.
Hamiltonian
Cycle do not consider about total traveling distance. Therefore,
Hamiltonian Cycle may not be used to solve Travelling
salesman problem. Travelling
salesman problem takes in the considerations of costs & times
associated with total traveling distance.
Because Hamiltonian Cycle do not consider about traveling distance,
the program below will use brute force / trial-and-check method to derive
Hamiltonian Cycle. Lists out all the possible paths and only print-out
those paths that visited all nodes exactly once. The start node and
destination node are the same in Hamiltonian Cycle paths.
Hamiltonian Cycle
path (Wikipedia reference)
Hamiltonian Cycle
paths (Wikipedia reference)
‘Graph4.txt’
‘Graph5.txt’
Visual c++ Console App
Each row in Graph4.txt,
Graph5.txt
refer to the respective nodes. First row represent node ‘0’, forth row
represent node ‘3’.
Each row contains
single or multiple pair of integers. In an integer pair, first integer is
the adjacent node ID; second integer is the traveling distance from current
node to this adjacent node.
The code below will
print out all the paths that fulfill Hamiltonian Cycle. Subsequently it
will also print-out all the paths that have same start node and destination
node.
In these Graph4.txt,
Graph5.txt
examples, start node / source node is set to ‘0’;
destination node / end node is ‘0’ too.
Version 0: HamiltonianCycle_rev0.cpp Graph4.txt Graph5.txt
Hemiltonian Cycle Path with cheapest total
gas cost considerations
In
this example code, Hemiltonian Cycle paths will
be taken in consideration of vehicle travelling gas cost.
The
example code uses trial-and-error approach to derive the cheapest
refillable gas amount at each gas station for every possible Hemiltonian Cycle path. Try every refill gas amount
(each time increment 1 liter) at each gas station and compute the total gas
cost. Finally the code will choose the grant cheapest Hemiltonian
Cycle path among all the possible Hemiltonian
Cycle path.
This
code is similar to ‘To
Fill or not to Fill: The Gas Stations Problem’, except this time we
presume starting node has gas station.
In
this code, we need to set ‘IS_HAMILTONIAN_CYCLE’ parameter to true if we
want to derive Hamiltonian Cycle paths. Because Hamiltonian Cycle paths
will have ‘total node count + 1’, different from ‘non-Hamiltonian Cycle
paths’ graph derivations. If we set ‘IS_HAMILTONIAN_CYCLE’ parameter to
false, the code will print-out all the paths from starting node to
designated destination node. Regardless whether the paths are Hamiltonian
Cycle paths.
‘Graph4_GasStation.txt’
‘Graph5_GasStation.txt’
Visual c++ Console App
Each row in Graph4_GasStation.txt,
Graph5_GasStation.txt
refer to the respective nodes. First row represent node ‘0’, forth row
represent node ‘3’.
Each row the first
float number is the current node’s gas station price. Subsequent values
contain single or multiple integer+float number
pair. In integer+float number pair, first integer
is the adjacent node ID; float number is the traveling distance from
current node to this adjacent node.
After set
‘IS_HAMILTONIAN_CYCLE’ parameter to true, the below code
will print out all the paths that fulfill Hamiltonian
Cycle. Also, the code will print-out the optimum refill gas amount at each
gas station to achieve cheapest total gas cost.
In these Graph4_GasStation.txt,
Graph5_GasStation.txt
examples, start node / source node is set to ‘0’;
destination node / end node is ‘0’ too.
Version 0: using
brute force to calculate gas cost
Try every possible
combination of gas refill amount and choose the cheapest gas refill
combinations for each path. Finally choose the grand cheapest gas cost from
all the possible routes.
This method is slow
and time consuming.
single threaded: HamiltonianCycle_GasStation_rev0.cpp Graph4_GasStation.txt Graph5_GasStation.txt
Version 1:
alternate and faster way to calculate gas cost
These is an
alternate and faster way to derive optimum gas refill amount at each gas
station.
Vehicle with full
gas tank travel a limited distance. Driver objective is to pump the most
gas at the cheapest and reachable gas station. That’s means within vehicle
reachable distance, driver will come across few gas stations. Driver will
pump as much gas as possible at the cheapest gas station among these
reachable gas stations.
Hence driver just
need to make sure his vehicle has enough gas inside gas tank to reach the
next reachable and cheapest gas station. By using this method, we can
derive the optimum gas refill amount at every gas station.
Finally choose the
grand cheapest gas cost from all the possible routes.
This method is
faster and efficient than version 0 brute force method.
single threaded: HamiltonianCycle_GasStation_rev1.cpp Graph4_GasStation.txt Graph5_GasStation.txt Graph7_GasStation.txt
‘Graph7_GasStation.txt’
|