Найдите, если случайно сгенерированный неориентированный простой граф имеет гамильтонов цикл

Question

Я знаю, что этот вопрос задавался десятки раз раньше, но я пытался следовать нескольким различным руководствам и не могу понять, почему мой конкретный алгоритм не работает.

Вот код:

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

#The reason we went with this algorithm instad of filling a matrix with random int from 0,1 to begin with is because this is always a simple graph, while
#the other approach almost never makes one. So, rather than checking and fixing those graphs, we thought this would be faster and easier
def makeGraph(order):
    p = .5 #represents the probability of an edge being created between any 2 verticies, if less than .4 its almost never connected for values 10+.
    g = nx.erdos_renyi_graph(order, p) #generates the graph, verticies are 0-order, edges are ordered pairs of these numbers
    return g

def Hamiltonian(matrix, order, path, currentVertex):
    while(True):
        if(currentVertex >= order):
            print("There is no H cycle")
            return
        checkVertex(matrix, order, path, currentVertex)
        if(path[currentVertex] == 0):
            print("There is no H cycle")
            return
        if(currentVertex == (order-1) and matrix[path[currentVertex]][0] == 1):
            path.append(0)
            print("Hamiltonian found, path is:", path)
            break
        else:
            Hamiltonian(matrix, order, path, currentVertex + 1)
            return 

def checkVertex(matrix, order, path, currentVertex):
    i=1
    while(True):
        path[currentVertex] = ((path[currentVertex]+i)%order)
        if(path[currentVertex] == 0):
            return
        if(matrix[path[currentVertex-1]][path[currentVertex]] == 1):
            for j in range (0, currentVertex+1):
                if(j != currentVertex and path[j] == path[currentVertex]):
                    path[currentVertex] = 0
                    i+=1
                    break
                if(j == currentVertex):
                    return
        else:
            path[currentVertex] = 0
            i+=1


#IN = input("Enter the number of desired vertices: ") #get input for number of verticies

#order = int(IN) #make input string an int

#TODO remove hard coded order
order = 10

graph = makeGraph(order) #make the graph 

#TODO remove printing of edges/nodes
#print("Number of nodes: ", graph.nodes)
print("Edges: ", graph.edges)

#init matrix filled with 0's for conversion
matrix = np.random.randint(0,1,(order,order))

#makes a pretty picture of the graph, great for finding cycles visually
#nx.draw(graph, with_labels=True) 
#plt.show() 


#convert ordered pairs into adj matrix for easier calculation
for i in range (0, order):
    for j in range (0, order):
        e = (i,j)
        if(graph.edges.__contains__(e)):
            matrix[i][j] = 1 #if there is an edge between vertex i and vertex j, append the matrix to have a 1 in the ith column jth row

path = [0] * (order) #init list to have n 0's
currentVertex = 1 #start the current vertex at 1

#matrix = [[0,0,1,0,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,1,0,0],[1,1,1,0,0]] #for testing, known cycle


Hamiltonian(matrix, order, path, currentVertex)

Похоже, что этот алгоритм работает примерно половину времени. Я думаю, что моя проблема в том, что я неправильно отслеживаю (или даже вообще не знаю, как это сделать), то есть, как только алгоритм достигает точки, где он не может продолжать, он не работает. 't go назад и попробуйте что-нибудь еще.

Как я могу это реализовать? Может ли кто-то указать мне на ресурс, который может мне это объяснить?

Спасибо!

Answer 1

Для любого, кто найдет этот пост, который не получил любви и нуждается в некотором руководстве, я понял, в чем проблема.

Оказывается, что использование значения счетчика в моей функции checkVertex (i) ограничило способ решения проблем. Мне также не нужно было ничего передавать из одной функции в другую, поскольку технически способ, которым я определил вещи, был таким, что матрица, путь и т. Д. 1013 * были глобальными в python. (Я обычно пишу код на C ++, но слышал, что эту проблему легче решить с помощью python).

В любом случае, вот код с правильными комментариями:

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import sys
import random

