C programozási kihívás
Feladat
Írj egy C nyelvű programot, amelyik egy parancssori argumentumként megadott fájlban definiált gráf
átlagos klaszterezettségi együtthatóját határozza meg és írja ki a képernyőre! A gráfok mérete változó lehet.
A program legyen képes nagy méretű (akár több millió csomópontból álló) gráfokat minél gyorsabban feldolgozni!
Definíciók
Szomszéd
Az i. és a j. csomópont szomszédai egymásnak, ha létezik őket közvetlenül összekötő él.
Fokszám
Az i. csomópont fokszáma (k
i) nem más, mint szomszédainak a száma.
Klaszterezettségi együttható
Az i. csomópont klaszterezettségi együtthatója (C
i) azt mondja meg, hogy milyen valószínűséggel szomszédai egymásnak az i.
csomópont szomszédai. Vagyis először meg kell számolni, hogy az i. csomópont közvetlen szomszédait hány él köti össze egymással,
majd ez el kell osztani k
i*(k
i-1)/2 értékével. (C
i tehát egy 0 és 1 közzé eső szám.) A klaszterezettségi
együtthatót nem értelmezzük azoknál a csomópontoknál, amelyeknek a fokszáma kevesebb, mint 2.
Átlagos klaszterezettségi együttható
A gráf átlagos klaszterezettségi együtthatója (ACC) a legalább 2 szomszéddal rendelkező csomópontjainak klaszterezettségi együtthatóiból
számolt számtani közép. (Azaz az értelmezhető C
i értékek átlaga, egyetlen 0 és 1 közé eső valós szám.)
Input
Egy gráfot leíró adatokat egy szöveges fájl tartalmazza olyan módon, hogy az egyes sorai a fájlnak a gráf egy-egy éle által
összekötött csomópontpár azonosítóit tartalmazzák ("%d\t%d\n" formában, azaz a fájl végén lehet üres sor is). A csomópontok
azonosítója egy nem negatív egész szám (gyakorlatilag 0-val kezdődő sorszám). A fájlban az élek sorrendje tetszőleges is lehet és
egy él két végét jelentő csomópontazonosítók sem biztos, hogy rendezetten szerepelnek az adott sorban. A mintagráfokban előfordulnak
olyan csomópontok, amelyeknek akár több ezer szomszédja/kapcsolata is van, de a csomópontok többségéhez csak néhány él kapcsolódik
(azaz skála-független hálózatokról van szó).
A gráfok irányítatlanok és egy adott csomópontpár között maximum 1 él lehet valamint a gráf nem tartalmaz hurkot, izolált csomópontot/részgráfot.
Beküldés
Ha a programod a minta gráfokra helyes eredményt ad, akkor küld el e-mailben a nevedet, neptunkódodat és forráskódot!
Irodalom:
