graph-theory - 快速哈密顿循环计算

Question

假设有一个有向图由以下命名的顶点组成:

"ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD",
"BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD",
"CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA", "DCB"

这些是 4 个不同字母的 3 个字母排列。 (总计 = 4*3*2=24)顶点名称还描述了它们之间的边。如果源的最后两个字符等于目标的前两个字符，则任意两个顶点相互连接，例如

ABC -> BCD

或

DCB -> CBA

该图与 De Burjin 或 Kautz 的非常相似，但又不相同。它是强连通的，我知道它有哈密顿循环。

为了解决这个问题，我不是算法专家，我只是浏览了最新的 boost 图形库并找到了 hawick_unique_circuits() 函数，它枚举了所有循环，这是我的示例代码:

#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 类只是检查找到的循环是否具有与 Graph 相同的顶点。如果有，则意味着我们找到了我们需要的哈密顿循环之一。

它非常适用于 24 个顶点，即从 4 个唯一字符中选择的 3 个字符，这是输出之一:

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

但是当我尝试解决类似的图形有 5040 个顶点命名为从 10 个唯一字符中选择的 4 个字符时，此函数永远不会返回。应该有比 hawick_unique_circuits() 更好的算法来做到这一点。因为我知道有人在不到一分钟的时间内对 10,000 个顶点进行类似的计算，但我不知道怎么做。非常感谢任何想法。

这是我需要解决的具有 5040 个顶点的图:

Answer 1

图表中的哈密顿循环:http://figshare.com/articles/Hamiltonian_Cycle/1228800

如何在 C# 中找到图中的哈密顿循环:

第一个文件:

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;
        }
    }
}

第二个文件:

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 };
}

我用我的算法的修改版本找到了哈密尔顿循环:http://arxiv.org/abs/1405.6347所做的修改是:

• 在相反图中搜索的算法
• 如果图断开则测试算法
• 算法没有测试“唯一邻居”规则
• 算法搜索非哈密顿量的循环，仅从创建当前访问的边的顶点开始 - 仅在函数 SearchForCycleAmongVerticesOfDegreeEqual1 中