使用 python 使用节点约束生成图

Use python to generate graph using node constraints

我正在尝试解决我的系统 (Python/Storm) 遇到的问题,但不确定什么是最好的工具。

目标:使用对节点输入和输出的约束来创建图的边。

我有大约 400+ python 函数(apache storm shell bolts 每个 bolt 都包含一个函数 - 在这种情况下 Storm 并不重要,我将它们视为节点)。

每个 bolt/function/Node 都有一个定义的输入和输出名称属性列表。 我有一个来源(有输出,但没有输入)。 节点(有输入和输出列表) Sink(只有输入没有输出)。

为了更清楚地说明我有:

S = Source , Input = [] , Output = ["a","b","c","d"] ("a","b","c","d" are attributes the sources produces).
A = Node , Input = ["a","b"], output = ["e"]
B = Node , Input = ["a","e"], output = ["f"]
Si = Sink, Input = ["a","b","c","d","e","f"] , Output = [] 

我希望 NetworkX(或其他图形库)使用节点上的这些约束单独创建边。

每个节点输出只是输出列表,不是输出+输入。

我想要的输出是边列表:

S,A
S,B
A,B
B,Si
A,Si
S,Si

*图中C=Si

NetworkX 是否支持这样的构建?如果可以,我该如何实施?

您可以根据您的数据构建二分图(我认为是定向的?),然后 "project" 将其构建到一组节点上以制作您想要的图。例如。如果有向边 S->a 和 a->T,则两个节点集是 {S,T} 和 {a}。投影到节点集 {S,T} 得到 S->T,因为在原始二分图中存在从 S->T 的路径。

import networkx as nx

data = [("S", [], ["a","b","c","d"]),
        ("A", ["a","b"], ["e"]),
        ("B", ["a","c"], ["f"]),
        ("Si", ["a","b","c","d","e","f"], [])]

G = nx.DiGraph()
#G = nx.Graph() # maybe you want an undirected graph?
nodes = []
for n,inedges,outedges in data:
    nodes.append(n)
    for s in inedges:
        G.add_edge(s,n)
    for t in outedges:
        G.add_edge(n,t)

P = nx.projected_graph(G,nodes)

print list(P.nodes())
print list(P.edges())
# OUTPUT
# ['A', 'S', 'B', 'Si']
# [('A', 'Si'), ('S', 'A'), ('S', 'Si'), ('S', 'B'), ('B', 'Si')]