Subarktomia izomorficzna

Question

W jaki sposób najszybciej znaleźć wszystkie proste ścieżki o długości 4 w skróconym grafiku? Jednym ze sposobów jest stworzenie wykresu prostej ścieżki o długości 4 i użycie funkcji vf2 izogermizmu subgraph. Czy jest to najlepszy/najszybszy sposób?

Nie mam węzła źródłowego, chciałbym wszystkie proste ścieżki o długości 4, które istnieją na całym wykresie.

W moich danych jest bardzo mało takich ścieżek i chciałbym móc je efektywnie powtórzyć.

Answer 1

Używanie funkcji podobnej do tej:

def simple_paths(start, length, visited=[]): 
    if length==0: 
     yield(visited + [start]) 
    else: 
     for child in children(start): 
      if child not in visited: 
       for path in simple_paths(child, length-1, visited + [start]): 
        yield(path) 

Można wymienić wszystkich prostych ścieżek długości 4 wywołując

for start in nodes(): 
    for path in simple_paths(start, 4): 
     print path 

Powyższe zakłada, że ​​nodes() zwraca iterable wszystkich węzłów w grafie, a children(x) zwraca iterable synów węzła x.

Stosując funkcję simple_paths() do powyższego wykresu prawidłowo Wynik:

['5', '9', '3', '1', '0'] 
['6', '5', '9', '3', '1'] 
['6', '5', '3', '1', '0'] 
['9', '5', '3', '1', '0'] 

Dowodzi to, że funkcja:

• szanuje skierowane krawędzie (na przykład nie wybierać ['6', '5', '1', '3', '9'])
• wybiera tylko proste ścieżki (np. . nie wybrać ['6', '5', '3', '1', '5'])

Answer 2

Można znaleźć odpowiednie docs tutaj :)

Simple Paths in NetworkX

zasadzie to tylko wyszukiwarka drzewo jakiegoś

można użyć list of nodes i zrobić

list_of_nodes = nodes(my_graph) 
for mysource in list_of_nodes: 
    for mytarget in list_of_nodes: 
     if source != target: 
      print all_simple_paths(my_graph,source=mysource,target=mytarget, cutoff=4) 

