Csoportosítás megadása

A csúcsok csoportosítását, azaz a csúcsok diszjunkt halmazainak halmazát több módszerrel is meg lehet adni. Mivel most a számítógépes ábrázolás lebeg a szemünk előtt, olyan ábrázolásokban gondolkodhatunk, amely számokat, vagy biteket tartalmaz. Talán a mindenki számára nyilvánvaló ábrázolás az, amikor egy csúcshalmazt egy számmal azonosítunk, és minden egyes csúcsra megadjuk, hogy melyik halmazban található. Ez összességében nem jelent mást mint egy szám n-est, ha n csúcsa van a gráfnak.

Talán az olvasó már találkozott azzal a megoldással, hogy egy halmazt bitsorozattal ábrázolunk. Ebben az esetben ha egy adott szám a halmaz része, akkor a neki megfelelő sorszámú bit egyes, egyébként nullás. Esetünkben nem csak egy halmaz lehetséges, hanem több is. Legrosszabb esetben minden elem külön halmazban található, így n bitsorozatra van szükség. A bitsorozatra majd később bitvektorként hivatkozunk, és ezek rendezett sorozatára pedig bitmátrixként. Az alábbi ábra egy öt csúcsú gráf csúcsait csoportosítja. Négy csoportot alkot az öt csúcs. Ezt leírhatjuk egyszerűen öt számmal, illetve 25 bittel is. Amint látjuk az ábra alsó részén lévő mátrixban az adott sorban levő elem pontosan akkor egyes, ha a neki megfelelő sor azonosítója van felette a számjegyes ábrázolásban.

At utolsó sorban azért szerepel csak nullás, mert négyes számjegy nincs a fenti számsorban. Viszont van ebben a számsorban két nullás, így az első (nullással jelölt) sor nekik megfelelő első és harmadik eleme tartalmaz egyes.

5.5. ábra - A partíciót ábrázoló szám n-es és bitmátrixos megfelelője

A partíciót ábrázoló szám n-es és bitmátrixos megfelelője

A több különböző ábrázolás léte miatt létrehoztunk egy absztrakt osztályt, mely a közös metódusokat tartalmazza. A csoportosítás azonban nem független a gráf ábrázolásától, épp ezért jelölni fogjuk a gráf tárolási osztályát is.

5.6. ábra - Groups osztálydiagram

Groups osztálydiagram

Klaszterek megadása

A csoportosítás, azaz a csúcsok diszjunkt halmazainak halmazát több módon is megadhatjuk, így az itt ismertetett osztály absztrakt:

package hu.unideb.inf.optimization.clustering;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
/**
 * A particionálás feladatának megoldása egy csoportosítás.
 * @author DUSZA Anikó, SZATMÁRI László
 */