#The reason we went with this algorithm instad of filling a matrix with random int from 0,1 to begin with is because this is always a simple graph, while
#the other approach almost never makes one. So, rather than checking and fixing those graphs, we thought this would be faster and easier
def makeGraph(order):
    x = random.randint(2,10)
    p = (x/10) #represents the probability of an edge being created between any 2 verticies, if less than .2 its almost never connected for values 10+.
    g = nx.erdos_renyi_graph(order, p) #generates the graph, verticies are 0 to order, edges are ordered pairs of these numbers
    return g


def Hamiltonian(currentVertex):
    while(True): #do this until we find a cycle or show there isnt one
        if(currentVertex == order): #once the value of cV is the order of G, its likely we found a cycle
            if(matrix[path[currentVertex-1]][0] == 1): #but, we should only cont. if there is for sure an edge from the last vertex and 0
                path.append(0) #add 0 to the end to illustrate that the path ends at 0
                print("There is a cycle, a path is: ", path)
                paintGraph()
            else:     
                return

        checkVertex(currentVertex) #dont have a cycle yet, so try again

        #if after check vertex the current vertex is 0,
        #we know that something went wrong so try a new value of cv, starting from 0
        if(path[currentVertex] == 0): 
            return

        Hamiltonian(currentVertex+1) #move on to the next vertex and try to find the next proper vertex


def checkVertex(cV):
    while(True):
        path[cV] = ((path[cV]+1)%order) #starting at 1, try and find a path from the last vertex to the cV
        if(path[cV] == 0): #because of the mod, if checkVertex has tried every possible vertex then we know to return
            return
        if(matrix[path[cV-1]][path[cV]] == 1): #if there is an edge from the last vertex and the current vertex
            #loop to ensure there are no duplicates
            for j in range (0, cV+1):
                if(path[j] == path[cV] and j!=cV):
                    break
                if(j == cV):
                    if(cV<order): #if we arent at the end of the path yet, keep trying
                        return
                    #if we are on a potential end, then we should make sure that we can get back to 0,
                    #otherwise, we should try again.
                    if(cV == order and matrix[path[cV]][0] == 1): 
                        return
                    else:
                        break

#this is for when we did find a cycle               
def paintGraph():
    nx.draw(graph, with_labels=True) 
    plt.show()
    #the sys.exit is so that once we did find a cycle we stop looking, because the way 
    #I have things Hamiltonian would find all possible cycles
    sys.exit("Finished")


IN = input("Enter the number of desired vertices: ") #get input for number of verticies

order = int(IN) #make input string an int


graph = makeGraph(order) #make the graph 

#init matrix filled with 0's for conversion
matrix = np.random.randint(0,1,(order,order))

nx.draw(graph, with_labels=True) 
plt.show() 

#convert ordered pairs into adj matrix for easier calculation
for i in range (0, order):
    for j in range (0, order):
        e = (i,j)
        if(graph.edges.__contains__(e)):
            matrix[i][j] = 1 #if there is an edge between vertex i and vertex j, append the matrix to have a 1 in the ith column jth row
            matrix[j][i] = 1


path = [0]*order #init list to have n 0's
currentVertex = 1 #start the current vertex at 1

Hamiltonian(currentVertex)

#If hamiltonian didn't find a cycle and force sys.exit, then we know no cycle exists
print("There is no Hamiltonian cycle")

#draw the graph again just so we can check.
nx.draw(graph, with_labels=True) 
plt.show() 

Надеюсь, это полезно для кого-то. Решить это было довольно весело, поэтому определенно попробуйте сделать это самостоятельно, прежде чем вставлять копию!

Редактировать: Если вам интересно, почему у меня есть вызов sys.exit, то это потому, что я заботился только о поиске ОДНОГО цикла H. Как написан этот код, мы найдем ВСЕ H циклов данного графа.

Это может занять очень много времени. Фактически, время выполнения этого алгоритма составляет O (n! * Log (n)), где n - порядок графа. Этот код должен был быть протестирован с графиками порядка 50, и даже нахождение одного цикла заняло у моего P C около часа, и я проверял это только один раз.