Jeśli chcesz wszystkie najkrótsze ścieżki o długości 4, możesz użyć ``all_pairs_shortest_path_```

paths = all_pairs_shortest_path(my_graph,cutoff=4) 
for k,v in paths: 
    if len(paths[k][v]) == 4: 
     print paths[k][v] 

Nie ma prawdziwego polecenia wbudowanego w celu wygenerowania wszystkich prostych ścieżek o określonej długości, ponieważ jedynym sposobem znalezienia jest wygenerowanie drzewa z każdego węzła, np. robi zmodyfikowaną wersję mojej pętli for powyżej, ponieważ używa zmodyfikowanego pierwszego wyszukiwania głębi.

---

"Droga bez powtarzających się wierzchołków nazywany jest prosta ścieżka" - Wikipedia

Jeśli chcieliby Państwo paper citation. Jedynym sposobem sprawdzenia prostych ścieżek jest sprawdzenie z każdego węzła. Jeśli masz wykres z 90000 elementów; nie ma innego sposobu sprawdzenia, czy dwa łączą się: /. "Cel" nie jest tak naprawdę konsekwencją, ponieważ jest tylko kolejnym punktem odcięcia, ale jeśli masz dużą liczbę węzłów, to może to coś zmienić, więc jesteś na miejscu :).

" def _all_simple_paths_graph(G, source, target, cutoff=None): 
     if cutoff < 1: 
      return 
     visited = [source] 
     stack = [iter(G[source])] 
     while stack: 
      children = stack[-1] 
      child = next(children, None) 
      if child is None: 
       stack.pop() 
       visited.pop() 
      elif len(visited) < cutoff: 
       if child == target: 
        yield visited + [target] 
       elif child not in visited: 
        visited.append(child) 
        stack.append(iter(G[child])) 
      else: #len(visited) == cutoff: 
       if child == target or target in children: 
        yield visited + [target] 
       stack.pop() 
       visited.pop()" 

powyższy kod z networkx docs

zmodyfikować go w celu wygenerowania DFS bez 'docelowej' odcięcia można użyć:

def _all_simple_paths_graph(G, source, target, cutoff=None): 
     if cutoff < 1: 
      return 
     visited = [source] 
     stack = [iter(G[source])] 
     while stack: 
      children = stack[-1] 
      child = next(children, None) 
      if child is None: 
       stack.pop() 
       visited.pop() 
      elif len(visited) < cutoff: 
       #if child == target: 
       # yield visited + [target] 
       #elif child not in visited: 
       if child not in visited: 
        visited.append(child) 
        stack.append(iter(G[child])) 
      #else: #len(visited) == cutoff: 
       #if child == target or target in children: 
       # yield visited + [target] 
       #stack.pop() 
       #visited.pop() 

---

nadzieja, że ​​pracuje dla Ciebie:)

Answer 3

Na początku, niech rozwiąże problemu bardziej prostszy - obliczyć liczbę ścieżek o długości 4.

1) Niech A będzie macierzą sąsiedztwa danego wykresu. A[i][j] = 1 jeśli istnieje krawędź między wierzchołkami I i J i 0 w przeciwnym razie. A^N podaje liczbę ścieżek o długości N dla niektórych stałych długości.

2) Macierz kwadratury wygląda

init(RES,0); 
for(row=1;N) 
     for(col=1;N) 
     for(common=1;N) 
      RES[row][col] + = a[row][common]*a[common][col]; 

Znaczenie fizyczne jest taka konstrukcja jest następujący:
Dla każdego stopnia deg danego matrycy A, A[i][j] przechowuje liczby ścieżek o długości = deg z i to j . W pierwszym etapie macierz sąsiedztwa zapisuje tylko liczbę ścieżek o długości = 1. Gdy mnożysz A^N to A, próbujesz przedłużyć ścieżki o długości N to N+1.

a[row][common]*a[common][col] można enterpreted jako „nie a[row][common] sposoby len = 1 z row do common i a[common][col] sposoby len = 1 z common do col. Według kombinatoryki mnożenie liczby zasadę sposobów z len = 1, od rzędu do COL a[row][common]*a[common][col] ".

Teraz ważna modyfikacja. Chcesz wyświetlić wszystkie ścieżki, nie tylko je policz! Zatem A [i] [j] nie jest liczbą całkowitą, ale vector lub ArrayList z liczb całkowitych. Zastąp RES[row][col] + = a[row][common]*a[common][col] z RES[row][col].push_back(cartesian_product(a[row][common],a[common][col])) Złożoność samych ścieżek zliczających to matrix multiplication*degree = N^3 * stopień. Stosując potęgowanie binarne można uzyskać N^3 * log (stopień). W naszym przypadku stopień = 4, log (4) = 2, 2 ~ 4 - nie ma znaczenia. Ale teraz nie możesz po prostu pomnożyć 2 numerów, które powinieneś zrobić, kartezjańskim iloczynem wektorów - ścieżek len N. Tak więc złożoność wzrasta do N w zwykłym przypadku, ale w naszym przypadku do 4)

Jeśli masz jakieś pytania, zapraszam .

Answer 4

Jeśli potrzebujesz tylko ścieżek o długości dokładnie 4, możesz łatwo znaleźć wyniki, znajdując najpierw wszystkie ścieżki o długości dwóch, a następnie łącząc je ze sobą. Teoretycznie można to zrobić dla dowolnych długości, ale byłoby to bardziej chaotyczne (prawdopodobnie skończyłoby się budowanie kilku list potęgi-dwóch, a następnie łączenie ich w celu uzyskania innych długości).

Nie jestem bardzo biegły z NetworkX lub iGraph, ale oto jak zrobiłbym to na wykresie określonym przez listy sąsiedztwa (gdzie n1[i] jest iterable zawierający wszystkie węzły, które mają przewagę zamiar nich od węzła i).Myślę, że powinno być łatwo zamapować to na odpowiedni interfejs API.

n1 = adjacency_lists() 
n2 = [[(a, b) for a in x for b in n1[a] if i != b] for i, x in enumerate(n1)] 
n4 = [[(a, b, c, d) for (a, b) in x for (c, d) in n2[b] 
     if i != c and i != d and a != c and a != d] 
     for (i, x) in enumerate(n2)] 

W if klauzul listowych upewnić się, że ścieżki są proste. Przyjąłem, że nie ma żadnych krawędzi od węzła do samego siebie. Jeśli to nie jest prawdą, dodaj do listy ze zrozumieniem dodatkową klauzulę if i != a (przed for b in n1[a]) i dodaj a != b do istniejącej klauzuli .

Można wyjście ścieżki z:

for i, paths in enumerate(n4): 
    for a, b, c, d in paths: 
     print("{}->{}->{}->{}->{}".format(i, a, b, c, d)) 

Obliczenia powinny mieć asymptotycznej czas pracy O(N*D^4) gdzie N jest liczba węzłów i D jest maksymalny stopień węzłów (co jest najlepsze, co możesz zrobić , Myślę). Wątpię, by było znacznie szybsze rozwiązanie w czystym Pythonie. Rozwiązanie wykorzystujące wywołania biblioteki graficznej zaimplementowane w języku C może być szybsze o (prawdopodobnie duży) stały współczynnik.