public abstract class Groups<Gr extends Groups, M extends Matrix> {

Célfüggvény értéke, változása

Egy-egy csoportosításhoz tartozik egy célfüggvény-érték, melyet nem kívánunk minden esetben újra és újra kiszámolni. Ezért a kiszámolt értéket tárolni fogjuk:

protected int value;

Ehhez megadunk egy getter függvényt:

/**
 * Lekéri a célfüggvény értékét.
 * @return célfüggvény értéke
 */
final int getValue() {
    return this.value;
}

Természetesen szükség lesz ennek az értéknek a meghatározására, amely természetesen függ a feladat gráfjától:

/**
 * Kiszámolja a célfüggvény értékét a mátrix és a csoportosítás alapján.
 * @param matrix
 */
abstract void calculate(M matrix);

Ezeket az értékeket fel fogjuk használni az egyes megoldások összehasonlítása során, így szükséges az alábbi metódust implementálni.

/** Összehasonlítás rendezéshez, melynél a célfüggvény szerint rendez.
 * @param g a másik csoportosítás, melyhez viszonyít
 * @return összehasonlítás eredménye
 */
final int compareTo(final Gr g) {
    return value - g.value;
}

Esetünkben a célfüggvény felbontható egymástól független részekre. Így lokális változás esetén nem kell az egész célfüggvényt újraszámolni, hanem annak csak kis részét:

/**
 * Mennyi konfliktust okoz így a <code>i</code>-dik elem?
 * @param i az elem indexe
 * @param matrix
 * @return konfliktusok száma
 */
abstract int conflicts(final int i, final M matrix);

Ahelyett, hogy a csoportosítást megváltoztatnánk, és alkalmaznánk az előbbi függvényt, majd visszaírnánk az eredeti értéket, alkalmazhatjuk az alábbi metódust:

/**
 * Mennyi konfliktust jelentene, ha ennél az <code>i</code>-dik helyen
 * <code>groupI</code> érték szerepelne?
 * @param i index
 * @param groupI érték
 * @param matrix
 * @return indexhez tartozó lehetséges konfliktusok száma
 */
abstract int possibleConflicts(final int i, final int groupI, final M matrix);

Az ilyen változtatással elért eltérést például az előbbi két függvény alkalmazásával lehet kiszámolni:

/**
 * Mennyit változna a célfüggvény,
 * ha az <code>i</code>-dik elem értéke <code>value</code> lenne?
 * @param i            index
 * @param value        új csoport azonosítója
 * @param matrix
 * @return             célfüggvény változása
 */
int diff(final int i, final int value, final M matrix) {
    //@author Koós Dániel, Szokol Péter
    return this.possibleConflicts(i, value, matrix)
            - this.conflicts(i, matrix);
}

Ezt a metódust a State osztályban lenne érdemes elhelyezni:

/**
 * Ha már ismert a célfüggvény értéke, és ismert a változás is,
 * akkor felesleges kiszámolni újra a célfüggvényt,
 * elég lenne változtatni rajta.
 * @param diff eltérés mértéke
 * @deprecated
 */
@Deprecated
final void correctValue(int diff) {
    this.value += diff;
}

Adatszerkezet módosítása

Időnként szeretnénk a csoportosítást alaphelyzetbe állítani, illetve egy másolatot készíteni róla, melyet majd tovább alakíthatunk az eredeti megváltoztatása nélkül:

/**
 * Az adatszerkezet kitakarítása
 */
abstract void clean();
/**
 * Klónoz egy csoportosítást.
 */
abstract Groups copy();

A csoportosítás egy-egy elemét lekérdezhetjük:

/**
 * Lekérdezi az <code>i</code>-dik elemet.
 * @param i elem indexe
 * @return <code>i</code>-dik elem értéke
 */
abstract int getX(final int i);

Valamint be is állíthatjuk:

/**
 * Beállítja az <code>i</code>-dik elemet <code>x</code>-re.
 * @param i elem indexe
 * @param x beállítandó érték
 */
abstract void setX(final int i, final int x);

Néhány esetben az előbbi beállítás költséges, ezért ekkor kezdetben érdemes az alábbi metódust használni:

/**
 * Beállítja az <code>i</code>-dik elemet <code>x</code>-re.
 * @param i            index
 * @param x            érték
 */
abstract void setFirstX(final int i, final int x);

Ugyanazon csoportosítást több módon is leírhatjuk, amit az alábbi metódus egységesít. Az elől szereplő csoportokat minél kisebb számmal fogjuk ábrázolni:

/**
 * A rekordot egy vele ekvivalens alakba konvertálja.
 */
void normalize() {
    int i;
    final int EMPTY = -1;
    int[] jump = new int[getSize()];
        Arrays.fill(jump,EMPTY);
    int counter = 0;

Feljegyezzük, hogy mely csoport mikor fordult elő először, és majd ennek megfelelően számozzuk át az egyes azonosítókat:

for (i = 0; i < getSize(); i++) {
    if (EMPTY == jump[getX(i)]) {
        jump[getX(i)] = counter; 
        counter++; 
    }
}
for (i = 0; i < getSize(); i++) {
    setX(i, jump[getX(i)]); 
}
}

Összevonunk két csoportot azáltal, hogy az első előfordulásait lecseréli a másodikra:

/** Áthelyezi a <code>old</code> csoport elemeit a
 * <code>new</code> csoportba
 *
 * @param old átirandó csoport azonosítója
 * @param New új csoport azonosítója
 */
void substitute(int old, int New) {
    for (int i = 0; i < getSize(); i++) {
        if (old == getX(i)) {
            setX(i, New);
        }
    }
}

Keresztezés, mutáció

A csoportosításokat elképzelhetjük, mint szám n-eseket. Ilyenkor a kereszteződés során két egymásnak megfelelő számot kell kicserélni, amit az alábbi metódus valósít meg:

/**
 * Az <i>i</i>-dik pozíción található elemet
 * kicseréljük a <i>g1</i> hasonló elemével
 * @param i csere pozíciója
 * @param g1 másik fél
 */
protected void swap(int i, Gr g1) {
    int temp = getX(i);
    setX(i, g1.getX(i));
    g1.setX(i, temp);
}

Egypontos kereszteződés esetén egy adott pontig kell kicserélni az egymásnak megfelelő elemeket:

/**
 * Egypontos kereszteződés a másik csoportosítással.
 * @param g1 másik csoportosítás
 */
void crossoverOnePoint(Gr g1) {
    Random r = new Random();
    int p1 = r.nextInt(getSize());
    for (int i = 0; i < p1; i++) {
        swap(i, g1);
    }
}

Kétpontos keresztezés során a két generált index között kell kicserélni az egymásnak megfelelő értékeket:

/**
  * Kétpontos kereszteződés a másik csoportosítással.
  * @param g1 másik csoportosítás
  */
 void crossoverTwoPoint(Gr g1) {
     Random r = new Random();
     int p1 = r.nextInt(getSize());
     int p2 = r.nextInt(getSize());
     int min = Math.min(p1,p2);
     int max = Math.max(p1, p2);
     for (int i = min; i < max; i++) {
         swap(i, g1);
     }
 }

Uniform keresztezés esetén pedig a véletlen dönt, hogy szükséges-e a csere, vagy sem:

/**
 * Uniform keresztezés a másik csoportosítással.
 * @param g1 másik csoportosítás
 * @param p csere valószínűsége
 */
void crossoverUniform(Gr g1, float p) {
    Random r = new Random();
    for (int i = 0; i < r.nextInt(getSize()); i++) {
        if (r.nextFloat() < p) {
            swap(i, g1);
        }
    }
}

A mutáció során a bármely elemet adott valószínűséggel egy másik csoportba tehetünk át:

/**
 * Az adatszerkezetünket véletlenszerűen megváltoztatjuk.
 * @param r mutáció foka
 */
void mutate(float r) {
    Random rnd = new Random();
    for (int i = 0; i < getSize(); i++) {
        if (rnd.nextDouble() < r) {
            setX(i, rnd.nextInt(getSize()));
        }
    }
}

Csoportosítás megadása

Az egyik keresési módszer akkor működik jól, ha egyeleműek a klaszterek:

/**
 * Csoportosítás feltöltése átlósan
 */
void fillDiagonal(){
    for (int i = 0; i < getSize(); i++) {
        setFirstX(i,i);
    }
}

A leginkább használt módszer esetén véletlen adatokkal töltjük fel:

/**
 * Csoportosítás feltöltése véletlen adatokkal
 */
void fillRandom() {
    Random rnd = new Random();
    for (int i = 0; i < getSize(); i++) {
        setFirstX(i, rnd.nextInt(getSize()));
    }
}

Tesztelés esetén konkrét csoportosítást külső állományból is betölthetünk. Ekkor a fájlban szereplő százalékjellel kezdődő sorokat figyelmen kívül hagyjuk. A fájlban szereplő első szám a gráf csúcsainak számát adja meg, míg a többi szám a csoportosítást jelöli:

/**
 * Rekord beolvasása fájlból.
 * @param filename az adatokat tartalmazó állomány neve
 * @throws FileNotFoundException ha a megadott állomány nem létezik
 */
void loadGroups(final String filename) throws FileNotFoundException {
    int n = -1;
    int counter = 0;
    int myValue;

    Scanner scanner = new Scanner(new FileInputStream(filename));
    while (scanner.hasNextLine()) {
        String sor = scanner.nextLine();
        if (!sor.startsWith("%")) {
            if (n > -1) { 
                String[] szamok = sor.split(" ");
                if (szamok.length > 0 && (szamok.length + counter) <= n) {
                    for (int i = 0; i < szamok.length; i++) {
                        myValue = Integer.parseInt(szamok[i]);
                        setFirstX(counter, myValue);
                        counter++;
                    }
                } else {
                    counter += szamok.length;
                }
            } else { 
                n = Integer.parseInt(sor);
                if (n < 0 || Constants.MAXSIZE < n) {
                    throw new IllegalArgumentException("Groups: " + n
                            + " is not valid size!");
                } else {
                    setSize(n);
                }
            }
        }
    }
    if (n != counter) {
        throw new IllegalArgumentException("Groups: in " + filename
                + " there are " + counter + " numbers instead of " + n);
    }
    scanner.close();
}

Kisebb csoportosítások esetén az adatokat konkrétan is megadhatjuk tesztesetekhez:

/**
 * Rekord feltöltése teszteléshez.
 * @param data adataink tömbje
 */
void dataGroups(final int[] data) {
    setSize(data.length);
    for (int i = 0; i < data.length; i++) {
        if (data[i] < data.length) {
            setFirstX(i, data[i]);
        } else {
            System.err.printf(" Number %d at position %d is too big!\n",
                    data[i], i);
            System.exit(1);
        }
    }
}

Konkrét gráfok esetén ismert a csúcsok száma, és a csoportosítás is ennyi elemből áll. Így ekkora adatszerkezetet kell létrehozni. Persze előtte érdemes megvizsgálni, hogy ezt megtehetjük-e, vagy sem:

/**
 * Rekord méretének megadása.
 * @param size a tömb mérete
 */
void sizeGroups(final int size) {
    if (size > Constants.MAXSIZE) {
        throw new IllegalArgumentException(
                "Groups: the size is too big, the maximal value: "
                + Constants.MAXSIZE);
    }
    setSize(size);
    //this.adat = new int[size];
}

Az előbbi metódusok mindegyike az alábbi metóduson alapul, mely létrehozza a kellő méretű adatszerkezetet:

/**
 * Inicializálja az adatszerkezetet.
 * @param size beállítandó méret
 * @see loadGroups (meghívja ezt, ha kiderül a méret)
 * @see dataGroups (meghívja ezt, ha kiderül a méret)
 * @see sizeGroups (meghívja ezt, ha kiderül a méret)
 */
abstract void setSize(int size);

Lekérdezések a csoportosítással kapcsolatban

Megkapjuk a gráf csúcsainak a számát:

/**
 * Lekérdezi a feladat méretét.
 * @return a mátrix mérete
 */
abstract int getSize();

Miután a megoldás jóságának jó mércéje a maximális csoport mérete, így ezt is implementálni fogjuk:

/**
 * Meghatározza a maximális csoportot.
 * @return a legnagyobb csoport mérete
 */
abstract int maxGroup();

Másik ilyen mérőszám a csoportok száma. A metódus a normalizálásra épít, így csak akkor ad jó értéket, ha a csoportosítás normalizált. Ekkor nincs más dolgunk, mint a legnagyobb csoport azonosítóját felhasználni:

/**
 * Megadja a csoportosításban szereplő csoportok számát.
 * @return csoportok száma
 */
final int numberOfGroups() {
    int max = 0;
    for (int i = 0; i < getSize(); i++) {
        if (getX(i) > max) {
            max = getX(i);
        }
    }
    return max + 1;
}

A szentjánosbogár algoritmusban szükség van két megoldás tárolására. Ez esetünkben az eltérő értékek számát jelenti:

/**
 * Kiszámítja a <code>g</code>-től mért távolságot.
 * @param g a másik csoportosítás, melyhez viszonyítunk
 * @return eltérés mértéke
 */
int distance(final Gr g) {
    int i = 0;
    for (int j = 0; j < g.getSize(); j++) {
        if (getX(j) != g.getX(j)) {
            i++;
        }
    }
    return i;
}

A rovarraj és a szentjánosbogár algoritmusban is van közelítés egy másik állapothoz. Ez a metódus az előbbi távolságot csökkenti. Ehhez egy véletlen helyről indulva megkeressük az első eltérést és megszüntetjük. Ha ilyen nincs, mert a két csoportosítás megegyezik, akkor nem teszünk semmit:

/**
 * Közelít egy lépésnyit a <code>direction</code> csoportosításhoz.
 * @param direction közelítés iránya
 */
void nearTo(final Gr direction) {
    Random rand = new Random();
    int maxStep = getSize();
    int i = rand.nextInt(maxStep);
    while (maxStep > 0) {
        if (getX(i) != direction.getX(i)) {
            setX(i, direction.getX(i));
            maxStep = 0;
        }
        i = (i + 1) % getSize();
        maxStep--;
    }
}

A tesztelést/debugolást segíti, ha olvasható a csoportosítás:

@Override
public final String toString() {
    StringBuilder st = new StringBuilder();
    // Egyszeruen kiírjuk a tömböt
    for (int i = 0; i < getSize(); i++) {
        st.append(getX(i));
        if (i < getSize() - 1) {
            st.append(",");
        }
    }
    st.append(" (");
    st.append(this.value);
    st.append(")");
    return st.toString();
}
}

