出発ノードを指定して、ハミルトン閉路を探す関数のサンプルです。グラフモジュール graph_1_1.py を使います。
ハミルトン閉路がない場合、最も多くノードを介する閉路のリストを返します。 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.