Gráf ábrázolása

A gráfok ábrázolására − a felhasznált műveletek figyelembe vételével − a szomszédsági mátrixot fogjuk használni. Mivel a gráf nem irányított, ezért ez a mátrix szimmetrikus lesz.

Konkrétan adott gráfok esetén azokat fájlból tudjuk beolvasni. A programrendszerünk részére létrehoztunk egy formát, ami a következőképpen néz ki: a fájl soronként értelmezendő. Egy sor megjegyzés, ha százalékjellel kezdődik. A nem megjegyzés sorok közül az első egy számot tartalmazhat, a mátrix méretét, azaz a gráf csúcsainak a számát. Az ezt követő nem megjegyzés soroknak ilyen hosszúnak kell lenniük, és ennyi ilyen sor lehet, mert így kapunk négyzetes mátrixot. A mátrix elemeit a 0, 1 és 2 számok jelölik, ezek a sorok csak ilyen karaktereket tartalmazhatnak. Az alábbi állomány egy öt csúcsú mátrixot jelöl:

% m5_303g.tab
% 3 groups
5
00010
00220
02010
% remark
12102
00020

A szomszédsági mátrixot tárolhatjuk egészek kétdimenziós tömbjeként, illetve majd ahogy a később látjuk bitekkel is ábrázolhatjuk. Ez utóbbi komplikáltabb ábrázolásnak az lesz az előnye, hogy bitműveletekkel jelentősen felgyorsíthatjuk az adatok feldolgozását. Viszont a különféle ábrázolások miatt bevezetünk egy absztrakt osztályt, mely a közös metódusokat tartalmazza. A soron következő alfejezetekben ezeket az osztályokat mutatjuk be, majd megadjuk, hogyan lehet adott tulajdonságú mátrixokat generálni.

5.3. ábra - Mátrix tárolására használt osztályok

Mátrix tárolására használt osztályok

Jelölt gráf ábrázolása mátrixszal

A korrelációs klaszterezési feladat inputja a mátrix, melynek elemei 1, 0 és -1 lehetnek. Ebben az absztrakt osztályban a különféle megvalósításokban közös metódusokat szerepeltetjük:

package hu.unideb.inf.optimization.clustering;
import static hu.unideb.inf.optimization.clustering.Constants.MAXSIZE;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.Scanner;

/**
 * A mátrix a particiós feladatunk inputját tárolja.
 * @author BÓNIS Balázs, SZOKOL Péter 
 */
