package jpp.simplegraph;
/**
* Diese Klasse implementiert das Interface ISimpleGraph.
*
* @author Laura
*
*/
public class SimpleGraph implements ISimpleGraph {
private double[][] matrix;
private int knotenanzahl;
private int kantenanzahl;
/**
* Konstruktor erzeugt einen Graphen mit n Knoten ohne Pfeile, wenn n
* negativ ist, so wird ein leerer Graph erzeugt.
*
* @param n
* Knotenanzahl
*/
public SimpleGraph(int n) {
if (n <= 0) {
this.matrix = null;
this.kantenanzahl = 0;
this.knotenanzahl = 0;
} else {
this.kantenanzahl = 0;
this.knotenanzahl = n;
this.matrix = new double[n - 1][n - 1];
for (int i = 0; i <= n - 1; i++) {
for (int j = 0; j <= n - 1; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else
this.matrix[i][j] = -1;
}
}
}
}
/**
* Erzeugt einen Graphen anhand der Adjazenzmatrix matrix (Kopie);
* entspricht die Adjazenzmatrix nicht den oben genannten Eigenschaften, so
* wird ein leerer Graph erzeugt.
*
* @param matrix
* Matrix
*/
public SimpleGraph(double[][] matrix) {
this.kantenanzahl = -1;
if (matrix == null) {
throw new NullPointerException("Matrix darf nicht null sein");
}
for (int i = 0; i < matrix.length; i++) {
if (matrix.length != matrix[i].length) {
this.matrix = null;
this.kantenanzahl = 0;
this.knotenanzahl = 0;
}
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][i] != 0) {
this.matrix = null;
this.kantenanzahl = 0;
this.knotenanzahl = 0;
}
for (int j = 0; j < matrix.length; j++) {
if (i != j) {
if (matrix[i][j] <= 0 && matrix[i][j] != -1) {
this.matrix = null;
this.kantenanzahl = 0;
this.knotenanzahl = 0;
}
}
}
}
if (this.kantenanzahl == -1) {
this.kantenanzahl = 0;
this.matrix = new double[matrix.length][matrix.length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
this.matrix[i][j] = matrix[i][j];
if (matrix[i][j] > 0) {
this.kantenanzahl++;
}
}
}
this.knotenanzahl = matrix.length;
}
}
/**
* Fuegt einen neuen Pfeil ein, existierende Pfeile werden ueberschrieben.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @param cost
* Kosten
* @return true wenn erfolgreich
*/
public boolean addEdge(int source, int target, double cost) {
if (source < 0 || target < 0 || source >= this.knotenanzahl
|| target >= this.kantenanzahl)
return false;
if (cost <= 0)
return false;
this.matrix[source][target] = cost;
return true;
}
/**
* Prueft ob ein Pfeil im Graphen existiert.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @return Wahrheitswert
*/
public boolean containsEdge(int source, int target) {
if (source < 0 || target < 0 || source >= this.knotenanzahl
|| target >= this.kantenanzahl)
return false;
if (this.matrix[source][target] <= 0)
return false;
else
return true;
}
/**
* Prueft ob ein Knoten im Graphen vorhanden.
*
* @param node
* Knoten
* @return Wahrheitswert
*/
public boolean containsNode(int node) {
if (node < 0 || node >= this.knotenanzahl)
return false;
return true;
}
/**
* Gibt die Kosten eines Pfeils zurueck.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @return Kosten (-1.0 wenn kein Pfeil existiert)
*/
public double getEdgeCost(int source, int target) {
if (source < 0 || target < 0 || source >= this.knotenanzahl
|| target >= this.knotenanzahl)
return -1;
return this.matrix[source][target];
}
/**
* Gibt die Anzahl der Pfeile des Graphen zurueck.
*
* @return Pfeilanzahl
*/
public int getEdgeCount() {
return this.kantenanzahl;
}
/**
* Gibt die Adjazenzmatrix (Kopie) des Graphen zurueck.
*
* @return Adajazenzmatrix
*/
public double[][] getMatrix() {
return matrix;
}
/**
* Gibt die Anzahl der Knoten des Graphen zurueck.
*
* @return Knotenanzahl
*/
public int getNodeCount() {
return this.knotenanzahl;
}
/**
* Gibt die Vorgaengerknoten eines Knoten in aufsteigender Reihenfolge
* zurueck; Existiert der Knoten nicht im Graphen, so wird ein leeres Array
* zurueck gegeben.
*
* @param node
* Knoten
* @return Array mit Vorgaengerknoten
*/
public int[] getPredecessors(int node) {
if (node < 0 || node >= this.knotenanzahl)
return null;
int[] vorgaengerknoten = null;
int j = 0;
for (int i = 0; i < this.knotenanzahl; i++) {
if (this.matrix[i][node] > 0) {
vorgaengerknoten[j] = i + 1;
j++;
}
}
return vorgaengerknoten;
}
/**
* Gibt die Nachfolgerknoten eines Knoten in aufsteigender Reihenfolge
* zurueck.
*
* Existiert der Knoten nicht im Graphen, so wird ein leeres Array zurueck
* gegeben.
*
* @param node
* Knoten
* @return Array mit Nachfolgerknoten
*/
public int[] getSuccessors(int node) {
if (node < 0 || node >= this.knotenanzahl)
return null;
int[] nachfolgerknoten = null;
int j = 0;
for (int i = 0; i < this.knotenanzahl; i++) {
if (this.matrix[node][i] > 0) {
nachfolgerknoten[j] = i + 1;
j++;
}
}
return nachfolgerknoten;
}
/**
* Loescht einen Pfeil.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @return true wenn erfolgreich
*/
public boolean removeEdge(int source, int target) {
if (source < 0 || target < 0 || source >= this.knotenanzahl
|| target >= this.kantenanzahl)
return false;
if (matrix[source][target] <= 0)
return false;
else
this.matrix[source][target] = -1;
return true;
}
/**
* Setzt den Graphen anhand der Adjazenzmatrix (Kopie).
*
* Entspricht die Adjazenzmatrix nicht den oben genannten Eigenschaften, so
* wird ein leerer Graph erzeugt.
*
* @param matrix
* Adjazenzmatrix
*/
public void setMatrix(double[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
}
}
