Grafy Rake Search

[Argento]

Grafy Rake Search potrafią zadziwić swoim stopniem skomplikowania i efektywności. Bardzo ogólnikowo znam pojęcia grafów matematycznych, ale nie potrafię zobrazować sobie co przedstawiają grafy Rake Search; tj. ich wierzchołki, krawędzie, kierunek krawędzi itd.

Wskaże mi ktoś z szanownych boincpipolów  :p_arr: jakiś kierunek do zrozumienia powyższych?

[MajkPascal]

Cofając się do postu ze stycznia: http://rake.boincfast.ru/rakesearch/forum_thread.php?id=54#294

Według mojego rozumowania: Każdy wierzchołek to diagonalny kwadrat łaciński. Krawędzie wskazują, które pary tworzą kwadraty ortogonalne.


Mnie zastanawia bardziej źródło danych dla tych grafów. Wygrzebałem listę pozytywnych wyników z ostatnich miesięcy: http://rake.boincfast.ru/rakesearch/files/odls/. Jest tam między innymi próbka o numerze odpowiadającym grafowi "kwiatka": http://rake.boincfast.ru/rakesearch/files/odls/R9_000040159_result.txt

Tyle, że według niej znaleziono tylko 2 pary. Gdzie jest pozostałe 60? Będę chyba kiedyś musiał napisać jakiś programik przeszukujący te wyniki, by na własnej skórze przekonać się co do powtarzalności kwadratów między próbkami.

[Argento]

Cofając się do postu ze stycznia: http://rake.boincfast.ru/rakesearch/forum_thread.php?id=54#294
Według mojego rozumowania: Każdy wierzchołek to diagonalny kwadrat łaciński. Krawędzie wskazują, które pary tworzą kwadraty ortogonalne.

Diagonalny, ortogonalny kwadrat łaciński... :dunno:. A ja sądziłem, że wiem czym są kwadraty łacińskie  :facepalm2:. Po drugie dlaczego dany wierzchołek jest w konkretnym miejscu konkretnego wzoru, grafu? Same wzory owych grafów są dla mnie chaotyczne a entropia tego chaosu jest wręcz niemieżalna  :dunno:. Przytoczony przez Ciebie "kwiatek

A na dodatek zdaję sobie doskonale sprawę, że wynika to z braków w mojej wiedzy.

http://rake.boincfast.ru/rakesearch/files/odls/R9_000040159_result.txt
Tyle, że według niej znaleziono tylko 2 pary. Gdzie jest pozostałe 60?

Kod [Zaznacz] Rozwiń

{
# ------------------------
# Detected pair for the square:
# ------------------------
{
0 1 2 3 4 5 6 7 8
1 2 5 6 3 8 0 4 7
4 3 1 7 8 6 2 5 0
2 8 7 4 5 1 3 0 6
5 0 4 8 6 3 7 1 2
                        6 4 8 0 2 7 1 3 5
                        8 7 3 1 0 2 5 6 4
3 5 6 2 7 0 4 8 1
7 6 0 5 1 4 8 2 3
}
# ------------------------
{
0 1 2 3 4 5 6 7 8
                        6 4 8 0 2 7 1 3 5
                        8 7 3 1 0 2 5 6 4
7 6 0 5 1 4 8 2 3
3 5 6 2 7 0 4 8 1
1 2 5 6 3 8 0 4 7
4 3 1 7 8 6 2 5 0
5 0 4 8 6 3 7 1 2
2 8 7 4 5 1 3 0 6
}

# Square 0 # 1

# Pairs found: 1
}
{
# ------------------------
# Detected pair for the square:
# ------------------------
{
0 1 2 3 4 5 6 7 8
1 2 5 6 3 8 0 4 7
8 3 1 7 0 6 2 5 4
2 8 7 4 5 1 3 0 6
5 0 4 8 6 3 7 1 2
                         6 4 8 0 2 7 1 3 5
                         4 7 3 1 8 2 5 6 0
3 5 6 2 7 0 4 8 1
7 6 0 5 1 4 8 2 3
}
# ------------------------
{
0 1 2 3 4 5 6 7 8
                         6 4 8 0 2 7 1 3 5
                         4 7 3 1 8 2 5 6 0
7 6 0 5 1 4 8 2 3
3 5 6 2 7 0 4 8 1
1 2 5 6 3 8 0 4 7
8 3 1 7 0 6 2 5 4
5 0 4 8 6 3 7 1 2
2 8 7 4 5 1 3 0 6
}

# Square 0 # 1

# Pairs found: 1
}
# ------------------------
# Total pairs found: 2
# Total squares with pairs: 2

Czy chodzi o te pary, które wyróżniłem...?  Czy para to znak, cyfra czy jest to cały ciąg jak powyżej...? Pytam, ponieważ już zaczynam wątpić czy w ogóle rozumiem kwadrat łaciński...

[MajkPascal]

Diagonalny, ortogonalny kwadrat łaciński... :dunno:. A ja sądziłem, że wiem czym są kwadraty łacińskie  :facepalm2:. Po drugie dlaczego dany wierzchołek jest w konkretnym miejscu konkretnego wzoru, grafu?

[...]

Czy chodzi o te pary, które wyróżniłem...?  Czy para to znak, cyfra czy jest to cały ciąg jak powyżej...? Pytam, ponieważ już zaczynam wątpić czy w ogóle rozumiem kwadrat łaciński...

Inaczej kwadrat grecko-łaciński, każda komórka zawiera parę, więc i cały kwadrat można uznać za parę kwadratów łacińskich (o te pary mi chodziło).
Co do lokalizacji wierzchołków, pierwsze co przychodzi mi do głowy to, że to tylko Gephi z którego korzystają do rysowania grafów tak te grafy optymalizuje. Z drugiej strony wygląda to wszystko zbyt pięknie by było kwestią przypadku.

Tutaj: http://rake.boincfast.ru/rakesearch/forum_thread.php?id=47 znalazłem post, który powinien rozwiać moje wątpliwości, wraz z zestawem wszystkich 48 kwadratów składających się na graf. Muszę tylko znaleźć czas by przeanalizować go krok po kroku.

[Argento]

MejkPascal, dziękuję. I ciemność stała się jaśniejsza  :parrrty:.