递归协同树生成算法
Recursive co-tree Generation algorithm
在 >this article< 的 pg.7 中，有一个递归算法解释了给定协图的协树的生成。基于这篇文章，我尝试在 python3 中使用图结构库 NetworkX 和图结构库 treelib 来实现它树数据结构。
为了准确起见，我创建了与示例完全相同的图形（再次在上述文章的第 7 页），并编写了以下函数：
import networkx as nx
from treelib import tree
# Globals
tree = Tree()
CC = 0
def generate_cotree(G,tree_pointer=None,complemented=None):
print("----------------")
global tree
global CC
def _getID():
global CC
CC += 1
return CC
string = "[{0}] Called for graph G = (V,E)\n V = {1} \n E = {2} \n".format(tree_pointer,G.nodes,G.edges)
print(string)
vertexes = list(G.nodes)
edges = list(G.edges)
graph_components = [G.subgraph(c).copy() for c in nx.connected_components(G)]
if len(vertexes) == 1:
'''
G(V,E) where |V| = 0 --> Trivial Cograph
'''
print("...Added leaf node!")
tree.create_node(tag=vertexes[0],parent=tree_pointer)
return 0
elif len(edges) == 0: # Trivial Cograph
'''
G(V,E) where |E| = 0 --> Trivial Cograph
'''
for vertex in vertexes:
tree.create_node(tag=vertex,parent=tree_pointer)
print("...Added leaf node " + str(vertex) + "!")
return 0
else:
if not nx.is_connected(G):
'''
Case A: The G(V,E) is a not connected graph --> Add a 0-node and call the
generate_cotree(g) for every g ε connected_components(G)
'''
print("...Added 0-Node")
id = _getID()
tree.create_node(tag=0,identifier=id,parent=tree_pointer)
tree_ptr = id # Increment the Tree Pointer
for sub_graph in graph_components:
generate_cotree(sub_graph,tree_pointer=tree_ptr)
else:
'''
Case B: The G(V,E) is a connected graph --> Add a 1-node and call the
generate_cotree(g) for every g ε connected_components(~G) where ~G is the complement of G
'''
print("...Added 1-Node")
id = _getID()
tree.create_node(tag=1,identifier=id,parent=tree_pointer)
tree_ptr = id # Increment the Tree Pointer
complement = nx.complement(G) # Get ~G
comp_graph_components = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for subgraph in comp_graph_components:
generate_cotree(subgraph,tree_pointer=tree_ptr)
我执行此测试的图 B 的代码如下：
B = nx.Graph()
B.clear()
B.add_node(1)
B.add_node(2)
B.add_node(3)
B.add_node(4)
B.add_node(5)
B.add_node(6)
B.add_node(7)
B.add_node(8)
B.add_edges_from([(2,4),(5,6),(6,7),(5,7),(3,7),(3,6)])
'''
-----
GRAPH:
------
(1) (2)-----(4)
(8) (3)
/ \
/ \
(6)-----(7)
\ /
\ /
(5)
'''
问题是我得到了错误的共同树，虽然我可以看到这里出了什么问题，但我不确定如何解决它：
EXPECTED CO-TREE:
(0-node)----------
/ | \ |
(1) (8) \ |
(1-node) (1-node)
/ | / | \
(2) (4) (6) (7) (0-node)
| \
(3) (5)
RESULTING CO-TREE AFTER generate_cotree()
(0-node)----------
/ | \ |
(1) (8) \ |
(1-node) (1-node)
/ | / | \
(2) (4) (6) (7) (1-node)
| \
(3) (5)
有人对这个话题有什么建议吗？
所以，我想通了。 （我想^^）
当下面的代码被执行时：
comp_graph_components = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for subgraph in comp_graph_components:
generate_cotree(subgraph,tree_pointer=tree_ptr)
这是函数中“案例 B”的一个片段，互补图 ~G 的每个连接组件（如果有）都会检查其连接性，因为每个组件都会调用该函数。这是错误的，但在算法中 not 很清楚。相反，对于每个连接的组件，应该考虑图 ~G 的连接性。这就是我按以下方式更改代码的原因：
def generate_cotree(G, tree_pointer=None, complemented=False):
# print("----------------")
global tree
global CC
# _getID() is no longer a nested function, I moved it outside of the function
# string = "[{0}] Called for graph G = (V,E)\n V = {1} \n E = {2} \n".format(tree_pointer, G.nodes, G.edges)
# print(string)
vertices = list(G.nodes)
edges = list(G.edges)
if len(vertices) == 1:
# print("...Added leaf node!")
tree.create_node(tag=vertices[0], identifier=getID(), parent=tree_pointer)
return 0
elif len(edges) == 0:
for vertex in vertices:
tree.create_node(tag=vertex, identifier=getID(), parent=tree_pointer)
# print("...Added leaf node " + str(vertex) + "!")
return 0
else:
if not nx.is_connected(G):
id = getID()
if complemented:
tree.create_node(tag=1, identifier=id, parent=tree_pointer)
# print("create node -> 1")
else:
tree.create_node(tag=0, identifier=id, parent=tree_pointer)
# print("create node -> 0")
tree_ptr = id
connected_subgraphs = [G.subgraph(c).copy() for c in nx.connected_components(G)]
for i in range(0, len(connected_subgraphs)):
generate_cotree(connected_subgraphs[i], tree_pointer=tree_ptr, complemented=complemented)
else:
id = getID()
if complemented:
tree.create_node(tag=0, identifier=id, parent=tree_pointer)
# print("create node -> 0")
else:
tree.create_node(tag=1, identifier=id, parent=tree_pointer)
# print("create node -> 1")
tree_ptr = id
complement = nx.complement(G)
complemented_subgraphs = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for i in range(0, len(complemented_subgraphs)):
generate_cotree(complemented_subgraphs[i], tree_pointer=tree_ptr, complemented=not complemented)
在 >this article< 的 pg.7 中，有一个递归算法解释了给定协图的协树的生成。基于这篇文章，我尝试在 python3 中使用图结构库 NetworkX 和图结构库 treelib 来实现它树数据结构。
为了准确起见，我创建了与示例完全相同的图形（再次在上述文章的第 7 页），并编写了以下函数：
import networkx as nx
from treelib import tree
# Globals
tree = Tree()
CC = 0
def generate_cotree(G,tree_pointer=None,complemented=None):
print("----------------")
global tree
global CC
def _getID():
global CC
CC += 1
return CC
string = "[{0}] Called for graph G = (V,E)\n V = {1} \n E = {2} \n".format(tree_pointer,G.nodes,G.edges)
print(string)
vertexes = list(G.nodes)
edges = list(G.edges)
graph_components = [G.subgraph(c).copy() for c in nx.connected_components(G)]
if len(vertexes) == 1:
'''
G(V,E) where |V| = 0 --> Trivial Cograph
'''
print("...Added leaf node!")
tree.create_node(tag=vertexes[0],parent=tree_pointer)
return 0
elif len(edges) == 0: # Trivial Cograph
'''
G(V,E) where |E| = 0 --> Trivial Cograph
'''
for vertex in vertexes:
tree.create_node(tag=vertex,parent=tree_pointer)
print("...Added leaf node " + str(vertex) + "!")
return 0
else:
if not nx.is_connected(G):
'''
Case A: The G(V,E) is a not connected graph --> Add a 0-node and call the
generate_cotree(g) for every g ε connected_components(G)
'''
print("...Added 0-Node")
id = _getID()
tree.create_node(tag=0,identifier=id,parent=tree_pointer)
tree_ptr = id # Increment the Tree Pointer
for sub_graph in graph_components:
generate_cotree(sub_graph,tree_pointer=tree_ptr)
else:
'''
Case B: The G(V,E) is a connected graph --> Add a 1-node and call the
generate_cotree(g) for every g ε connected_components(~G) where ~G is the complement of G
'''
print("...Added 1-Node")
id = _getID()
tree.create_node(tag=1,identifier=id,parent=tree_pointer)
tree_ptr = id # Increment the Tree Pointer
complement = nx.complement(G) # Get ~G
comp_graph_components = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for subgraph in comp_graph_components:
generate_cotree(subgraph,tree_pointer=tree_ptr)
我执行此测试的图 B 的代码如下：
B = nx.Graph()
B.clear()
B.add_node(1)
B.add_node(2)
B.add_node(3)
B.add_node(4)
B.add_node(5)
B.add_node(6)
B.add_node(7)
B.add_node(8)
B.add_edges_from([(2,4),(5,6),(6,7),(5,7),(3,7),(3,6)])
'''
-----
GRAPH:
------
(1) (2)-----(4)
(8) (3)
/ \
/ \
(6)-----(7)
\ /
\ /
(5)
'''
问题是我得到了错误的共同树，虽然我可以看到这里出了什么问题，但我不确定如何解决它：
EXPECTED CO-TREE:
(0-node)----------
/ | \ |
(1) (8) \ |
(1-node) (1-node)
/ | / | \
(2) (4) (6) (7) (0-node)
| \
(3) (5)
RESULTING CO-TREE AFTER generate_cotree()
(0-node)----------
/ | \ |
(1) (8) \ |
(1-node) (1-node)
/ | / | \
(2) (4) (6) (7) (1-node)
| \
(3) (5)
有人对这个话题有什么建议吗？
所以，我想通了。 （我想^^）
当下面的代码被执行时：
comp_graph_components = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for subgraph in comp_graph_components:
generate_cotree(subgraph,tree_pointer=tree_ptr)
这是函数中“案例 B”的一个片段，互补图 ~G 的每个连接组件（如果有）都会检查其连接性，因为每个组件都会调用该函数。这是错误的，但在算法中 not 很清楚。相反，对于每个连接的组件，应该考虑图 ~G 的连接性。这就是我按以下方式更改代码的原因：
def generate_cotree(G, tree_pointer=None, complemented=False):
# print("----------------")
global tree
global CC
# _getID() is no longer a nested function, I moved it outside of the function
# string = "[{0}] Called for graph G = (V,E)\n V = {1} \n E = {2} \n".format(tree_pointer, G.nodes, G.edges)
# print(string)
vertices = list(G.nodes)
edges = list(G.edges)
if len(vertices) == 1:
# print("...Added leaf node!")
tree.create_node(tag=vertices[0], identifier=getID(), parent=tree_pointer)
return 0
elif len(edges) == 0:
for vertex in vertices:
tree.create_node(tag=vertex, identifier=getID(), parent=tree_pointer)
# print("...Added leaf node " + str(vertex) + "!")
return 0
else:
if not nx.is_connected(G):
id = getID()
if complemented:
tree.create_node(tag=1, identifier=id, parent=tree_pointer)
# print("create node -> 1")
else:
tree.create_node(tag=0, identifier=id, parent=tree_pointer)
# print("create node -> 0")
tree_ptr = id
connected_subgraphs = [G.subgraph(c).copy() for c in nx.connected_components(G)]
for i in range(0, len(connected_subgraphs)):
generate_cotree(connected_subgraphs[i], tree_pointer=tree_ptr, complemented=complemented)
else:
id = getID()
if complemented:
tree.create_node(tag=0, identifier=id, parent=tree_pointer)
# print("create node -> 0")
else:
tree.create_node(tag=1, identifier=id, parent=tree_pointer)
# print("create node -> 1")
tree_ptr = id
complement = nx.complement(G)
complemented_subgraphs = [complement.subgraph(c).copy() for c in nx.connected_components(complement)]
for i in range(0, len(complemented_subgraphs)):
generate_cotree(complemented_subgraphs[i], tree_pointer=tree_ptr, complemented=not complemented)