Gráf generálása

5.4. ábra - Gráf generálására használt osztályok

Gráf generálására használt osztályok

Mátrixsorozat generálása

A korrelációs klaszterezésnél alapvető kérdés, hogy különféle mátrixok esetén mi az optimális csoportosítás. Itt a különféle mátrixon érthetjük azt, hogy a teljes mátrixhoz képest mekkora aránya hiányzik az éleknek, vagy akár azt is, hogy mi a negatív élek aránya az összes élhez képest. Ez az osztály az utóbbi értéket változtatva generál egy gráfsorozatot, ahol a csak negatív éleket tartalmazó gráfból több lépésen keresztül csak pozitív éleket tartalmazó gráfot készít.

package hu.unideb.inf.optimization.clustering;
/**
 * A módszerek teszteléséhez tesztmátrixokat generál.
 * @author ASZALÓS László
 */
public class WriteMatrixSequence {

Ez az osztály csak egy metódust tartalmaz. Ennek nincs más dolga, mint a többi osztály metódusait összefogva megoldja a gráf mátrixsorozatának generálását. Ez a program a parancssoron négy paramétert vár: - a generált gráf méretét - az élek mekkora aránya hiányozzon a teljes gráfhoz képest - hány gráfot generáljon - az egyes fájlok milyen közös azonosítót tartalmazzanak

Mivel a felhasználói inputra épít a program, figyelni kell, hogy ezeket mind megkapja-e. Ha igen, akkor az adott méretnek megfelelő üres mátrixot generál. Szükség lesz a generált mátrixok fájlba írására (wm), egy Erdős-Rényi gráfgenerátorra, mely feltölti a paramétereknek megfelelően az üres mátrixot, majd a munka dandárját a wm osztálya végzi el:

/**
 * Kiírja a paraméterek szerint generált mátrixot fájlba.
 * @param args a generáláshoz szükséges paraméterek
 */
public static void main(final String[] args) {

    if (args.length != 4) {
        System.err.println("Generate random matrix\n"
                + " Parameters: size, rate of zeros, "
                + " number of matrices and id (string)");
        System.exit(1);
    }
    int size = Integer.parseInt(args[0]); // meret
    MatrixByte m = new MatrixByte(size);
    WriteMatrix wm = new WriteMatrix();
    int zeros = Integer.parseInt(args[1]); // nullák aranya
    ErdosRenyi er = new ErdosRenyi();
    er.generate(m, zeros);
    int number = Integer.parseInt(args[2]); // ismétlés száma
    wm.printMatrices(m, number, args[3]);
}}

Erdős-Rényi gráfgenerálás

Talán a legegyszerűbb módszer gráfok generálására az Erdős-Rényi módszer. Végigmegyünk az összes csúcspáron és a véletlen alapján élet húzunk közéjük:

package hu.unideb.inf.optimization.clustering;
import static hu.unideb.inf.optimization.clustering.Constants.SURE;
import java.util.Random;
/**
 * Erdős-Rényi módszernek megfelelő mátrixgenerálás
 * @author ASZALÓS László
 */
public class ErdosRenyi {

Az osztálynak egyetlen metódusa van, mely a paraméterként kapott mátrixot a másik paraméter által meghatározott eséllyel feltölti, feltéve ha ez az érték megfelel egy valószínűségnek.

A metódus működése igen egyszerű: dupla ciklusban bejárjuk a mátrix felső háromszög részét, és vagy nem kerül él a két ciklusváltozó által meghatározott csúcsok közé, vagy negatív él kerül be. Mivel a mátrix szimmetrikus, azt az egy élet két helyen is le kell könyvelnünk.

Végül a véletlen mátrixba kerülő hurkokat töröljük:

/**
 * Szimmetrikusan feltölti a mátrixot véletlen elemekkel!
 * @param zeros nullák aránya
 */
public void generate(Matrix m, int zeros) {
    Random rnd = new Random();
    int i, j;
    if (zeros > SURE || zeros < 0) {
        throw new IllegalArgumentException(
                "The argument " + zeros + " must be between 0 and"
                + SURE + ".");
    }
    for (i = 0; i < m.getSize(); i++) {
        for (j = i + 1; j < m.getSize(); j++) {
            if (rnd.nextInt(SURE) < zeros) {
                // nulla következik
                m.setXY(i, j, (byte) 0);
                m.setXY(j, i, (byte) 0);
            } else {
                // kettes jön
                m.setXY(i, j, (byte) 2);
                m.setXY(j, i, (byte) 2);
                // listába betenni az elemet
            }
        }
        m.setXY(i, i, (byte) 0); // átló
    }
}}