public abstract class Matrix {

Mátrixok konstruktorai

Az öröklődés furcsaságai miatt szükséges volt megadni a legegyszerűbb konstruktort:

Matrix() {
}

Megtehetjük, hogy csak a mátrix méretét kapja meg a konstruktor. Jellemzően ekkor generáljuk a mátrixot:

/**
 * Beállítja a mátrix méretét.
 * @param size a mátrix mérete
 */
Matrix(final int size) {
       setSize(size);
}

Konkrét problémák megoldása esetén a mátrixot akár helyi, akár egy távoli gépről beolvashatjuk. Annak érdekében, hogy ne szülessenek fals számítások, mindkét konstruktor ellenőrzi, hogy a beolvasott mátrix valóban szimmetrikus-e vagy sem:

/**
  * Beolvassa a mátrixot külső fájlból.
  * @param filename a mátrixot tartalmazó fájl neve
  */
 Matrix(final String filename) {
     loadMatrix(filename);
     isSymmetric();
 }
/**
  * Beolvassa a mátrixot URL címről.
  * @param address a mátrixot tartalmazó fájl címe
  */
 Matrix(final URL address) {
     loadURLMatrix(address);
     isSymmetric();
 }

Egységtesztelés során jól használható, ha előre megadott mátrixokkal dolgozhatunk:

/**
 * Megadja a mátrixot konkrét adatokkal.
 * @param adat konstans tömb
 */
public Matrix(final int[][] adat) {
    storeMatrix(adat);
}

Segédmetódusok mátrixok konstruktoraihoz

A kivételek kezelése miatt mind a fájlból, mint a net-ről olvasó programok kicsit elbonyolítottak. A lényeg az, hogy egy közös metódusra vezetjük vissza mindkét feladatot:

/**
 * Olvassa be külső fájlból a mátrixot!
 * @param filename a mátrixot tartalmazó fájl neve
 */
protected final void loadMatrix(final String filename) {
    try {
        Scanner scanner = new Scanner(new FileInputStream(filename));
        loadStream(scanner, filename);
    } catch (FileNotFoundException e) {
        throw new IllegalArgumentException("Matrix: file not found:"
                + filename, e);
    }
}
protected final void loadURLMatrix(final URL urlAddress) {
    try {
        Scanner scanner = new Scanner(new InputStreamReader(
              urlAddress.openStream()));
        loadStream(scanner, urlAddress.toString());
    } catch (MalformedURLException e) {
        throw new IllegalArgumentException("Matrix: Wrong address:"
                + urlAddress, e);
    } catch (IOException e) {
        System.err.println("Cannot connect to " + urlAddress);
        System.exit(1);
    }
}

A fájl, melyben a mátrix adatai találhatóak tartalmazhatnak megjegyzés-sorokat. Ezt a sor elején szereplő százalékjel jelzi. Az első nem ilyen sornak a mátrix méretét kell tartalmaznia, és az azt követő soroknak a mátrix sorait. Természetesen ezeknek a hossza adott. Egy mátrixelemet egy betű jelöl, a -1-et a 2-es karakter jelöli:

/**
 * Mátrix feltöltése helyi vagy távoli állományból.
 * @param scanner a szöveg feldolgozó elemző.
 * @param filename mely fájlból, vagy URL-ről olvasunk?
 * @throws IllegalArgumentException
 */
protected void loadStream(Scanner scanner, final String filename)
        throws IllegalArgumentException {
    String actualLine;
    int size = -1;
    int lineNo = 0;
    final int charZero = 48;

    while (scanner.hasNextLine()) {
        actualLine = scanner.nextLine(); 
        if (actualLine.charAt(0) != '%') {
            if (size == -1) {
                size = Integer.parseInt(actualLine);
                if (1 < size && size <= MAXSIZE) {
                    setSize(size);
                }
                else {
                    throw new IllegalArgumentException("Matrix: in "
                            + filename + " the size is " + actualLine);
                }
            }
            else {
                if (actualLine.length() != size) {
                    throw new IllegalArgumentException("Matrix: in "
                            + filename + " the " + (lineNo + 1)
                            + ". line of data is wrong: " + actualLine);
                }
                else {
                    for (int i = 0; i < size; i++) {
                        byte number = (byte) (actualLine.charAt(i)
                                - charZero);
                        if (number != 0 && number != 1 && number != 2) {
                            throw new IllegalArgumentException(
                                    "Matrix: in "
                                    + filename + " at " + (lineNo + 1) + "/"
                                    + (i + 1) + " the character "
                                    + (actualLine.charAt(i)) + "is wrong!");
                        }
                        setXY(lineNo, i, number);
                    }
                    lineNo++;
                }
            }
        }
    }
}

A konstruktorok által közvetetten hívott függvény beállítja a mátrix tárolására használt adatszerkezetek méretét:

/** Mátrix méretének beállítása
 * @param size megadott méret
 */
protected abstract void setSize(final int size);

A fájlból dolgozó konstruktorok tesztelik a mátrix szimmetrikusságát. Itt csak végig kell menni a fél mátrixon, és tesztelni, hogy megegyezik-e a másik felével, vagy sem:

/** Tesztelje, hogy valóban szimmetrikus a mátrix!  */
private void isSymmetric() {
    for (int i = 0; i < getSize(); i++) {
        for (int j = i + 1; j < getSize(); j++) {
            if (getXY(i, j) != getXY(j, i)) {
                System.out.println(this.toString());
                throw new IllegalArgumentException(
                        "Matrix: the matrix isn't symmetric at "
                        + i + "," + j + ":" + getXY(i, j) + "/"
                        + getXY(j, i));
            }
        }
    }
}

Az egyik konstruktor közvetlenül hívja az alábbi metódust, mely szépen sorban elhelyezi az paraméteréül adott tömb adatait a mátrixban:

/**
 * Megadja a mátrixot konkrét adatokkal tesztelés céljából.
 * @param adat konstans tömb
 */
protected final void storeMatrix(final int[][] adat) {
    setSize(adat.length);
    for (int i = 0; i < getSize(); i++) {
        for (int j = 0; j < getSize(); j++) {
            setXY(i, j, (byte)adat[i][j]);
        }
    }
}

Az előbbi metódusok felhasználták a mátrix elemeit lekérdező, illetve megváltoztató metódusokat:

/** Olvassa ki a mátrix <code>i</code>,
  * <code>j</code> pozíciójában szereplő elemet!
  * @param i első index
  * @param j második index
  * @return kért adat
  */
 abstract int getXY(int i, int j);


/** Tárolja az <code>x</code> elemet a mátrix <code>i</code>,
  * <code>j</code> pozíciójában!
  * @param i első index
  * @param j második index
  * @param x tárolandó érték
  */
 abstract void setXY(int i, int j, byte x);

A klaszterezési feladat méretét a mátrix méretére, azaz alábbi metódusra vezetjük vissza:

/** Mátrix méretének lekérdezése.
 * @return adatmátrix mérete
 */
abstract int getSize();

A mátrix két csúcsa akkor tekinthető egymáshoz hasonlónak, ha ugyanazokhoz a csúcsokhoz ugyanolyan előjelű éllel kapcsolódnak. Ezért bevezetjük a két csúcs közti távolságot, melyet a mátrix sorainak hasonlósága alapján adunk meg:

/**
 * A mátrix két sorának távolsága.
 * @param i egyik sor azonosítója
 * @param j másik sor azonosítója
 * @return a két sor távolsága
 */
abstract protected int distance(int i, int j);
//TODO: mohó keresési módszer, mely a legközelebbi csúcsokat rendeli 
//egy közös csoportba

Annak érdekében hogy az előbbi metódust ne kelljen újra és újra meghívni kívülről, az alábbi metódus az összes csúcspár távolságából egy mátrixot állít elő:

/**
 * Minden sorpár távolsága.
 * @return négyzetes mátrix mely a csúcsok távolságából áll
 */
int [][] distances(){
    int[][] t = new int[getSize()][getSize()];
    for (int i = 0; i < getSize(); i++) {
        for (int j = i+1; j < getSize(); j++) {
            t[i][j] = distance(i, j);
            t[j][i] = t[i][j];
        }
        t[i][i]=0;
    }
    return t;
}

A tesztelés/debug során sokat segít a mátrix kiírása:

@Override
public String toString() {
    StringBuilder st = new StringBuilder();
    // Egyszerűen kiírjuk a mártixot
    for (int i = 0; i < getSize(); i++) {
        for (int j = 0; j < getSize(); j++) {
            st.append(getXY(i, j));
        }
        st.append("\n");
    }
    return st.toString();
}}

