Graf nieskierowany - algorytm

Graf nieskierowany - algorytm
Blue_Carpet
Blue_Carpet
Blue_Carpet
Blue_Carpet
  • Rejestracja:ponad 9 lat
  • Ostatnio:ponad 3 lata
  • Postów:132
0

Witam,
Mam następujący problem, dla którego nie mogę znaleźć szybko działającego rozwiązania, a mianowicie:
Wczytuję sobie graf w postaci listy incydencji.
Wszystkie krawędzie w grafie mają takie same wagi.
Następnie muszę dodać do tego grafu krawędzie w następujący sposób:
Tworzę krawędź pomiędzy dwoma wierzchołkami, nazwijmy je A i B jeżeli:
NIE ISTNIEJE taka krawędź oraz NAJKRÓTSZE przejście pomiędzy tymi dwoma wierzchołkami wymaga DOKŁADNIE JEDNEGO przejścia przez inny wierzchołek to znaczy, że tworzę krawędź pomiędzy wierzchołkami A i B jeżeli aktualnie najkrótsza ścieżka je łącząca wymaga przejścia tylko przez jeden inny wierzchołek czyli np. C.
Inaczej:
Istnieje ścieżka: A - C - B
To tworzę krawędź pomiędzy A i B, ponieważ najkrótsza ścieżka pomiędzy tymi dwoma wierzchołkami wymaga przejścia przez tylko jeden inny wierzchołek.
We wczytywanym grafie krawędzie nigdy nie krzyżują się oraz wczytywany graf jest spójny.
Tak się zastanawiam w jaki szybki sposób mógłbym sprawdzać, w których miejscach powinienem dodawać brakujące krawędzie. Aktualnie robię to tak, że sprawdzam po prostu każdy wierzchołek po kolei i jeżeli natrafię na kombinację, że np.: Wierzchołek_Sprawdzany, Wierzchołek_Sąsiad, Wierzchołek_Sąsiad_Sąsiada i nie ma krawędzi pomiędzy: Wierzchołek_Sprawdzany, a Wierzchołek_Sąsiad_Sąsiada to ją tworzę, bo aktualnie najkrótsza ścieżka łącząca te wierzchołki wymaga przejścia dokładnie przez jeden inny wierzchołek, a mianowicie: Wierzchołek_Sąsiad. Takie sprawdzanie po kolei tych możliwości daje bardzo dużą złożoność obliczeniową ;/. Ma ktoś jakiś inny pomysł na szybkie tworzenie brakujących krawędzi?

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
wartek01
W0
wartek01
W0
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 2 godziny
  • Postów:3550
0

Zaimplementuj liczenie odległości:
https://pl.wikipedia.org/wiki/Algorytm_Dijkstry

Każda krawędź ma wagę 1. Łączysz te wierzchołki których odległość jest równa dokładnie 2.

edytowany 1x, ostatnio: wartek01
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Blue_Carpet
Blue_Carpet
Blue_Carpet
Blue_Carpet
  • Rejestracja:ponad 9 lat
  • Ostatnio:ponad 3 lata
  • Postów:132
0

@wartek01
Ale wtedy Dijkstrę musiałbym puszczać z każdego wierzchołka, żeby wszystkie krawędzie stworzyć, a wierzchołków może być 100 000.

edytowany 1x, ostatnio: Blue_Carpet
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
wartek01
W0
wartek01
W0
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 2 godziny
  • Postów:3550
0
Blue_Carpet napisał(a):

@wartek01
Ale wtedy Dijkstrę musiałbym puszczać z każdego wierzchołka, żeby wszystkie krawędzie stworzyć, a wierzchołków może być 100 000.

Tak, ale ten algorytm dla tego konkretnego przypadku dałoby się pewnie zoptymalizować tak, żeby sprawdzał tylko czy jest 2 czy nie.

Blue_Carpet
ale w jaki sposób w tym sęk, bo patrz załóżmy, że puszczę Dijkstrę z wierzchołka nr 1 to wykryję tylko, że muszę dorysować krawędź pomiędzy 1 i 4 ;p
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
wartek01
W0
wartek01
W0
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 2 godziny
  • Postów:3550
1

Może i racja co do tego Djikstry. W takim razie można spróbować lecieć od środka:

Tj.

  1. Wybierasz wierzchołek A.
  2. Wybierasz parę wierzchołków sąsiądujących X, Y.
  3. Sprawdzasz, czy istnieje droga X -> Y

Druga opcja optymalizacji - użyć jakiejś struktury w której sprawdzenie, czy istnieje X -> Y nie będzie trwało N ale mniej. Np. wpakuj to do HashSet'a, a w Node:

