Studoši

Jel ima jos netko kome radi na malom primjeru, ali na velikom primjeru krivo izbacuje cvorove/krivo racuna centralnost? Pokusavam shvatit u cemu je problem i fixat vec dan i pol, izmijenila sam svasta, cini mi se kao da na velikom primjeru ne pronalazi dobro najkrace puteve (prvo nadem sve puteve, a onda izracunam koji je najkraci)…

Kako ste implementirali pronalazak svih najkraćih puteva između 2 čvora? Jel ima neki jednostavni, tried and true način? Stalno mi negdje puca pa pretpostavljam da mi pristup nije dobar, a i voljela bih ne imat milijun for petlji :/

temari Nije optimalno, ali je moguće BFS pokretati iz svakog čvora do svakog čvora (EDIT: nije potrebno iz svakog u svaki jer je graf neusmjereni) uz modifikaciju da se ne završi kada je pronađen prvi put nego da se algoritam izvrti do kraja i onda sve pronađene puteve spremaš u listu puteva. Prije dodavanja puta u listu provjeriš koliko je dug put/putevi u listi pa onda na temelju toga ili dodaješ ili ne dodaješ novodobiveni put.

Kako se kod izgradnje grafa računa sličnost vektora?
Kaže “na Slici 9 vidimo da je maksimalan iznos mjere sličnosti vektora svojstava jednak 5.”. Kako to kad ne postoje 2 vektora (svi su duljine 5) koji su isti?

pushPop Mislim da je to kao imaš 5 elemenata u vektoru i njih najviše 5 može bit isto između 2 vektora, tako da je max sličnost 5. Ne gledaš ove konkretne vektore nego sve moguće i think

in1 Da li si koristio 2d matricu za prikaz grafa ili nešto drugo, ako si koristio 2d polje jel imaš link za neki dobar pseudokod, slomih se dok sam trazio BFS za 2d polje

gagotron
Koristih:
HashMap<Integer, List<Node>> connections = parsedInput.connections;
HashMap<Integer, int[]> properties = parsedInput.properties;

Uzeo sam kod koji sam imao sa 1. labosa umjetne i njega sam preuredio na ovaj način in1

Kakvav je labos po težini naspram prijašnjih?

adidas Upute imaju 10 stranica
nuff said

Jel netko moze objasniti kako izračunati modularnost (točno)? Ja za mali primjer i ručno i u programu uporno dobivam u zadnjoj iteraciji 0.30469 umjesto 0.124 kako piše u primjer. Izbacivanje bridova tj. ostatak zadatka mi je točan.
Računam k_u*k_v za sve kombinacije vrhova (i kad je u=v i kada je (u,v)=(v,u) tj. duplo ). U svakoj iteraciji imam drugačiji m i k, po iteracijama mi je m= 22,20,16, a vektor k=[8, 5, 14, 7, 10], [8, 3, 14, 7, 8], [8, 3, 10, 3, 8]

tbauman https://fer.studosi.net/d/3899-avsp-pitanja-i-odgovori/101 kolega je ovdje objasnio da su u mailu rekli da se kroz iteracije m i tezine bridova ne mijenjaju ( sto je malo glupo), tako da samo mijenjaš deltu a ostale podatke izvuces iz pocetnog grafa i tjt.

Jel se ikom dogodilo za manji primjer da su prva i zadnja modularnost dobre, a u drugoj iteraciji ispadne -0.0909

Bono ovo se meni dogodilo, pogledaj Sipa31. Ukratko, nemoj mijenjati varijablu A{uv} kad uklanjaš bridove s gridova. Konkretno za tebe, kad izbrišes brid (2,5) u prvoj iteraciji, nemoj mijenjat A_{25}, tj. nemoj zamijenit težinu od brida (2,5) s nulom kao što sam ja radio.

Pomoću nekog algoritma nađem dužinu najkraćeg puta svih parova čvorova u grafu.
Kada tražim bridove koji su uključeni u neki put onda to radim rekurzivno? (ili moram prepraviti algoritam pronalaska najkraćih puteva tako da mi odma pamti i bridove u najkraćem putu?)

Da li su u početku algoritma svi čvorovi u jednoj zajednici za mali primjer? Za veliki ne bi smjeli biti jer ima izoliranih čvorova. I ako su svi u zajednici, kako se dogodi da je modularnost u prvoj iteraciji?
EDIT: na zaokruživanju na 4 decimale ispadne 0, da ne bi u nekog drugog izazvalo tilt ko u mene

Može neko pojasniti malo izračun bridne centralnosti?

Rezultat koji dobijem mi ovisi o redoslijedu na koji obilazim čvorove, a probao sam i ručno riješiti pa dobivam iste rezultate kao u kodu. Ne mogu nikako replicirati ovaj njihov primjer što su stavili u pripremi.

korisnickoime

1. izračunaš najkraće puteve od svakog čvora do svakog čvora
2. za svaki najkraći put, bridovima na tom putu dodaješ 1/N gdje je N broj najkraćih puteva između ta dva vrha

Ispod imaš najkraće puteve i vrijednosti bridne centralnosti po koracima pa vidi što ti ne štima.

ja ne dobijem rješenje za t.in kao t.out nego je isto kao i rješenje iz zadatka (gdje je napisan primjer za izlaz i modularnost). ne razumijem zasto te dvije stvari nisu iste, jel netko skuzio o cem se radi?
na SPRUT-u mi je rješenje OK.

tbauman Poprilično sam siguran da gledaš u krivi t.out jer su rezultati tamo jednaki kao u uputi.

in1 Iz kojeg razloga su putevi od 1 do 4 i od 4 do 1 različiti u prvoj iteraciji?

in1 da, vidim sad. valjda sam skinula zip prije nego sto su ga promijenili jer se sigurno radi o istom zadatku