Számsorozat ábrázolás

A csoportosítás legnyilvánvalóbb ábrázolása, amikor egy szám n-esként tároljuk. Ekkor a mátrix is egészek formájában áll elő:

package hu.unideb.inf.optimization.clustering;
import java.io.FileNotFoundException;
import java.util.Arrays;
/**
 * A csoportosítást szám <code>n</code>-esként ábrázolja.
 * @author DUSZA Anikó, SZATMÁRI László
 */
public class GroupsN extends Groups<GroupsN, MatrixByte> {

Az adatszerkezet egy egyszerű vektor:

private int[] data;

GroupsN konstruktorai

A legegyszerűbben egy hasonló csoportosítás alapján készíthetünk egy úgy csoportosítást:

private GroupsN(GroupsN g){
    this(g.getSize());
    value=g.value;
    System.arraycopy(g.data, 0, data, 0, g.getSize());
}

Melyet remekül felhasználhatunk másolat készítésére:

@Override
final Groups copy() {
    return new GroupsN(this);
}

A konstruktor megkaphat egy méretet:

/**
 * Méret megadása (generáláshoz).
 * @param size vektor mérete
 */
GroupsN(final int size) {
    sizeGroups(size);
}

De rendszerint teszteléskor megadhatunk egy konkrét vektort, vagy csoportosítást tartalmazó fájlt is:

/**
 * Konstruktor vektorral (teszteléshez).
 * @param data adataink tömbje
 */
public GroupsN(final int[] data) {
    dataGroups(data);
}

/**
 * Konstruktor fájllal (teszteléshez).
 * @param filename az adatokat tartalmazó állomány neve
 * @throws FileNotFoundException
 */
public GroupsN(final String filename) throws FileNotFoundException {
    loadGroups(filename);
}

A konstruktorok mindegyike közvetetten felhasználja ezt a metódust, mely beállítja a vektor méretét:

@Override
void setSize(int size) {
    data = new int[size];
}

GroupsN apróbb metódusai

Mivel most nem hivatkozunk más osztályra, itt kell implementálni a metódusokat. Törlésnél feltöltjük a vektort:

@Override
void clean() {
    Arrays.fill(data, 0);
}

Elég nyilvánvaló, hogy a méret a vektorunk hossza, ha az i-dik elemet írni/olvasni szeretnénk a vektor megfelelő elemét kell írni/olvasni. Itt az írás egyszerű, így a setX és setFirstX metódus egybeesik:

@Override
int getSize() {
    return data.length;
}

@Override
void setX(final int i, final int x) {
    data[i] = x;
}

@Override
void setFirstX(final int i, final int x) {
    setX(i, x);
}

@Override
final int getX(final int i) {
    return this.data[i];
}

Ha a legnagyobb csoport méretére vagyunk kíváncsiak, akkor a vektor minden eleméről fel kell jegyezni, hogy hova tartozik, ezeket összesíteni, és a maximális értéket megkeresni:

@Override
int maxGroup() {
    int max = 0;
    int[] size = new int[getSize()];
    for (int i = 0; i < getSize(); i++) {
        size[getX(i)]++;
    }
    for (int i = 0; i < getSize(); i++) {
        if (size[i] > max) {
            max = size[i];
        }
    }
    return max;
}

Célfüggvényérték metódusai GroupsN-ben

Az alábbi metódusra fogunk mindent visszavezetni, ám ez is támaszkodik a mátrix megfelelő metódusára. Valójában megvizsgáljuk az elem, a lehetséges csoportja és a többi elem és csoportja kapcsolatát:

@Override
int possibleConflicts(final int i, final int groupI,
        MatrixByte matrix) {
    int sum = 0;
    int groupJ;
    for (int j = 0; j < getSize(); j++) {
        groupJ = getX(j);
        sum += matrix.error(groupI, groupJ, i, j); 
    }
    return sum;
}

Ha a lehetséges csoport, az elem valódi csoportja, már meg is kapjuk a másik függvény értékét:

@Override
int conflicts(final int i, MatrixByte matrix) {
    return this.possibleConflicts(i, getX(i), matrix);
}

Míg a célfüggvény meghatározásához csak végig kell menni a mátrix felén és a konfliktusok számát összeszámolni. Itt is lehetne a korábbi függvényekre alapozni, de akkor dupla ennyi ideig tartana a számolás:

@Override
void calculate(MatrixByte matrix) {
    int myValue = 0; 
    int groupI, groupJ; 
    for (int i = 0; i < getSize(); i++) {
        groupI = getX(i);
        for (int j = i + 1; j < getSize(); j++) {
            groupJ = getX(j);
            myValue += matrix.error(groupI, groupJ, i, j);
        }
    }
    value = myValue;
}}