Kopiuj
 public class Node {
	private final int nodeId;
	private Set<Node> neighbours = new HashSet<>(); 
	// ... 
	
	@Override
	public int hashCode(){
		return nodeId; 
	}
}

I wtedy nie iterujesz po wszystkich, ale używasz Set.contains(node) - to będzie dużo wydajniejsze niż zwykłe iterowanie.

Blue_Carpet
Kurcze nie wiem, coś kombinuje z tymi krawędziami bądź może z tym, że "krawędzie się nie krzyżują" musi być jakies rozwiązanie o złożoności liniowej / logarytmicznej.
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
wartek01
W0
wartek01
W0
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 2 godziny
  • Postów:3550
1

Ja bym pokombinował w ten sposób:

  1. Przechodząc z hashseta na tablicę N na N możesz zmniejszyć złożoność sprawdzenia dostępu do 1.
  2. Można też zmniejszyć ilość sprawdzeń.
    Dla pierwszego elementu sprawdzamy (zgodnie z podanym algorytmem) C(k[0]-1,2) (bo tyle jest możliwych par). Dla drugiego nie musimy już sprawdzać jedynki, czyli C(k[1]-2,2) gdzie k[i] - liczba sąsiadów i-tego wierzchołka.

Pesymistycznie (każdy wierzchołek łączy się z każdym innym) wyjdzie n^2, ale w przypadkach bardziej optymistycznych dużo mniej.

Można też próbować zapisać to w formie tablicy N na N i zobaczyć, czy się da z tego coś wyznaczyć.

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
wartek01
W0
wartek01
W0
  • Rejestracja:ponad 12 lat
  • Ostatnio:około 2 godziny
  • Postów:3550
0

Dodatkowo - można to zrobić bez tworzenia obiektów typu Node a przejście na coś trochę lżejszego.

  1. Ustawiasz wszystkie node'y w kolejności. Oznaczmy jeden node jako 1,2...i
    Tj. dla przykładu
    W(1), W(2), W(3), W(4), W(5)

  2. Do każdego node'a przypisujesz listę sąsiądujących node'ów, tj. L(W(i)) = {k(i, j) ... k(i, j(i)))}
    W(1) = {2,3}
    W(2) = {1,3}
    W(3) = {1,2,4}
    W(4) = {3,5}
    W(5) = {4}

  3. Filtrujesz każdą taką kolekcję odrzucając k(i, j) < i, tj.
    W(1) = {2,3}
    W(2) = {3}
    W(3) = {4}
    W(4) = {5}
    W(5) = {}

  4. Połączenia F(W(i)) = {W(k(i, 1))\W(i) ... W(k(i, j(i))\W(i)} tj.
    F(W(1)) = {{3}{2,3}, {4}{2,3}} = {{}, {4}} - tworzymy połączenie 1->4
    F(W(2)) = {{4}{3}} = {{4}} - tworzymy połączenie 2->4
    F(W(3)) = {{5}{4}} = {{5}} - tworzymy połączenie 3->5
    F(W(4)) = {{}{4}} = {{}} - brak połączeń

Takie operacje na zbiorach intów będą wydajniejsze - pamięciowo i obliczeniowo - od obiektów. Złożoność pesymistyczna będzie podobna jak przy poprzednim algorytmie, ale czas powinien być - w zależności od implementacji - krótszy.

Ps. tak, wiem że punkty 1,2,3 da się zrobić za jednym zamachem ;)

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
krsp
KR
krsp
KR
  • Rejestracja:ponad 8 lat
  • Ostatnio:około 4 godziny
  • Postów:166
0

Hmmm. Nie wczytywałem się w komentarze i może ktoś to opisał ale dla A i B.
Weż sąsiadów A, Weź sąsiadów B.
Jeżeli A ma sąsiada B to krawędź istnieje.
Sprawdź czy A i B ma jakiegoś wspólnego sąsiada C. Narysuj krawędź jeśli istniej wspólny sąsiad.

.edit Należy uwzględnić fakt że zmienia się graf. W sensie nie wiadomo czy mają być te zmiany uwzględnione czy nie (podejrzewam, że łatwiej jakby krawędzie byłyby dorysowane po wykryciu wszystkich brakujących - zmiana grafu nastąpiłaby po wykryciu wszystkich brakujących krawędzi).

.edit2 Albo jeszcze zmienić problem z wyszukiwania wspólnych sąsiadów na taki:
Masz C. Bierzesz sąsiadów C. Sprawdzasz czy sąsiedzi są połaczeni ze sobą. Jak nie to znaczy, że potrzebują krawędzi.

edytowany 4x, ostatnio: krsp
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Treść
Podgląd
Kliknij, aby dodać treść...
Kliknij, aby dodać załącznik lub wklej ze schowka.
Instrukcja obsługi Markdown
Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)