Przeszukiwanie skierowanych grafów

Szukam algorytmu, najlepiej już zaimplementowanego w bibliotece Pythona, który pomoże mi znaleźć najczęściej występujące podgrafy w danym zbiorze skierowanych grafów.

Skerowane grafy mają takie właściwości:

1. Mają węzeł główny, z którego krawędzie wyłącznie wychodzą.
2. Z wyjątkiem węzła głównego, węzły łączy tylko jedna krawędź.
3. Do każdego węzła prowadzi tylko jedna ścieżka.

Po angielsku:

A directed graph that satisfies the following constraints:

1. There is a single designated root node that has no incoming arcs.
2. With the exception of the root node, each vertex has exactly one incoming arc.
3. There is a unique path from the root node to each vertex in V.

Przykładowe drzewo:
https://ibb.co/JqzPpQr

Znalazłem taki algorytm:
https://www.philippe-fournier-viger.com/spmf/GSPAN_subgraph.php

Wydaje się odpowiedni, ale chcę was się poradzić. Jakbyście się za to zabrali?

Spróbuj tego:
https://networkx.org/documentation/stable/reference/introduction.html

lion137 napisał(a):

Spróbuj tego:
https://networkx.org/documentation/stable/reference/introduction.html

Dzięki. Najwyraźniej nie umiem szukać w Google.:(

Ja bym powiedział, żebyś dał całą treść zadnia lub kod, bo przeszukiwanie grafu jest proste jak but, to się szybko nauczysz.

.GodOfCode. napisał(a):

Ja bym powiedział, żebyś dał całą treść zadnia lub kod, bo przeszukiwanie grafu jest proste jak but, to się szybko nauczysz.

To tak naprawdę całe zadanie. Przeszukiwanie grafu jest może i proste, ale nie dla amatora. Dlatego szukałem gotowca.

Twój problem z przeszukaniem grafu jest prosty, nie szuka się gotowca, tylko znasz kombinatorykę?

masz 3 liczby i chcesz wyświetlić wszystkie liczby bez powtórzeń.
to masz [1, 2, 3] tablice, potem [2, 3], potem [3], czyli masz najpierw 3 wybory potem dwa, potem jeden 3*2*1 = 6 kombinacji, jeśli powiesz że mogą się powtarzać, czyli z powtórzeniami to masz [1,2,3], [1,2,3],[1,2,3], czyli 3*3*3 = 27 kombinacji, teraz robisz pętlą przejście po pierwszej tablicy, usuwasz jeden element i w następnej pętli iterujesz bez tego elementu, a jak masz z powtórzeniami to cały czas iterujesz o tablicy tej samej wielkości.

To jest przejście grafu, teraz masz jakieś punkty początkowe w innym problemie każda droga to taka liczba z tablicy [1,2,3,4,5] tyle ile drug, po wybraniu jednej znowu masz jakąś tablicę drug i tak.
Musisz dobrze opisać problem, żeby potem łatwiej było go rozwiązać, wszystko sprowadza się do przejścia po grafie każdy problem matematyczny, graf jest uogólnieniem wszystkiego.