将树表示为粘合的半边
Representing a tree as glued half-edges
我有一棵树，例如作为 networkx 对象。为了将其输入给我的黑盒算法，我需要将其保存为以下奇怪的格式：
按顺时针顺序遍历树。当我穿过边缘的一侧时，我会逐渐标记它。然后我想为每条边保存其两侧的标签。
例如，星形将成为列表 [(0,1),(2,3),(4,5),...]，具有 3 个顶点的路径将成为 [(0,3),(1,2)]。
我很难实现这个。如何才能做到这一点？我可以使用任何库。
我在 networkx 中发现了这个很棒的内置函数 dfs_labeled_edges。从那里开始变得轻而易举。
def get_new_encoding(G):
dfs = [(v[0],v[1]) for v in nx.dfs_labeled_edges(G, source=1) if v[0]!=v[1] and v[2]!="nontree"]
dfs_ind = sorted(range(len(dfs)), key=lambda k: dfs[k])
new_tree_encoding = [(dfs_ind[i],dfs_ind[i+1]) for i in range(0,len(dfs_ind),2)]
return new_tree_encoding
我会在不参考任何图书馆的情况下回答这个问题。
您需要执行深度优先遍历，并在访问子树之前以及在之后记录（全局）增量数30=] 你访问过它。这两个数字构成了你必须前置到你从子树遍历得到的结果的元组。
这里是一个需要将图表示为邻接表的实现。 main函数需要获取根节点和邻接表
def iter_naturals(): # helper function to produce sequential numbers
n = 0
while True:
yield n
n += 1
def half_edges(root, adj):
visited = set()
sequence = iter_naturals()
def dfs(node):
result = []
visited.add(node)
for child in adj[node]:
if child not in visited:
forward = next(sequence)
path = dfs(child)
backward = next(sequence)
result.extend([(forward, backward)] + path)
return result
return dfs(root)
以下是您如何 运行 为您提到的两个示例。我刚刚将这些图实现为邻接列表，其中节点由它们在该列表中的索引标识：
示例 1：“星星”：
根节点是所有其他节点的父节点
adj = [
[1,2,3], # 1,2,3 are children of 0
[],
[],
[]
]
print(half_edges(0, adj)) # [(0, 1), (2, 3), (4, 5)]
示例 2：具有 3 个节点的单个路径
adj = [
[1], # 1 is a child of 0
[2], # 2 is a child of 1
[]
]
print(half_edges(0, adj)) # [(0, 3), (1, 2)]
我有一棵树，例如作为 networkx 对象。为了将其输入给我的黑盒算法，我需要将其保存为以下奇怪的格式：
按顺时针顺序遍历树。当我穿过边缘的一侧时，我会逐渐标记它。然后我想为每条边保存其两侧的标签。
例如，星形将成为列表 [(0,1),(2,3),(4,5),...]，具有 3 个顶点的路径将成为 [(0,3),(1,2)]。
我很难实现这个。如何才能做到这一点？我可以使用任何库。
我在 networkx 中发现了这个很棒的内置函数 dfs_labeled_edges。从那里开始变得轻而易举。
def get_new_encoding(G):
dfs = [(v[0],v[1]) for v in nx.dfs_labeled_edges(G, source=1) if v[0]!=v[1] and v[2]!="nontree"]
dfs_ind = sorted(range(len(dfs)), key=lambda k: dfs[k])
new_tree_encoding = [(dfs_ind[i],dfs_ind[i+1]) for i in range(0,len(dfs_ind),2)]
return new_tree_encoding
我会在不参考任何图书馆的情况下回答这个问题。
您需要执行深度优先遍历，并在访问子树之前以及在之后记录（全局）增量数30=] 你访问过它。这两个数字构成了你必须前置到你从子树遍历得到的结果的元组。
这里是一个需要将图表示为邻接表的实现。 main函数需要获取根节点和邻接表
def iter_naturals(): # helper function to produce sequential numbers
n = 0
while True:
yield n
n += 1
def half_edges(root, adj):
visited = set()
sequence = iter_naturals()
def dfs(node):
result = []
visited.add(node)
for child in adj[node]:
if child not in visited:
forward = next(sequence)
path = dfs(child)
backward = next(sequence)
result.extend([(forward, backward)] + path)
return result
return dfs(root)
以下是您如何 运行 为您提到的两个示例。我刚刚将这些图实现为邻接列表，其中节点由它们在该列表中的索引标识：
示例 1：“星星”：
根节点是所有其他节点的父节点
adj = [
[1,2,3], # 1,2,3 are children of 0
[],
[],
[]
]
print(half_edges(0, adj)) # [(0, 1), (2, 3), (4, 5)]
示例 2：具有 3 个节点的单个路径
adj = [
[1], # 1 is a child of 0
[2], # 2 is a child of 1
[]
]
print(half_edges(0, adj)) # [(0, 3), (1, 2)]