Graf nieskierowany - algorytm

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?

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.

@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.

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.

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:

 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.

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ć.

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 ;)

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.