Egészek mátrixa

A legegyszerűbb megoldás kétdimenziós egészek tömbjét használni. Mivel 3 különböző érték valamelyikét kell tárolni egy egésznek, a legrövidebb egészet, a bájtot használjuk erre:

package hu.unideb.inf.optimization.clustering;
import java.net.URL;
/** A mátrixot egy kétdimenziós bájttömb ábrázolja.
 * @author BÓNIS Balázs, SZOKOL Péter
 */
public class MatrixByte extends Matrix {

A kétdimenziós tömb lesz az egyetlen adatszerkezet. Ebben, hogy ne kelljen az előjellel foglalkozni, a -1 értéket a 2 fogja jelölni:

private byte[][] data;

A négy különféle konstruktornál az ősosztályban megadott függvényekre és konstruktorokra építünk:

/**
 * Konstruktor mérettel.
 * @param size mátrix mérete
 */
MatrixByte(final int size) {
    super(size);
}
/**
 * Konstruktor fájlnévvel.
 * @param filename az adatokat tartalmazó fájl neve
 */
MatrixByte(final String filename) {
    super(filename);
}

/**
 * Konstruktor URL-lel.
 * @param address az adatokat tartalmazó URL
 */
MatrixByte(final URL address) {
    super(address);
}
/**
 * Konstruktor tömbbel (teszteléshez)
 * @param d a mátrix tartalma
 */
public MatrixByte(final int[][] d) {
    super(d);
}

A méreteket, valamint az egyes elemeket az tömböt használva tudjuk lekérdezni illetve beállítani:

@Override
protected final void setSize(int size) {
    data = new byte[size][size];
}
@Override
final int getSize() {
    return data.length;
}

@Override
final int getXY(int i, int j) {
    return data[i][j];
}

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

A mátrix két sorát ott tekintjük eltérőnek, ahol ugyanahhoz a csúcshoz különböző előjelű éllel kapcsolódnak. Ha az egyik kapcsolódik egy harmadik csúcshoz, de a második nem, arra mint információ hiányára tekintünk:

@Override
protected final int distance(int i, int j) {
    int d = 0;
    for (int k = 0; k < getSize(); k++) {
        if (2 == data[i][k] * data[j][k]) {
            d++;
        }
    }
    return d;
}

Hibának/konfliktusnak tekintjük, ha a két elem különböző csoportban szerepel, de + él köti össze őket, vagy azonos csoportban vannak és - éllel kapcsolódnak össze:

/**
 * Adott csoportok és adott elemek esetén úgy viselkednek, ahogy kellene?
 * @param groupI egyik csoport azonosítója
 * @param groupJ másik csoport azonosítója
 * @param i egyik azonosító
 * @param j másik azonosító
 * @return 0 ha helyes a viselkedés, 1 ha problémásak
 */
final int error(final int groupI, final int groupJ,
        final int i, final int j) {
    switch (getXY(i, j)) {
        case 1:
            if (groupI != groupJ) {return 1;}
            break;
        case 2:
            if (groupI == groupJ) {return 1;}
            break;
    }
    return 0;
}}

