find Hamilton Path

出発ノードを指定して、ハミルトン閉路を探す関数のサンプルです。グラフモジュール graph_1_1.py を使います。

maxim_1Stroke.zip

ハミルトン閉路がない場合、最も多くノードを介する閉路のリストを返します。 GH-Pythonだと計算フレームが問題になりそうです。サンプルは30ノード38エッジ程度。

import rhinoscriptsyntax as rs
import Rhino.Geometry as rg
import graph_1_1 as g

def tryHamiltonianPath(nodes, startn):
    print "from ", startn
    rtn_path = []
    routes = []
    branch = []
    branch.append([startn])

    i = 0
    while 1:
        routes = list(branch)
        branch = []
        pthmaxsize = 0
        for rt in routes:
            if pthmaxsize < len(rt):
                pthmaxsize = len(rt)
        for rt in routes:
            n = rt[-1]
            headn = rt[0]
            for e in n.edges:
                no = e.otherside(n)
                if no in rt:
                    if headn == no:
                        rtn_path.append(list(rt))
                else:
                    newrt = list(rt)
                    newrt.append(no)
                    if len(newrt) > pthmaxsize:
                        branch.append(list(newrt))

        #print "branch ",len(branch)
        if len(branch) == 0:
            break

        i += 1
        if i>10000:
            print "break for safty "
            break

    print "we have",len(rtn_path),"stroke(s)"
    maxsize = 0
    for rt in rtn_path:
        if maxsize < len(rt):
            maxsize = len(rt)
    if maxsize == len(nodes):
        print "we have hamilton path"

    maxroutes = []
    for rt in rtn_path:
        if maxsize == len(rt):
            rt.append(startn)
            maxroutes.append(rt)

    print "we have",len(maxroutes)," maxim stroke(s)"
    return maxroutes

def getEdges(nodes):
    if len(nodes) < 1:
        return []
    edges = []
    for i in range(len(nodes)-1):
        n1 = nodes[i]
        n2 = nodes[i+1]
        l = rs.AddLine(n1.pos,n2.pos)
        edges.append(l)
    return edges

#--------------------
objs = []
g.initFromCrv(cvs)
startnode = g.closestNode(sPt)
objs.append(rs.AddCircle(startnode.pos,2000))
paths = tryHamiltonianPath(g.nodes,startnode)

for i in range(len(paths)):
    rt = paths[i]
    edges = getEdges(rt)
    tedges = rs.MoveObjects(edges,[0,0,i*2000])
    objs.extend(tedges)

a = objs

Comments are closed.