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 (ki) nem más, mint szomszédainak a száma.

Klaszterezettségi együttható

Az i. csomópont klaszterezettségi együtthatója (Ci) 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 ki*(ki-1)/2 értékével. (Ci 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ő Ci é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.

Minta hálózatok letöltése

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:

Látogatási információ Frissí­tve: 2017.03.11