Bitmátrixos ábrázolás

Egyik lehetséges ábrázolás, melyben egy-egy csoport egy bitvektornak felel meg: annyiadik bit egyes, ahányadik elem tartozik a csoportjába. Hogy ezt az ábrázolást hatékonyan használhassuk, a gráf mátrixának bitmátrixos ábrázolására lesz szükség:

package hu.unideb.inf.optimization.clustering;
import java.io.FileNotFoundException;
/**
 * A csoportosítást bitvektorok halmazaként ábrázolja.
 * @author ASZALÓS László
 */
public class GroupsB extends Groups<GroupsB, MatrixBits> {

A csoportosítás adatait egy egyszerű bitmátrix tárolja:

protected BitMatrix bitMatrix;

GroupsB konstruktorai

Az aktuális csoportosítást létrehozhatjuk egy másik hasonló csoportosítás alapján:

GroupsB(GroupsB g){
    sizeGroups(g.getSize());
    value = g.value;
    bitMatrix = g.bitMatrix.copy();
}

Ezt a konstuktort a másolat készítésére fogjuk használni:

@Override
Groups copy() {
    return new GroupsB(this);
}

Konstruktor használhatja a gráf csúcsainak a számát is:

/** 
 * Méret megadása.
 * @param size adatszerkezet mérete
 */
GroupsB(final int size) {
    sizeGroups(size);
}

Továbbá alapvetően tesztekhez használhatunk vektorként megadott csoportosítást (kisebb méretek esetén), illetve fájlban megadott méretesebb csoportosításokat:

/** Vektor alapú konstruktor (teszteléshez).
 * @param data adataink vektora
 */
public GroupsB(final int[] data) {
    dataGroups(data);
}

/** 
 * Fájl alapú konstruktor (teszteléshez).
 * @param filename az adatokat tartalmazó állomány neve
 * @throws FileNotFoundException
 */
public GroupsB(final String filename) throws FileNotFoundException {
    loadGroups(filename); //setX-et használ
}

BitMatrix osztályon alapuló metódusok

Miután az ábrázolás egy másik osztályon alapul, így igen sok metódus attól az osztálytól függ, így csak továbbítjuk a feladatot:

@Override
void clean() {
    bitMatrix.clean();
}
@Override
int getSize() {
    return bitMatrix.getSize();
}
@Override
int getX(int i) {
    return bitMatrix.getX(i);
}
@Override
int maxGroup() {
    return bitMatrix.maxGroup();
}
@Override
void normalize() {
    bitMatrix.normalize();
}

@Override
void setSize(int n) {
    bitMatrix = new BitMatrix(n);
}

Ebben az esetben meg kell keresni a régi értéket, és törölni. Ez lassú folyamat. Épp ezért ellenőrizzük, hogy valóban szükség van-e törlésre:

@Override
void setX(final int i, final int x) {
    int j = getX(i);
    if ( j != x) {
        bitMatrix.setX(i, x, j);
    }
}

Első értékadáskor ezzel nincs baj:

@Override
void setFirstX(final int i, final int x) {
    bitMatrix.setXY(x, i); // új érték beállítása
}

Függvényértékkel kapcsolatos metódusok

Mint látható, a mátrixra bízzuk a függvény kiszámítását, amelynek átadjuk az az adott csoportot leíró bitsorozatot:

/**
 * <code>i</code>-hez tartozó konfliktusok száma
 *
 * @param i index
 * @param group csoport
 * @return konfliktusok száma
 */
int errors(final int i, final int group, MatrixBits matrix) {
    return matrix.errors(i, bitMatrix.getVector(group));
}

Az előbbi metódusra hivatkozunk, ha valós konfliktusok számára vagyunk kíváncsiak:

@Override
int conflicts(final int i, MatrixBits matrix) {
    return errors(i, getX(i), matrix); 
}

De akkor is, ha a jövőbeli konfliktusok száma a kérdéses:

@Override
int possibleConflicts(final int i, final int value, MatrixBits matrix) {
    return errors(i, value, matrix);
}

Az adott csoportosításhoz tartozó függvényérték a konfliktusok összege. De mivel egy konfliktust mindkét oldalról figyelembe veszünk, az így kapott értéket végül felezni kell:

@Override
void calculate(final MatrixBits matrix) {

    int myValue = 0;
    for (int i = 0; i < getSize(); i++) {
        myValue += conflicts(i, matrix);
    }
    value = myValue / 2;
}

A tesztelés során felhasználható ha valóban bitmátrixként látjuk a csoportosítást. Ezt írja ki az alábbi metódus:

/** Kiírja a bitmátrixot teszteléshez. */
void printGroups() {
    for (int i = 0; i < getSize(); i++) {
        System.out.printf("%3d: ",i);
        System.out.printf("%s\n", bitMatrix.getVector(i).toString());
   }
}}

