获取具有给定数量的节点和边的所有可能的图形(使用图形工具)
Get all possible graphs with a given number of nodes and edges (with graph-tools)
我对图形还很陌生,我的知识接近于 0。
但是我需要建立一个模型以获得所有可能的图,这些图具有给定的边数、给定的节点数和每个节点之间的最大度数。
因此,例如,我想获得所有具有 8 个节点且每个节点之间正好有 3 个连接(边)的图可能性。
我也想把所有的可能性都当成字典,像这样:
{ 1 : [2,3,4],
2 : [5,3,1],
3 : [6,2,7]
... and so on
当然边不能与自身相连。
到目前为止,我尝试使用图形工具库 (here)
我尝试的是:
from graph_tool.all import *
def degree () :
return 3,3
g = random_graph(8, degree)
a = g.get_edges([g.edge_index])
print(a)
哪个输出我:
[[ 0 7 0]
[ 0 5 2]
[ 0 2 1]
[ 1 7 12]
[ 1 5 14]
[ 1 6 13]
[ 2 3 9]
[ 2 4 10]
[ 2 1 11]
[ 3 6 22]
[ 3 0 23]
[ 3 1 21]
[ 4 3 3]
[ 4 1 5]
[ 4 0 4]
[ 5 2 20]
[ 5 0 19]
[ 5 4 18]
[ 6 7 15]
[ 6 5 16]
[ 6 4 17]
[ 7 6 8]
[ 7 3 7]
[ 7 2 6]]
有人可以解释一下我做错了什么吗? (例如,为什么第一个列表是 0,7,0(这意味着什么......同样,我对这类东西完全陌生))
如果我只定义了8个节点,为什么会有大于7的数字?
我怎样才能得到所有的可能性(所有 8 个节点的图和每个节点之间恰好 3 个连接)?
我不确定你想达到什么目的,但我写了一个代码来解决类似的问题,并从使用图形工具库生成的随机 distinct 图形生成数据结构。
它可能会帮助您获得所需的东西。
如果您有任何问题,请告诉我。
from graph_tool.all import *
import json
def isDifferentList(list1, list2):
return list1 != list2
def isDifferentGraph(graph1, graph2):
for k in graph1.keys():
if isDifferentList(graph1[k], graph2[k]):
# if all lists of connection exists, return true and stop all iterations,
# this mean that the graph exists, so need to generate a new one
return True
#the graph does not exist, we can continue with the current one
return False
def graphExists(graph, all):
for generated in all:
if not isDifferentGraph(graph, generated):
return True
return False
def generate_output_data(gr):
gGraph = {}
for vertex in gr.get_edges():
vertex0 = int(vertex[0]) + 1
vertex1 = int(vertex[1]) + 1
if int(vertex0) not in gGraph:
gGraph[vertex0] = []
if vertex1 not in gGraph:
gGraph[vertex1] = []
gGraph[vertex0].append(vertex1)
gGraph[vertex1].append(vertex0)
return gGraph
def getRandomGraph():
return generate_output_data(random_graph(VERTICES, lambda: DEGREE, directed=False))
def defineDegreeAndvertexs(vertexs, in_degree):
global VERTICES, DEGREE
DEGREE = in_degree
VERTICES = vertexs
def generateNgraph(in_vertices, in_degree, n_graphs):
#first store inputs in globals variable
defineDegreeAndvertexs(in_vertices, in_degree)
#generate empty list of generated uniques graphs
all_graphs = []
for i in range(0, n_graphs):
#generate a new random graph and get it as a desired output data struct
g = getRandomGraph()
# check if this graph already exists and generate a new one as long as it already been generated
while graphExists(g, all_graphs):
g = getRandomGraph()
#Write the new graph in a text file
with open("graphs.txt", 'a+') as f:
f.write(json.dumps(g))
f.write("\n")
#append the new graph in the all graph list - this list will be the input for the graphExists function
all_graphs.append(g)
if __name__ == '__main__':
generateNgraph(8, 3, 1500)
关注这里的主要功能及其注释,了解整个流程。
输出:
{"1": [2, 7, 5], "2": [1, 7, 5], "7": [1, 2, 6], "5": [1, 3, 2], "4": [6, 3, 8], "6": [4, 7, 8], "3": [4, 5, 8], "8": [6, 3, 4]}
{"1": [8, 7, 2], "8": [1, 2, 6], "7": [1, 4, 5], "2": [1, 6, 8], "6": [2, 3, 8], "4": [7, 3, 5], "3": [4, 5, 6], "5": [4, 3, 7]}
{"1": [8, 7, 5], "8": [1, 3, 2], "7": [1, 5, 6], "5": [1, 4, 7], "2": [3, 4, 8], "3": [2, 6, 8], "4": [6, 2, 5], "6": [4, 3, 7]}
其中每个字典的键是一个命名的顶点,值是一个表示连接顶点的列表。
这不是真正的优化代码,因为它的复杂性随着图形的生成而增加。它将检查为每次迭代生成的每个图,因此复杂度为 O(n)。
现在给你第一个问题:给定n条边和给定的度我们可以输出多少个图,首先如果你想要所有的边都严格连接可能无解。其次,在我看来是一道非常复杂的数学题。
这是我到目前为止所发现的,但是为了在代码中实现它,我让其他专家来回答这个问题(因为我不知道抱歉)。
我对图形还很陌生,我的知识接近于 0。 但是我需要建立一个模型以获得所有可能的图,这些图具有给定的边数、给定的节点数和每个节点之间的最大度数。
因此,例如,我想获得所有具有 8 个节点且每个节点之间正好有 3 个连接(边)的图可能性。
我也想把所有的可能性都当成字典,像这样:
{ 1 : [2,3,4],
2 : [5,3,1],
3 : [6,2,7]
... and so on
当然边不能与自身相连。
到目前为止,我尝试使用图形工具库 (here)
我尝试的是:
from graph_tool.all import *
def degree () :
return 3,3
g = random_graph(8, degree)
a = g.get_edges([g.edge_index])
print(a)
哪个输出我:
[[ 0 7 0]
[ 0 5 2]
[ 0 2 1]
[ 1 7 12]
[ 1 5 14]
[ 1 6 13]
[ 2 3 9]
[ 2 4 10]
[ 2 1 11]
[ 3 6 22]
[ 3 0 23]
[ 3 1 21]
[ 4 3 3]
[ 4 1 5]
[ 4 0 4]
[ 5 2 20]
[ 5 0 19]
[ 5 4 18]
[ 6 7 15]
[ 6 5 16]
[ 6 4 17]
[ 7 6 8]
[ 7 3 7]
[ 7 2 6]]
有人可以解释一下我做错了什么吗? (例如,为什么第一个列表是 0,7,0(这意味着什么......同样,我对这类东西完全陌生))
如果我只定义了8个节点,为什么会有大于7的数字?
我怎样才能得到所有的可能性(所有 8 个节点的图和每个节点之间恰好 3 个连接)?
我不确定你想达到什么目的,但我写了一个代码来解决类似的问题,并从使用图形工具库生成的随机 distinct 图形生成数据结构。
它可能会帮助您获得所需的东西。
如果您有任何问题,请告诉我。
from graph_tool.all import *
import json
def isDifferentList(list1, list2):
return list1 != list2
def isDifferentGraph(graph1, graph2):
for k in graph1.keys():
if isDifferentList(graph1[k], graph2[k]):
# if all lists of connection exists, return true and stop all iterations,
# this mean that the graph exists, so need to generate a new one
return True
#the graph does not exist, we can continue with the current one
return False
def graphExists(graph, all):
for generated in all:
if not isDifferentGraph(graph, generated):
return True
return False
def generate_output_data(gr):
gGraph = {}
for vertex in gr.get_edges():
vertex0 = int(vertex[0]) + 1
vertex1 = int(vertex[1]) + 1
if int(vertex0) not in gGraph:
gGraph[vertex0] = []
if vertex1 not in gGraph:
gGraph[vertex1] = []
gGraph[vertex0].append(vertex1)
gGraph[vertex1].append(vertex0)
return gGraph
def getRandomGraph():
return generate_output_data(random_graph(VERTICES, lambda: DEGREE, directed=False))
def defineDegreeAndvertexs(vertexs, in_degree):
global VERTICES, DEGREE
DEGREE = in_degree
VERTICES = vertexs
def generateNgraph(in_vertices, in_degree, n_graphs):
#first store inputs in globals variable
defineDegreeAndvertexs(in_vertices, in_degree)
#generate empty list of generated uniques graphs
all_graphs = []
for i in range(0, n_graphs):
#generate a new random graph and get it as a desired output data struct
g = getRandomGraph()
# check if this graph already exists and generate a new one as long as it already been generated
while graphExists(g, all_graphs):
g = getRandomGraph()
#Write the new graph in a text file
with open("graphs.txt", 'a+') as f:
f.write(json.dumps(g))
f.write("\n")
#append the new graph in the all graph list - this list will be the input for the graphExists function
all_graphs.append(g)
if __name__ == '__main__':
generateNgraph(8, 3, 1500)
关注这里的主要功能及其注释,了解整个流程。
输出:
{"1": [2, 7, 5], "2": [1, 7, 5], "7": [1, 2, 6], "5": [1, 3, 2], "4": [6, 3, 8], "6": [4, 7, 8], "3": [4, 5, 8], "8": [6, 3, 4]}
{"1": [8, 7, 2], "8": [1, 2, 6], "7": [1, 4, 5], "2": [1, 6, 8], "6": [2, 3, 8], "4": [7, 3, 5], "3": [4, 5, 6], "5": [4, 3, 7]}
{"1": [8, 7, 5], "8": [1, 3, 2], "7": [1, 5, 6], "5": [1, 4, 7], "2": [3, 4, 8], "3": [2, 6, 8], "4": [6, 2, 5], "6": [4, 3, 7]}
其中每个字典的键是一个命名的顶点,值是一个表示连接顶点的列表。
这不是真正的优化代码,因为它的复杂性随着图形的生成而增加。它将检查为每次迭代生成的每个图,因此复杂度为 O(n)。
现在给你第一个问题:给定n条边和给定的度我们可以输出多少个图,首先如果你想要所有的边都严格连接可能无解。其次,在我看来是一道非常复杂的数学题。
这是我到目前为止所发现的,但是为了在代码中实现它,我让其他专家来回答这个问题(因为我不知道抱歉)。