Let's start out with a clean table. Here we go.
Vertex/Mask |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Step 1: Initial Setup
The first step is to look at columns where the binary
Hamming Weight (number of bits set to 1) is 1.
Since those sub-problems only have 1 node in them, they are
"1" by default. This is for 0001, 0010, 0100, and 1000.
Vertex/Mask |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Step 2: Column Generation
Next, we will start generating cell values on a column-by-column basis.
This will apply for all columns where the binary Hamming Weight
is 2 or more. Therefore, we will skip 0-2 and start at mask
0x3 (0011). Here is how our graph will look:
The nodes that are not in the mask are transparent. Since it's
mask 0x3, only nodes 0 and 1 are involved.
Remember how we talked about how if A --> B and B --> C, then
there exists a path of A --> B --> C? We can take advantage of
this property by using this table.
For all nodes involved (0 and 1), rather than check paths by
using a DFS or brute force method, we can cheat and use previous
columns to check if there is a path that exists and goes to the
cell in question. This is better taught by example so...
For Node 0:
- Go to mask of same value except without node 0 (0011 XOR 0001 = 0010)
- At mask 0010, check all cells set to 1 and see if those vertices can go to 0.
- Vertex 1 at mask 0010 is set to "1" and it can go to 0. Set the cell to 1.
This is our table currently. Notice something new?
Vertex/Mask |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Why this works: We go to a mask where we know there is a
path between certain nodes that exist, but doesn't include the
one we are checking (mask 0010 doesn't have node 0). Then we
see if any of the nodes in that mask
can go to that
node. If there is a path from any node to it, set it to 1.
Even more simply put:
If we were checking for a path for C, and we know there's a path
of A --> B and B --> C, go to the mask that doesn't have C
and check if either A or B go to C. If either does, we know a path
exists between all 3.
So we did the part for Node 0, but mask 3 also involves Node 1.
So let's do that one too.
For Node 1:
- Go to mask of same value except without node 1 (0011 XOR 0010 = 0001)
- At mask 0001, check all cells set to 1 and see if those vertices can go to 1.
- Vertex 0 at mask 0001 is set to "1" and it can go to 1. Set the cell to 1.
And here's our updated table:
Vertex/Mask |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Perfect! Repeat the procedure for all cells of all columns
where the Hamming Weight is 2 or more and you're done. This
means you'll be doing this procedure for the following
columns: 5, 6, 7, 9, A, B, C, D, E, F. That's pretty tedious.
Here's the completed table, once again.
Vertex/Mask |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
2 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Step 3: Determining a Hamiltonian Path's existence
Let's look at mask F (1111) again. If there are any 1's in that
column, there exists a Hamiltonian Path in the graph! But
that's not all. We can also determine where the path ends from
the table. If the first cell at the top is "1", then there
exists a Hamiltonian Path that ends at Vertex 0.
From what I can see, all 4 cells in that column are set to "1".
This means there are Hamiltonian Paths that end at all vertices
in the graph! That's pretty nice, but there are a few problems
to this approach for the problem we are trying to solve...