effiziente Weise alle Paare von Scheitelpunkten auszuwählen, die in einem zweiteiligen Netzwerk gemeinsame Nachbarn teilen

Question

ich alle Paare von Eckpunkten des gleichen Typs auswählen muß, die

Zum Beispiel in einem zweiteiligen Netzwerk gemeinsame Nachbarn teilen:

In diesem Diagramm I habe: (A, B), (A, C), (B, C), (C, D), (1,2) und (2,3)

I kann durch eine quadratische Lösung lösen:

import igraph 
import time 

def common_neighbors(adjlist, i, j): 
    return len(adjlist[i].intersection(adjlist[j])) 

def matching_1(graph, row, column): 
    adjlist = map(set, graph.get_adjlist()) 
    matching = [] 
    dict_edges = dict() 
    for i in range(row): 
     for j in range(i+1, row): 
      if common_neighbors(adjlist, i, j) > 0: 
       matching.append((i, j)) 
    dict_edges = dict() 
    for i in range(row, row+column): 
     for j in range(i+1, row+column): 
      if common_neighbors(adjlist, i, j) > 0: 
       matching.append((i, j)) 
    return matching 

def matching_2(graph, row, column): 
    adjlist = map(set, graph.get_adjlist()) 
    matching = [] 
    for vertex in range(row): 
     twohops = set((twohop for onehop in adjlist[vertex] for twohop in adjlist[onehop])) -set([vertex]) 
     for twohop in twohops: 
      matching.append((vertex, twohop)) 
    for vertex in range(row, row+column): 
     twohops = set((twohop for onehop in adjlist[vertex] for twohop in adjlist[onehop])) -set([vertex]) 
     for twohop in twohops: 
      matching.append((vertex, twohop)) 
    return matching 

if __name__ == "__main__": 

    row, column = 500, 500 
    graph = igraph.Graph.Full_Bipartite(row, column) 

    tp_start = time.time() 
    m = matching_1(graph, row, column) 
    print "%.4f" % (time.time()-tp_start) 

    tp_start = time.time() 
    m = matching_2(graph, row, column) 
    print "%.4f" % (time.time()-tp_start) 

Dies ist die logischste Art und Weise, wie ich es mir vorstellen kann. Wenn jemand einen effizienteren Weg kennt, bin ich ganz Ohr. Jede Hilfe wird sehr geschätzt.

Answer 1

Sie berechnen im Grunde die Kantenlisten der zwei bipartiten Projektionen Ihres ursprünglichen Netzwerks. IGRAPH verfügt über eine integrierte Methode für diese Annahme, dass Ihre Eckpunkte haben einen Vertex-Attribut namens type, welcher Teil des Diagramms beschreibt die Eckpunkte gehören:

>>> g=Graph.Formula("A--1--B--2--C--3--D, A--2") 
>>> g.vs["type"] = [name in "ABCD" for name in g.vs["name"]] 
>>> g1, g2 = g.bipartite_projection() 
>>> [tuple(g1.vs[pair]["name"]) for pair in g1.get_edgelist()] 
[('1', '2'), ('2', '3')] 
>>> [tuple(g2.vs[pair]["name"]) for pair in g2.get_edgelist()] 
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')]