Mátrixsorozat mentése

Az osztály megkap egy gráfot, melynek csak negatív élei vannak. Aztán lépésről lépésre ezeket az éleket átnevezi pozitívra, hogy a végén csak ilyen élei legyenek a gráfnak. Minden egyes köztes gráfot fájlba írunk:

package hu.unideb.inf.optimization.clustering;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
 * Általános mátrixkiíró osztály (fájlba menti a mátrixokat
 * @author ASZALÓS László
 */
public class WriteMatrix {

A negatív élekből megkonstruálunk egy listát, melyet szép lassan kiürítünk:

private List<Integer> twos = new ArrayList<Integer>();

A gráf éleinek számát tárolja ez a változó:

private int edges;

A WriteMatrixSequence osztálytól csak a mátrixot kapjuk meg. A mátrix felső háromszögén végighaladva megkeressük az éleket, és ha egyre ráakadunk, akkor azt a listában tároljuk. A könnyebb kezelhetőségért a két csúcs azonosítójából egy számot generálunk, és ezt használjuk. Mikor bejártuk a félmátrixot, megtudjuk, hogy hány él van valójában a gráfban:

/**
 * A mátrixban szereplő ketteseket egy listába gyűjtjük
 * @param m a gráf mátrixa
 */
void searchForTwos(Matrix m) {
    for (int i = 0; i < m.getSize(); i++) {
        for (int j = i + 1; j < m.getSize(); j++) {
            if (2 == m.getXY(i, j)) {
                twos.add(i * m.getSize() + j);
            }
        }
    }
    edges = twos.size(); // ezzel kell számolni a későbbiekben
}

Ha 10 lépésben akarjuk egyenletesen a negatív éleket átírni pozitívra, akkor minden lépésben az élek tizedét kell átírnunk. A metódus number paramétere adja meg ezt a lépésszámot. Így szükségünk van egy ciklusra, melynek a felső határát az élek és a lépés számának hányadosa adja. Ennyiszer kell kiválasztani egy véletlen elemet a listából, azt visszaalakítani számpárrá, és a neki megfelelő mátrixelemet átírni pozitívra:

/**
 * A mátrixban a megadott számnak megfelelő arányban átírja a ketteseket
 * egyesekre.
 * @param m mátrix
 * @param number arány
 */
void nextLabeling(Matrix m, int number) {
    Random r = new Random();
    for (int k = 0; k < Math.round(((float) edges / number)); k++) {
        if (!twos.isEmpty()) {
            int t = r.nextInt(twos.size());
            int s = twos.remove(t);
            int i = s / m.getSize();
            int j = s % m.getSize();
            m.setXY(i, j, (byte) 1);
            m.setXY(j, i, (byte) 1);
        }
    }
}

A segédmetódusok mind kész vannak. A mátrix éleinek felmérése után egy ciklus indul, ami akkor ér véget, ha már nincs a mátrixnak negatív éle. A ciklusban meghatározzuk a pozitív élek arányát, hogy az majd a gráf elnevezésében megjelenhessen. Majd a gráfra vonatkozó adatokat egy fájlba írjuk, és ezt követi a mátrix maga, szerencsés módon a toString felhasználásával.

Ha van még negatív él, akkor végrehajtunk egy lépést, egyébként kilépünk:

/**
 * A paramétereknek megfelelő fajtájú és számú mátrixot ír ki fájlba.
 * @param m a feladat mátrixa
 * @param number generált mátrixok száma
 * @param id azonosító a generált fájlok nevében
 */
void printMatrices(Matrix m, int number, String id) {
    boolean notFinal;
    String name = "m" + m.getSize() + id + "-";
    String fullname;
    searchForTwos(m);

    do {
        int q = Math.round(100 * (1 - ((float) twos.size() / edges)));
        fullname = name + String.format("%03d.tab", q);
        try {
            FileWriter fstream = new FileWriter(fullname);
            BufferedWriter out = new BufferedWriter(fstream);
            out.write("% " + fullname + "\n");
            out.write("% Rate of positive links: " + q + "\n");
            out.write(m.getSize() + "\n");
            out.write(toString());
            out.close();
        } catch (Exception e) {
            System.err.println("Error: " + e.getMessage());
        }
        notFinal = !twos.isEmpty();
        nextLabeling(m, number);
    } while (notFinal);
}}

Barabási-Albert modell

A valós életben előforduló mátrixok nem követik az Erdős-Rényi modellt. Ezért bemutatunk egy másik, kicsit bonyolultabb módszert is. Az 1999-ben publikált eredmény jelentősen megmozgatta a tudományos világot. Noha az algoritmus nem a legpontosabban adott. Így kisebb változtatásokkal/pontosításokkal implementáljuk itt a skálafüggetlen gráfokat:

package hu.unideb.inf.optimization.clustering;
import java.util.Arrays;
import java.util.Random;
/**
 * Szimmetrikus mátrixok generálása a Barabási-Albert modell szerint.
 * @author ASZALÓS László
 */
public class BarabasiAlbert {

A módszer sokkal összetettebb mint a Erdős-Rényi módszer. Ha egy csúcs már sok más csúccsal össze van kötve, akkor a gráf új csúcsai is szívesen fogják választani. Ezért nyilván kell tartanunk, hogy mi a csúcsok fokszáma:

private int[] connectivity;

Paramétere a módszernek a kiinduló csúcsok száma, melyek már megtalálhatóak a gráfban a generálás kezdetén. Arról, hogy ezek egymással összekötöttek-e vagy sem, az eredeti cikk nem ad információt. A kiinduló csúcsok számát az alábbi változó tárolja:

private int m0;

Másik paramétere a módszernek az, hogy az új csúcsot hány korábbi csúccsal köti össze. Ezt az alábbi változó tárolja:

private int m;

Azt, hogy a soron következő új csúcsot mely régi csúcsokkal kötjük össze, az alábbi vektor tárolja:

private int[] next;

A mátrix generálásának paraméterei alapján megadjuk az m és m0 változóink értékét. A csúcsok száma megszabja, a connectivity vektor, az egy lépésben generált élek száma pedig a next vektor méretét. A programszövegből látható, hogy a connectivity akkumulált módon fogja tárolni a csúcsok fokszámát:

/**
 * Módszer inicializálása
 * @param m0 kiinduló csúcsok száma
 * @param m lépésenként generált új élek száma
 * @param N gráf csúcsainak száma
 */
private void init(int m0, int m, int n) {
    this.m0 = m0;
    this.m = m;
    connectivity = new int[n];
    for (int i = 0; i < m0; i++) {
        connectivity[i] = i;
    }
    next = new int[m];
}

Mivel m szomszédra van szükség, egy ciklusban van az érdemi rész. A csúcsok összfokszámától függő véletlen számot választunk, és megkeressük, hogy ez melyik korábbi csúcshoz tartozik. (Hasonló módszert alkalmaztunk a sztochasztikus hegymászó módszernél is.) Ha az új csúcsot ehhez a csúcshoz már hozzá akartuk kötni, akkor újra sorsolunk.

/**
 * A soron következő i-dik csúcsnak keresünk szomszédokat
 * @param i új csúcs sorszáma
 */
private void newEdges(int i) {
    Random r = new Random();
    boolean wrong;
    int v, h;
    for (int j = 0; j < m; j++) {
        do {
            v = r.nextInt(connectivity[i - 1]+1); 
            h = Arrays.binarySearch(connectivity, 0, i, v);
            if (h < 0) { next[j] = -h-1; } else { next[j] = h; }
            wrong = false;
            for (int k = 0; k < j; k++) {
                if (next[j] == next[k]) {
                    wrong = true;
                }
            }
        } while (wrong);
    }
}

Ha a connectivity vektor csak a fokszámokat tárolná, akkor könnyű helyzetünk lenne. De mivel ezeket akkumuláltan tárolja, kicsit meg kell kínlódni vele. Az előbbi metódus eredményeképpen a next tömb tartalmazza az új csúccsal összekötött csúcsokat. Első lépésben ezt a tömböt rendezzük.

Gondoljunk bele, ha az 5. és a 7. csúcs lesz összekötve az újjal, akkor csak ennek a két csúcsnak változik a fokszáma. Az akkumulált fokszám viszont megváltozik nemcsak ezeknél, hanem az 5. utáni összes csúcsnál. Az 5. és 6. akkumulált fokszáma eggyel nő, viszont a 7. és azt követő csúcsokét kettővel. Ezt fogja csinálni a következő dupla ciklus, a két szerencsés kiválasztott csúcsok közti akkumulált fokszámokat megnöveli először eggyel, majd kettővel, és így szépen sorba tovább. Természetesen nem feledkezhetünk meg az utolsó kiválasztottat követő csúcsokról sem, azokat az utolsó ciklus rendezi, végül az új csúcsról is gondoskodni kell.

/**
* A fokszámok frissítése
* @param i új szomszéd indexe
*/
private void updateConnectivity(int i) {
    Arrays.sort(next);
    for (int k = 0; k < next.length - 1; k++) {
        for (int j = next[k]; j < next[k + 1]; j++) {
            connectivity[j] += k + 1;
        }
    }
    for (int j = next[m - 1]; j < i; j++) {
        connectivity[j] += m;
    }
    connectivity[i] = connectivity[i - 1] + m;
}

A generálás nem áll egyébből, mint az előbb ismertetett metódusok összekapcsolásából. Az inicializálás után a hiányzó csúcsok mindegyikéhez meg kell keresni a szomszédjait, ezt duplán (szimmetrikus!) dokumentálni, majd rendbe rakni a nyilvántartást:

/**
 * Barabási-Albert féle szimmetrikus mátrix generálása
 * @param mat mátrix
 * @param m0 kiinduló csúcsok száma
 * @param m lépésenkénti új élek száma
 */
public void generate(Matrix mat, int m0, int m) {
    init(m0, m, mat.getSize());
    for (int i = m0; i < mat.getSize(); i++) {
        newEdges(i);
        for (int j : next) {
            mat.setXY(i, j, (byte) 2);
            mat.setXY(j, i, (byte) 2);
        }
        updateConnectivity(i);
    }
}}

Feladatok

  1. A Barabási-Albert módszernél a connectivity karbantartása költséges. Implementálja a módszert úgy, hogy ez a vektor ne a kumulált értékeket tartalmazza, hanem a konkrét szomszédok számát. (A kiinduló csúcsok esetén ez legyen 1-1, hogy a valószínűségek képletében ne legyen nullával osztás!) Ekkor a bináris keresés helyett lineárist kell alkalmazni, viszont a karbantartás leegyszerűsödik.

  2. Az előző implementációhoz készítsen egy kupachoz hasonló adatszerkezetet, mely a részfában szereplő kumulált összeget tartalmazza! Ennek karbantartása — az eredetitől eltérően — nem lineáris, hanem logaritmikus bonyolultságú lesz. Viszont ezen értékeket alkalmazva a keresés is logaritmikus bonyolultságú, hasonlóan a bináris kereséshez.