транзитивного замыкания в графе

Question

У меня есть ориентированный граф х-> у y-> г

я хотел бы добавить к этому grpah транзитивного замыкания х-> г

Что я должны изменить теперь я создаю все возможные комбинации между x, y и z в обоих направлениях.

Мой код ниже.

def transitive_closure(G): 
    TC = nx.DiGraph() 
    TC.add_nodes_from(G.nodes()) 
    TC.add_edges_from(G.edges()) 
    for v in G: 
     TC.add_edges_from((v, u) for u in nx.dfs_preorder_nodes(G, source=v) 
         if v != u) 
    return TC 

Answer 1

Вы можете попробовать итеративное решение. Во-первых, вместо того чтобы создавать новый граф со всеми узлами и краями последнего, просто скопируйте его:

TC = G.copy() 

Затем перебирать узлы и добавить все соседи соседей, чтобы быть соседями x:

for x in G: 
    # Extract all neighbours of neighbours of x (from G) 
    all_nh = [] 
    for y in G.neighbours(x): 
     all_nh += G.neighbours(y) 

    # Remove from the list of neighbors the current node and its immediate neighbors 
    all_nh = set(all_nh) - set([x]) - set(G.neighbours(x)) 

    # Create new edges (x -> z) 
    edges = map(lambda z: (x, z), all_nh) 

    # Add them to the new graph 
    TC.add_edges_from(edges) 

Обратите внимание, что set в Python является контейнером для уникальных значений, таким образом, set(a) - set(b) будет удалить записи из b из a.

для цикла, чтобы извлечь все соседи соседей может быть уменьшена, и (вероятно, ускорив) немного больше, используя список понимание:

all_nh = [z for y in G.neighbors(x) for z in G.neighbors(y)] 

Уступая что-то вроде этого:

def transitive_closure(G): 
    TC = G.copy() 
    for x in G: 
     all_nh = [z for y in G.neighbors(x) for z in G.neighbors(y)] 
     all_nh = set(all_nh) - set([x]) - set(G.neighbors(x)) 
     edges = map(lambda z: (x, z), all_nh) 
     TC.add_edges_from(edges) 
    return TC