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。但是，当我想反转树并重新编号节点时，我必须更改很多东西：我的节点字典的键，每个节点的标签，也许（或者它们可以指向我的节点字典中的节点吗？ ) 也是我的 arcs dict 中的节点。所以我认为我实现这种通用结构的方式不是一个好方法。有解决这个问题的标准方法吗？或者你将如何构建这样的树结构？

提前致谢，

乔里斯

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 回答