Bitek mátrixai

Ahogy a csoportosítás is megadható bitmátrixszal, úgy a mátrix is. Viszont mivel itt egy elem három értéket tartalmazhat, két bitre lesz szükség a tárolására. Ennek megfelelően használunk egy pozitív és egy negatív bitmátrixot is:

package hu.unideb.inf.optimization.clustering;
import java.net.URL;
/**
 * Az adatmátrixot bitmátrix is tárolhatja.
 * @author Aszalós László
 * @see BitMatrix
 */
public class MatrixBits extends Matrix {

A negatív bitmátrixot az n, míg a pozitívat a p tárolja:

private BitMatrix n, p;

A konstruktoraink megegyeznek a másik megvalósításnál ismertetett konstruktorokkal:

/*
 * Konstruktor mérettel
 * @param size mátrix mérete
 */
MatrixBits(int size) {
    super(size);
}
/*
 * Konstruktor fájlnévvel.
 * @param filename mátrix adatait tartalmazó fájl neve
 */
MatrixBits(String filename) {
    super(filename);
}
/*
 * Konstruktor URL-lel.
 * @param address mátrix adatait tartalmazó URL
 */
MatrixBits(URL address) {
    super(address);
}
/*
 * Konstruktor tömbbel (teszteléshez).
 * @param data mátrix adatai
 */
MatrixBits(int[][] data) {
    super(data);
}

A mátrix méretének megadásánál, lekérdezésénél a BitMatrix típusra hivatkozunk:

@Override
final int getSize() {
    return n.getSize();
}

@Override
final protected void setSize(int size) {
    n = new BitMatrix(size);
    p = new BitMatrix(size);
}

Ha a mátrix egy elemét be kívánjuk állítani, akkor mindkét bitmátrixban változtatnunk kell:

@Override
final void setXY(int i, int j, byte x) {
    if (1 == x) {
        p.setXY(i, j); 
        n.unSetXY(i, j);
    }
    if (2 == x) {
        n.setXY(i, j);
        p.unSetXY(i, j);
    }
    if (0 == x) {
        p.unSetXY(i, j);
        n.unSetXY(i, j);
    }
}

Lekérdezéskor is figyelembe kell venni mindkét bitmátrixot. Ha az adott bit mindkét mátrixban be van állítva, az hibát jelent!

@Override
final int getXY(int i, int j) {
    switch (p.getXY(i, j) + 2 * n.getXY(i, j)) {
        case 3:
            throw new IllegalArgumentException("double value at " + i
                    + "," + j + ".");
        case 2:
            return 2;
        case 1:
            return 1;
        default:
            return 0;
    }
}

Ami miatt érdemes volt bevezetni a bitmátrixos ábrázolást, az a következő metódus. Természetesen ez is átadja a munka részét egy másik osztálynak:

/** Hány elemmel áll konfliktusban az <code>i</code>-dik elem,
 * melynek csoportját <code>bv</code> írja le?
 * @param i elem sorszáma
 * @param bv csoportszerkezete <code>i</code> csoportjának.
 * @return konfliktusok száma
 */
final int errors(final int i, final BitVector bv) {
    return bv.bitAnd(n.getVector(i)) + bv.bitNotAnd(p.getVector(i));
}

Ha két csúcs távolságát keressük, azt is más osztályok segítségével számíthatjuk ki:

@Override
protected final int distance(int i, int j) {
    return n.getVector(i).bitAnd(p.getVector(j))
            + n.getVector(j).bitAnd(p.getVector(i));
}

A tesztelést megkönnyítendő ezeket a bitmátrixokat is átalakítjuk kiírható formára:

@Override
public final String toString() {
    StringBuilder st = new StringBuilder();
    st.append(n.toString());
    st.append("\n");
    st.append(p.toString());
    return st.toString();
}
}

Feladatok

  1. A mátrixokra értelmeztük a sorainak a távolságát. Erre építve implementáljon egy mohó keresési algoritmust, mely az egymáshoz legközelebbi sorok csúcsait kapcsolja egy csoportba.

    Majd vizsgálja meg, hogy egy csúcs átmozgatása egy másik csoportba javít-e a célfüggvény értékén. Ha igen, akkor ezeket az átmozgatásokat hajtsa mind végre. Hasonlítsa össze ennek a módszernek az eredményességét a többi módszerével.

  2. Adjon meg módszereket, mellyel ritka mátrixot hatékonyan lehet tárolni és feldolgozni!