Kombinált ábrázolás

Az előbb ismertetett mindkét ábrázolásnak vannak előnyei. Próbáljuk ezt ötvözni! Mivel a Java nem ismeri a többszörös öröklődést, egyik szülőtől öröklünk mindent, a másik szülőre vonatkozó attribútumot, metódust megismételjük:

package hu.unideb.inf.optimization.clustering;
import java.io.FileNotFoundException;
import java.util.Arrays;
/**
 * Kombinált ábrázolásmód.
 * @see GroupsB
 * @see GroupsN
 * @author ASZALÓS László
 */
class GroupsBN extends GroupsB {

A GroupsN-ben szereplő vektort megismételjük:

private int[] data;

Kombinált konstruktorok

Támaszkodhatunk az ős konstruktorára, csak a vektor másolásáért leszünk felelősek:

/** Az aktuális méretnek megfelelő csoportosítást készít.
 * @param g másolandó csoportosítás
 */
GroupsBN(GroupsBN g){
    super(g);
    System.arraycopy(g.data, 0, data, 0, data.length);
}

Az előbbi konstruktor használható fel a másolásra:

@Override
Groups copy() {
  return new GroupsBN(this);
}

Ha méretet adunk meg, akkor üres adatszerkezet generálódik, tehát nincs teendőnk a vektorral

/** Konstruktor mérettel.
 * @param size gráf csúcsainak száma
 */
GroupsBN(int size) {
    super(size);
}

Ha teszteléshez töltjük fel az adatszerkezetet, akkor a setX-et fogjuk használni, ezért azt kell úgy megadni, hogy végezze a kettős könyvelést (a bitmátrixban és vektorban is):

/** Konstruktor vektorral (teszteléshez).
 * @param data adatvektor
 */
public GroupsBN(int[] data) {
    super(data);
}

/** 
 * Konstruktor fájllal (teszteléshez).
 * @param filename az adatokat tartalmazó állomány neve
 * @throws FileNotFoundException
 */
public GroupsBN(final String filename) throws FileNotFoundException {
    super(filename); 
}

Ez a metódus, melyet minden konstruktor meghív, gondoskodik arról, hogy mindkét adatszerkezetet létrehozza:

@Override
void setSize(int n) {
    data = new int[n];
    super.setSize(n);
}

Apróbb metódusok kombinált esetre

Kiolvasásnál elegendő az egyik adatszerkezet használni, és mivel a vektor a gyorsabb hozzáférésű, egyértelmű a megoldás (ua mint GroupN-ben):

@Override
int getX(int i) {
    // mint GroupN-ben is.
    return data[i];
}

Ahogy írtuk, itt kell a kettős könyvelés, persze csak akkor, ha az előzőtől eltérő adatot írunk be.

@Override
void setX(final int i, final int x) {
    if (x != data[i]){
        bitMatrix.setX(i, x, data[i]); 
        data[i] = x;
    }
}

Kezdeti feltöltésnél nem kell vigyázni:

@Override
void setFirstX(final int i, final int x) {
    bitMatrix.setXY(x, i); 
    data[i] = x;
}

Ezt örökölhettünk volna a GroupN-ből, de mivel nem lehet, megismételjük:

@Override
void normalize() {
    int i;
    final int EMPTY = -1;
    int[] jump = new int[getSize()];
    Arrays.fill(jump,EMPTY);
    int counter = 0;
    for (i = 0; i < getSize(); i++) {
        if (EMPTY == jump[getX(i)]) {
            jump[getX(i)] = counter; 
            counter++; 
        }
    }
    for (i = 0; i < getSize(); i++) {
        setX(i, jump[getX(i)]);
    }
}
}