graph-theoryhamiltonian-cycle
Fast Hamiltonian cycle calculation
Suppose that there is a directed graph consists of vertices named below:
"ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD",
"BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD",
"CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA", "DCB"
These are the 3 letter permutations over 4 different letters. (total = 4*3*2=24)
Name of vertices also describes edges between them. Any two vertices are connected to each other if last two character of source is equal to first two character of destination such as
ABC -> BCD
or
DCB -> CBA
The graph is very similar to De Burjin's or Kautz's, but not same. It is strongly connected and I know that it has Hamiltonian cycle.
To solve the problem, I'm not an expert at algorithms, I simply went through latest boost graph library and found hawick_unique_circuits() function which enumerates all cycles and here is my example codes:
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/hawick_circuits.hpp>
#include "combination.hpp" // from http://howardhinnant.github.io/combinations.html
using namespace std;
using namespace boost;
typedef boost::adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, uint32_t> > TGraph;
TGraph m_Graph;
vector<string> m_StrVertexList;
void CreateStringVertexList(vector<string>& vl, uint32_t n, uint32_t k)
{
vl.clear();
if ((k > 0) && (n > k))
{
string code = "A";
while (--n)
{
code += code.back() + 1;
}
// for_each_permutation from Howard Hinnant
// http://howardhinnant.github.io/combinations.html
for_each_permutation(code.begin(), code.begin() + k, code.end(),
[&](string::iterator first, string::iterator last)->bool{ vl.push_back(string(first, last)); return(false); });
}
}
void AddEdgesFromStringVertex(TGraph& g, const vector<string>& vl)
{
uint32_t connection_len = vl.begin()->size() - 1;
g.clear();
for (uint32_t f = 0; f < vl.size(); f++)
for (uint32_t t = 0; t < vl.size(); t++)
{
if ((f != t) &&
(vl[f].substr(1, connection_len) == vl[t].substr(0, connection_len)))
{
add_edge(f, t, 1, g);
}
}
}
class hawick_visitor
{
public:
void cycle(const vector<TGraph::vertex_descriptor>& circuit, const TGraph& graph) const
{
if (circuit.size() == m_StrVertexList.size())
{
for (auto ii = circuit.begin(); ii != circuit.end(); ++ii)
{
cout << m_StrVertexList[*ii] << " -> ";
}
cout << endl;
}
}
};
void Circuits(const TGraph& g)
{
hawick_unique_circuits(g, hawick_visitor());
cout << "- end of hawick_unique_circuits() -" << endl;
}
void main(void)
{
//CreateStringVertexList(m_StrVertexList, 10, 4);
CreateStringVertexList(m_StrVertexList, 4, 3);
AddEdgesFromStringVertex(m_Graph, m_StrVertexList);
Circuits(m_Graph);
}
hawick_visitor class simply checks whether cycle found has same vertices as Graph's. If it has, that means we find one of Hamiltonian cycle we need.
It works perfectly for 24 vertices which is 3 char chosen from 4 unique char and here is one of outputs:
ABC -> BCA -> CAD -> ADB -> DBC -> BCD -> CDA -> DAC ->
ACB -> CBD -> BDC -> DCB -> CBA -> BAC -> ACD -> CDB ->
DBA -> BAD -> ADC -> DCA -> CAB -> ABD -> BDA -> DAB -> ABC
But when I try to solve similar graph has 5040 vertices named as 4 char chosen from 10 unique char, this function never returns. There should be a far better algorithm than hawick_unique_circuits() to do that. Because I know people doing similar calculation for 10,000 vertices less than a minute, but I don't know how. Any idea highly appreciated.
Here is the graph has 5040 vertices that I need to solve:
Solution
Hamiltonian cycle from your graph: http://figshare.com/articles/Hamiltonian_Cycle/1228800
How to find Hamiltonian cycle in your graph in C#:
First file:
using System;
using System.Collections.Generic;
namespace Graph
{
partial class Program
{
static List<string> vertices;
static void Main(string[] args)
{
List<int>[] graph = GetGraph();
List<int> HamiltonianCycle = Algorithm(graph);
string a = Translate(HamiltonianCycle);
Console.Write(a);
Console.ReadKey();
}
static List<int>[] GetGraph()
{
List<string> list = new List<string>(){"A","B","C","D","E","F","G","H","I","J"};
vertices = new List<string>();
for(int a=0;a<10;++a)
for(int b=0;b<10;++b)
for(int c=0;c<10;++c)
for(int d=0;d<10;++d)
{
if(a==b || a== c || a==d || b == c || b == d|| c==d)
continue;
string vertex = list[a] + list[b] + list[c] + list[d];
vertices.Add(vertex);
}
List<int>[] graph = new List<int>[vertices.Count];
for(int i=0;i<graph.Length;++i)
graph[i] = new List<int>();
foreach(string s1 in vertices)
foreach(string s2 in vertices)
if(s1 != s2)
if(s1[s1.Length-3] == s2[0] && s1[s1.Length-2] == s2[1] && s1[s1.Length-1] == s2[2])
{
int v1 = vertices.IndexOf(s1);
int v2 = vertices.IndexOf(s2);
graph[v1].Add(v2);
}
return graph;
}
static string Translate(List<int> HamiltonianCycle)
{
string a = "";
foreach(int b in HamiltonianCycle)
a += vertices[b] + " -> ";
return a;
}
}
}
Second file:
using System;
using System.Collections.Generic;
using System.Linq;
namespace Graph
{
partial class Program
{
static List<int>[] graph, oppositeGraph;
static List<int> HamiltonianCycle;
static bool endOfAlgorithm;
static int level, v1, v2;
static List<int> Algorithm(List<int>[] graphArgument)
{
graph = SaveGraph(graphArgument);
HamiltonianCycle = new List<int>();
endOfAlgorithm = false;
level = 0;
RemoveMultipleEdgesAndLoops(graph); //3.1
CreateOppositeGraph(graph);
bool HamiltonianCycleCantExist = AnalyzeGraph(new List<Edge>()); //6.1.a
ReverseGraph();
if (!HamiltonianCycleCantExist)
FindHamiltonianCycle(GetNextVertex()); //5.3
HamiltonianCycle.Reverse();
return HamiltonianCycle;
}
static void ReverseGraph()
{
graph = SaveGraph(oppositeGraph);
CreateOppositeGraph(graph);
}
static void FindHamiltonianCycle(int a)
{
if (!endOfAlgorithm)
{
++level;
if (HamiltonianCycleFound())
endOfAlgorithm = true;
SortList(a); //5.4
while (graph[a].Count > 0 && !endOfAlgorithm)
{
List<Edge> removedEdges = new List<Edge>();
int chosenVertex = graph[a][0];
graph[a].Remove(chosenVertex);
List<int>[] currentGraph = SaveGraph(graph);
#region 6.2
foreach (int b in graph[a])
{
removedEdges.Add(new Edge(a, b));
oppositeGraph[b].Remove(a);
}
graph[a].Clear();
#endregion
graph[a].Add(chosenVertex);
v1 = a;
v2 = chosenVertex;
bool HamiltonianCycleCantExist = AnalyzeGraph(removedEdges); //6.1.b
if (!HamiltonianCycleCantExist)
{
FindHamiltonianCycle(GetNextVertex()); //5.5
RestoreGraphs(currentGraph); //6.4
}
else
{
foreach (Edge e in removedEdges) //6.3
{
graph[e.from].Add(e.to);
oppositeGraph[e.to].Add(e.from);
}
RemoveEdge(new Edge(a, chosenVertex), graph, oppositeGraph);
}
}
if (!endOfAlgorithm)
{
--level;
if (level == 0)
endOfAlgorithm = true;
}
}
}
static bool HamiltonianCycleFound()
{
foreach (List<int> list in graph)
if (list.Count != 1)
return false;
HamiltonianCycle = GetHamiltonianCycle(graph);
return true;
}
static List<int> GetHamiltonianCycle(List<int>[] graphArgument)
{
List<int> cycle = new List<int>() { 0 };
while (true)
{
if (cycle.Count == graphArgument.Length && graphArgument[cycle.Last()].Contains(cycle[0]))
return cycle;
if (cycle.Contains(graphArgument[cycle.Last()][0]))
return new List<int>();
else
cycle.Add(graphArgument[cycle.Last()][0]);
}
}
static int GetNextVertex()
{
List<int> correctOrder = GetCorrectOrder(graph);
foreach (int a in correctOrder)
if (graph[a].Count != 1)
return a;
return 0;
}
static bool AnalyzeGraph(List<Edge> removedEdges)
{
bool HamiltonianCycleCantExist = false;
int a;
do
{
a = removedEdges.Count;
HamiltonianCycleCantExist = RemoveUnnecessaryEdges(graph, oppositeGraph, removedEdges, false);
if (!HamiltonianCycleCantExist)
HamiltonianCycleCantExist = RemoveUnnecessaryEdges(oppositeGraph, graph, removedEdges, true);
}
while (a != removedEdges.Count && !HamiltonianCycleCantExist);
if (!HamiltonianCycleCantExist)
HamiltonianCycleCantExist = GraphIsDisconnected(graph);
return HamiltonianCycleCantExist;
}
static bool RemoveUnnecessaryEdges(List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges, bool oppositeGraph)
{
bool HamiltonianCycleCantExist = false;
for (int a = 0; a < graphArgument.Length; ++a)
{
if (graphArgument[a].Count == 0 //4.1
|| (graphArgument[a].Count == 1 && SearchForCycleAmongVerticesOfDegreeEqual1(graphArgument, a)) //4.2.1
|| (graphArgument[a].Count > 1 && SearchForCycleAmongVerticesOfDegreeGreaterThan1(a, graphArgument, oppositeGraphArgument))) //4.2.2
return true;
List<Edge> edges = new List<Edge>();
#region 3.2
if (graphArgument[a].Count == 1 && oppositeGraphArgument[graphArgument[a][0]].Count != 1)
{
foreach (int c in oppositeGraphArgument[graphArgument[a][0]])
if (c != a)
if (!oppositeGraph)
edges.Add(new Edge(c, graphArgument[a][0]));
else
edges.Add(new Edge(graphArgument[a][0], c));
}
#endregion
#region 3.4
if (graphArgument[a].Count == 1 && graphArgument[graphArgument[a][0]].Contains(a))
{
if (!oppositeGraph)
edges.Add(new Edge(graphArgument[a][0], a));
else
edges.Add(new Edge(a, graphArgument[a][0]));
}
#endregion
foreach (Edge edge in edges)
{
removedEdges.Add(edge);
if (!oppositeGraph)
RemoveEdge(edge, graphArgument, oppositeGraphArgument);
else
RemoveEdge(edge, oppositeGraphArgument, graphArgument);
}
}
return HamiltonianCycleCantExist;
}
static bool SearchForCycleAmongVerticesOfDegreeEqual1(List<int>[] graphArgument, int a)
{
if(!(a==v1 || a == v2))
return false;
List<int> cycle = new List<int>() { a };
while (true)
if (graphArgument[cycle.Last()].Count == 1 && cycle.Count < graphArgument.Length)
if (cycle.Contains(graphArgument[cycle.Last()][0]))
return true;
else
cycle.Add(graphArgument[cycle.Last()][0]);
else
return false;
}
static bool SearchForCycleAmongVerticesOfDegreeGreaterThan1(int a, List<int>[] graphArgument, List<int>[] oppossiteGraphArgument)
{
if (!ListsAreEqual(graphArgument[a], oppossiteGraphArgument[a], true))
return false;
int b = 1;
for (int c = 0; c < graphArgument.Length && graphArgument.Length - c > graphArgument[a].Count - b; ++c)
{
if (c == a)
continue;
if (ListsAreEqual(graphArgument[c], graphArgument[a], false) && ListsAreEqual(graphArgument[c], oppossiteGraphArgument[c], true))
++b;
if (b == graphArgument[a].Count)
return true;
}
return false;
}
static bool ListsAreEqual(List<int> firstList, List<int> secondList, bool EqualCount)
{
if (EqualCount && firstList.Count != secondList.Count)
return false;
foreach (int a in firstList)
if (!secondList.Contains(a))
return false;
return true;
}
static void SortList(int a)
{
List<int> correctOrder = GetCorrectOrder(oppositeGraph);
for (int b = 1; b < graph[a].Count; ++b)
for (int c = 0; c < graph[a].Count - 1; ++c)
if (correctOrder.IndexOf(graph[a][c]) > correctOrder.IndexOf(graph[a][c + 1]))
{
int n = graph[a][c];
graph[a][c] = graph[a][c + 1];
graph[a][c + 1] = n;
}
}
static List<int> GetCorrectOrder(List<int>[] graphArgument) //5.1
{
Dictionary<int, int> vertices = new Dictionary<int, int>();
List<int> order = new List<int>();
for (int a = 0; a < graphArgument.Length; ++a)
vertices.Add(a, graphArgument[a].Count);
IEnumerable<int> v = from pair in vertices orderby pair.Value ascending select pair.Key;
foreach (int a in v)
order.Add(a);
return order;
}
static void RemoveEdge(Edge e, List<int>[] graphArgument, List<int>[] oppositeGraphArgument)
{
graphArgument[e.from].Remove(e.to);
oppositeGraphArgument[e.to].Remove(e.from);
}
static void RemoveMultipleEdgesAndLoops(List<int>[] graphArgument)
{
for (int a = 0; a < graphArgument.Length; ++a)
{
graphArgument[a] = graphArgument[a].Distinct().ToList();
graphArgument[a].Remove(a);
}
}
static void CreateOppositeGraph(List<int>[] graphArgument)
{
oppositeGraph = new List<int>[graphArgument.Length];
for (int a = 0; a < graphArgument.Length; ++a)
oppositeGraph[a] = new List<int>();
for (int a = 0; a < graphArgument.Length; ++a)
foreach (int b in graphArgument[a])
oppositeGraph[b].Add(a);
}
static void RestoreGraphs(List<int>[] graphArgument)
{
graph = new List<int>[graphArgument.Length];
for (int a = 0; a < graphArgument.Length; ++a)
{
graph[a] = new List<int>();
graph[a].AddRange(graphArgument[a]);
}
CreateOppositeGraph(graph);
}
static List<int>[] SaveGraph(List<int>[] graphArgument)
{
List<int>[] savedGraph = new List<int>[graphArgument.Length];
for (int a = 0; a < graphArgument.Length; ++a)
{
savedGraph[a] = new List<int>();
savedGraph[a].AddRange(graphArgument[a]);
}
return savedGraph;
}
static bool GraphIsDisconnected(List<int>[] graphArgument)
{
Stack<int> stack = new Stack<int>();
Color[] colors = new Color[graphArgument.Length];
colors[0] = Color.Gray;
stack.Push(0);
while (stack.Count > 0)
{
int a = stack.Pop();
foreach (int b in graphArgument[a])
{
if (colors[b] == Color.White)
{
colors[b] = Color.Gray;
stack.Push(b);
}
}
colors[a] = Color.Black;
}
foreach (Color c in colors)
if (c != Color.Black)
return true;
return false;
}
}
class Edge
{
public int from, to;
public Edge(int f, int t)
{
from = f;
to = t;
}
}
enum Color { White, Gray, Black };
}
I found Hamilonian cycle with modified version of my algorithm: http://arxiv.org/abs/1405.6347 Modifications that were made are:
- Algorithm searched in opposite graph
- Algorithm tested if graph is disconnected
- Algorithm did not test "unique neighbours" rule
- Algorithm searched for cycles that are not Hamiltonian, starting only from vertices that creates currently visited edge - only in function SearchForCycleAmongVerticesOfDegreeEqual1
- Depth First Search v.s. Greedy Best First Search
- If every strongly connected component has only one incoming edge each from outside, is that necessary and sufficient for a reducible graph?
- Brent's cycle detection algorithm
- Using multi-indexing to find all combinations matching a certain pattern
- Assigning codes to nodes such that codes are unique and create two groups which share common properties
- Finding lowest common ancestor for more than two nodes
- Prove or disprove: there exists three vertexes a,b,c in a connected but incomplete graph satisfying a and b have a common neighbor c
- How to draw a node in some given coordinates
- Optimal map printing algorithm
- How accurate is Dijkstra Algorithm?
- Create a tree structure from a graph
- All possible maximum matchings of a bipartite graph
- Map exploration/path planning for multiple robots (no obstacles)
- Struggling with Shortest Path Calculation in Graph with Special Edge Weights
- Find number of redundant edges in components of a graph
- Get the most optimal combination of places from a list of places through graph algorithm
- Graph Theory: Splitting a Graph
- Minimal path on weighted tree query
- Minimum edges to form path with length L
- What is the complexity of the following code? Is it O(n^3log(n))?
- Efficient algorithm for detecting cycles in a directed graph
- Construct adjacency matrix in MATLAB
- Linear time algorithm for computing radius of membership hyper-sphere
- How to find all simple paths of no more than k lengths starting at a vertex in a directed graph?
- Delete from child table on update of parent row with composite foreign key
- Topological sort not printing all vertexes
- Tarjan Algorithms for SCC
- Given a set of edges and an undirected graph, how do I pick the best edge to add to graph to minimize the shortest path?
- Is there an algorithm to determine the faces of a planar graph?
- How can I correct the error ' AttributeError: 'dict_keys' object has no attribute 'remove' '?