やりたいこと
最終的にpythonで書かれたZDDのコードをC#に書き直して、Unityでも使えるようにしたい
###引用元のコード
ここで提示されているコードをそのまま使っています
https://qiita.com/cabernet_rock/items/01c48dd06178ba0768f9
###問題点
文中で出てくるhow_many_edgesという関数部分が記述されていないためそこを足したいが、記述方法が分からない
以下は引用元で紹介されているコードをひとまとめにしたものです。
python
1# -*- coding: utf-8 -*- 2""" 3Spyderエディタ 4 5これは一時的なスクリプトファイルです 6""" 7""" 89つの頂点、 9vertex_set=["e0","e1","e2","e3","e4","e5","e6","e7","e8"] 10edges=[("e0","e1"),("e0","e3"),("e1","e2"),("e1","e4"),("e2","e5"),("e3","e4"),("e3","e6"),("e4","e7"),("e4","e5"),("e5","e8"),("e6","e7"),("e7","e8")] 11""" 12import collections 13import copy 14""" 15字数制限のため一部略 16ここにサイトで紹介されているupdate_frontier関数、update_mate_arr関数、Remove_impossible関数、Flatten_dual関数が入る 17""" 18 19def One_stroke(edges, frontier_mate_dict, start, on_the_way): 20 """ 21 関数の概要:一筆書きの集合かを判断する関数(ループを除く) 22 @param edges :調べたいエッジ 23 @param frontier_mate_dict :mate配列 24 @param start :始点 25 @param on_the_way :終点までつながっていない=True 26 @return:True or False 27 """ 28 # フロンティア同士が繋がっているものの片方のフロンティアを残す。また、e0に繋がっているフロンティアも除く。 29 together = [k for k,v in frontier_mate_dict.items() if (k in frontier_mate_dict.values()) and k<v and k!=start] 30 out_edges = [edges[i][1] for i in range(len(edges)) if edges[i][0] == start] 31 if len(out_edges)!=1: return False 32 edge = out_edges[0] 33 b_edge = start 34 35 count = how_many_edges(edges, start) 36 if on_the_way: 37 # フロンティア同士が繋がっているものがあれば、それも考える。 38 for i in range(int(len(together))): 39 count += how_many_edges(edges, together[i]) 40 return count==len(edges) 41 42def how_many_edges(edges,start): 43 #実装内容 44 #current_nodeの頂点と始点となる頂点が一致する辺(タプル)の取り出し 45 #current_nodeと始点が一致する辺があれば、current_nodeを一致した辺の終点と入れ替え、countを1増やし、flagをTrueにし、break 46 #一致するものがなければFlagがFalseのままなのでwhileを抜ける 47 count=0 48 current_node=start 49 _copy=copy.deepcopy(edges) 50 flag=False 51 while len(_copy)>0: 52 i=0 53 flag=False 54 for i in range(len(_copy)): 55 if(current_node==_copy[i][0]): 56 count+=1 57 current_node= _copy.pop(i)[1] 58 flag=True 59 break 60 else: 61 continue 62 if flag == False: 63 break 64 65 return count 66 67 68 69 70def rootnum(vertex_set, edges, flag=False): 71 """ 72 関数の概要:ルートの総数を調べる。 73 @param vertex_set :グラフの頂点集合 74 @param edges :グラフの辺の集合 75 @param flag :等価なエッジ集合を表示するか 76 """ 77 start = vertex_set[0] # 始点 78 end = vertex_set[-1] # 終点 79 frontier = vertex_set[:1] # フロンティアの初期化。 80 mate_dict = dict() # mate配列の初期化。 81 for i in range(len(vertex_set)): mate_dict[vertex_set[i]] = vertex_set[i] 82 counter = collections.Counter([edge[0] for edge in edges]) # フロンティアの更新に利用する。 83 answer = 0 # 求めたいルートの数 84 answer_list = [] # 求めたいルート(等価なものに圧縮済) 85 86 edges_set = [[[],1,mate_dict]] # 初期化 87 for i in range(len(edges)): 88 # 新しいノードを獲得する処理 89 frontier = update_frontier(frontier, edges[i], edges, counter) # フロンティアの更新。 90 edges_set_get = copy.deepcopy(edges_set) # 新規のエッジを獲得する方 91 edges_set_not = copy.deepcopy(edges_set) # 新規のエッジを獲得しない方 92 for j in range(len(edges_set_get)): 93 edges_set_get[j][0].append(edges[i]) 94 edges_set = edges_set_not+edges_set_get # 順番意外と大事(より簡単な方を等価なものの代表にできる。) 95 96 for j in range(len(edges_set)): # mate配列の更新。 97 edges_set[j][2] = update_mate_arr(edges_set[j][2],frontier,edges_set[j][0]) 98 99 # [frontierのmate配列]をkey,[取得edges,等価なものの個数,mate配列]をvalueにする。 100 result_dict = dict() # 圧縮をするためdictionaly型。 101 for j in range(len(edges_set)): 102 mate_arr = edges_set[j][2] # 全てのmate配列(dictionaly型) 103 mate_arr_frontier = dict([(k,v) for k,v in mate_arr.items() if k in frontier]) # フロンティア部分のみ 104 mate_key = "".join(mate_arr_frontier.values()) # 文字を結合することで key にする。 105 get_edges = edges_set[j][0] # 獲得したエッジ 106 num = edges_set[j][1] # これより前で圧縮された等価なものの数 107 """ 108 ここで、既に不正解だとわかっているものを取り除く。 109 ・フロンティア配列のmate配列のvalueにe0が存在しない。(これだとe0からエッジがないものも含まれる。) 110 ・1つのノードから3本以上のエッジが出ている。 111 ・ループができている。 112 """ 113 if start in mate_arr_frontier.values(): # フロンティアのmate配列に始点が含まれないものを取り除く。 114 if Remove_impossible(get_edges, frontier, start): # 既に無理なものを取り除く。 115 if start in Flatten_dual(get_edges): # 始点が獲得エッジに含まれているもののみにする。 116 if One_stroke(get_edges, mate_arr_frontier, start, True): # ループが複数ノードを取り除く。 117 if end in frontier and mate_arr_frontier[end] == start: 118 if One_stroke(get_edges, mate_arr_frontier,start, False): 119 if flag: answer_list.append({"num":num,"route":get_edges}) # 必要であれば最後まで行ったパスを記憶する。 120 answer+=num 121 continue 122 else: 123 continue 124 """フロンティア部分のmate配列が等しいものを圧縮する。""" 125 # mate配列の同じものがあれば、エッジ数の少ないものを残して圧縮する。 126 if mate_key in result_dict: 127 result_dict[mate_key][1] += num # 等価なものは圧縮する。 128 else: 129 result_dict[mate_key] = [get_edges, num, mate_arr] 130 131 # 圧縮後を回収する。 132 edges_set = [] 133 for k,v in result_dict.items(): 134 edges_set.append([v[0],v[1],v[2]]) 135 136 print("{} から {} までのルートの総数は {} 通りです。".format(start,end,answer)) 137 if flag: return answer_list 138 139
自分が実装したのはここ
python
1def how_many_edges(edges,start): 2 #実装内容 3 #current_nodeの頂点と始点となる頂点が一致する辺(タプル)の取り出し 4 #current_nodeと始点が一致する辺があれば、current_nodeを一致した辺の終点と入れ替え、countを1増やし、flagをTrueにし、break 5 #一致するものがなければFlagがFalseのままなのでwhileを抜ける 6 count=0 7 current_node=start 8 _copy=copy.deepcopy(edges) 9 flag=False 10 while len(_copy)>0: 11 i=0 12 flag=False 13 for i in range(len(_copy)): 14 if(current_node==_copy[i][0]): 15 count+=1 16 current_node= _copy.pop(i)[1] 17 flag=True 18 break 19 else: 20 continue 21 if flag == False: 22 break 23 24 return count
このコードがあっているか分からないが、サイトで紹介されている例2を試したとき
vertex_set=["e0","e1","e2","e3","e4","e5","e6","e7","e8"]
edges=[("e0","e1"),("e0","e3"),("e1","e2"),("e1","e4"),("e2","e5"),("e3","e4"),("e3","e6"),("e4","e7"),("e4","e5"),("e5","e8"),("e6","e7"),("e7","e8")]
=>サイトでの回答:12、私が作成した上記コード:6
[{'num': 3, 'route': [('e0', 'e1'), ('e1', 'e2'), ('e2', 'e5'), ('e5', 'e8')]},
{'num': 3, 'route': [('e0', 'e1'), ('e1', 'e4'), ('e4', 'e7'), ('e7', 'e8')]}]
という回答になってしまった
私が作成した部分が間違っているのか、サイトで紹介されているコードに誤りがあるのか教えてほしい。
###環境
Windows10
Spyder
Python3.8
どうぞよろしくお願いいたします。
あなたの回答
tips
プレビュー