1

ノードとアークのデータを使用してツリーを構築しようとしています。これまでに行ったことは、次のようにクラスTree、Arc、Nodeをビルドすることです。

class Tree():

  def __init__(self):
    self.root = None
    self.nodes = {}
    self.end_arcs = {}

class Arc():

  def __init__(self,start,end,data={}):
    self.start = start
    self.end = end
    self.data = data

class Node():

  def __init__(self,token,data={}):
    self.token = str(token)
    self.state = self.OPEN
    self.data = data

ノードにはますます番号が付けられ、エンドノードには-1のラベルが付けられます。ただし、ツリーを逆にしてノードの番号を付け直したい場合は、多くのことを変更する必要があります。ノードのキー、すべてのノードのラベル、そしておそらく（または、ノードのノードを指すことができますか？ ）また、私のアークのノードが口述します。ですから、この共通の構造を実装する私の方法は良いものではないと思います。この問題を解決する標準的な方法はありますか？または、このようなツリー構造をどのように構築しますか？

前もって感謝します、

ジョリス

4

2 に答える 2

1

私のコメントを少し拡張して、次のことを検討してください

class Tree():
  def __init__(self):
    self.root = None
    self.nodes = {}
    self.end_arcs = {}

class Arc():
  def __init__(self,start,end,data={}):
    self.start = start
    self.end = end
    self.data = data

  def __str__(self):
    return "%s-%s" % (self.start.token, self.end.token)

class Node():
  def __init__(self,token,data={}):
    self.token = str(token)
    #self.state = self.OPEN
    self.data = data


n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)

t = Tree()
t.root = n1
t.nodes = [n1,n2,n3,n4,n5]

a1 = Arc(n1,n2)
a2 = Arc(n2,n3)
a3 = Arc(n2,n4)
a4 = Arc(n1,n5)

print(a1)  # 1-2
# "Rename" Nodes
n1.token = 101 
n2.token = 102
print(a1)  # 101-102

アークは ID ではなく「参照によって」ノードを追跡するため、ノードの「名前変更」は問題ありません。たとえば、アークを見ると、参照を使用すると、基になるノードがどのように変更されるかを気にする必要がなくなります。

于 2012-06-19T08:17:07.160 に答える
1

このグラフ インフラストラクチャを自分で実装したくない場合は、NetworkXをご覧ください。これは機能満載のグラフ/ネットワーク ライブラリであり、簡単に始めることができます。

import networkx as nx

class Node(object):
    def __init__(self, data):
        self.data = data

G = nx.Graph()
G.add_nodes_from([Node(1), Node(2), Node(3), Node(4)])
G.add_edge(1, 2, data='some data')
G.add_edge(2, 3, data='some more data')
G.add_edge(2, 4, data='yet more data')

これにより、次のようなグラフが作成されます

  1
  |
  2
 / \
/   \
|   |
3   4

ノードにカスタム クラスを使用する必要はありません。文字列、整数など（任意のハッシュ可能なオブジェクト）を単純に使用できます。

于 2012-06-19T09:20:42.963 に答える