ich kriege es nicht hin und weiß nicht wo mein Fehler ist also mein Interface ist
es dient zu Graphen
und dazu habe ich die Breitensuche
der Fehler taucht bei dem Test wenn es 4 edge geaddet (hinzugefügt) werden nehmt man getEdgeCount und es soll 3 sein aber es zeigt 15
z.b
wo kann es daran liegen
Java:
package jpp.simplegraph;
import java.util.ArrayList;
/**
* Repraesentiert ein einfacher Graph.
*
* @
*
* @author Mohamed Baa
* @version 10.03.2010
*/
public class SimpleGraph implements ISimpleGraph {
/**
* Anzahl Knoten.
*/
private int nodeCount;
/**
* Anzahl Kanten.
*/
private int edgeCount;
/**
* zahl minuseins.
*/
private final int minuseins = -1;
/**
* leere Adjazenzmatrix.
*/
private double[][] matrix;
/**
* erzeugt ein Graph mit n Knoten.
*
*/
public SimpleGraph(int n) {
// ISimpleGraph graph = new ISimpleGraph;
if (n <= 0) {
this.matrix = new double[0][0];
this.nodeCount = 0;
this.edgeCount = 0;
} else {
this.edgeCount = 0;
this.nodeCount = n;
this.matrix = new double[n][n];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; 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.setMatrix(matrix);
}
/**
* Gibt die Adjazenzmatrix (Kopie) des Graphen zurueck.
*
* @return Adajazenzmatrix
*/
public double[][] getMatrix() {
double[][] copyMatrix = new double[matrix.length][matrix.length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
copyMatrix[i][j] = matrix[i][j];
if (matrix[i][j] > 0) {
this.edgeCount++;
}
}
}
return copyMatrix;
}
/**
* 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) {
this.nodeCount = -1;
this.edgeCount = -1;
if (matrix == null) {
this.matrix = new double[0][0];
this.nodeCount = 0;
this.edgeCount = 0;
return;
}
boolean failed = false;
for (int i = 0; i < matrix.length; i++) {
if (matrix.length != matrix[i].length) {
failed = true;
System.out.println("graph init failed: not quadratic");
}
if (!failed && matrix[i][i] != 0) {
System.out.println("graph init failed: diagonal not zero");
failed = true;
}
}
if (!failed) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (i != j && (matrix[i][j] <= 0 && matrix[i][j] != -1)) {
System.out
.println("graph init failed: negative values");
failed = true;
}
}
}
}
// prüfung auf korrektheit fertig
// matrix setzen
if (failed) {
this.matrix = new double[0][0];
this.nodeCount = 0;
this.edgeCount = 0;
} else {
this.edgeCount = 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.edgeCount++;
}
}
}
this.nodeCount = matrix.length;
}
// System.out.println("set matrix: \n" + this.toString());
}
/**
* Gibt die Anzahl der Knoten des Graphen zurueck.
*
* @return Knotenanzahl
*/
public int getNodeCount() {
return this.nodeCount;
}
/**
* Gibt die Anzahl der Pfeile des Graphen zurueck.
*
* @return Pfeilanzahl
*/
public int getEdgeCount() {
return this.edgeCount;
}
/**
* 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 Vorgaegerknoten
*/
public int[] getPredecessors(int node) {
if (node >= this.nodeCount || node < 0) {
return new int[0];
}
ArrayList<Integer> predecessors = new ArrayList<Integer>();
for (int i = 0; i < nodeCount; i++) {
for (int j = 0; j < nodeCount; j++) {
if (j == node) {
if (this.matrix[i][j] > 0) {
predecessors.add(Integer.valueOf(i));
}
}
}
}
int[] s = new int[predecessors.size()];
for (int i = 0; i < predecessors.size(); i++) {
s[i] = predecessors.get(i).intValue();
}
// System.out.println("get predecessor of " + node + " : " +
// predecessors);
return s;
}
/**
* 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 >= this.nodeCount || node < 0) {
return new int[0];
}
double[] a = this.getMatrix()[node];
ArrayList<Integer> successors = new ArrayList<Integer>();
for (int i = 0; i < nodeCount; i++) {
if (a[i] > 0) {
successors.add(Integer.valueOf(i));
}
}
int[] s = new int[successors.size()];
for (int i = 0; i < successors.size(); i++) {
s[i] = successors.get(i).intValue();
}
// System.out.println("get successor of " + node + " : " + successors);
return s;
}
/**
* 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.nodeCount
|| target >= this.nodeCount)
return false;
if (cost <= 0 || target == source)
return false;
if (matrix[source][target] <= 0) {
this.matrix[source][target] = cost;
edgeCount++;
System.out.println("add edge of " + source + " : " + target +" : " + cost +" : " + getNodeCount() + " : "+ getEdgeCount() + ":" + addEdge(source,target,cost));
return true;
} else {
this.matrix[source][target] = cost;
System.out.println("add edge of " + source + " : " + target +" : " + cost +" : " + getNodeCount() + " : "+ getEdgeCount());
return true;
}
}
/*
* public boolean addEdge(int source, int target, double cost) { if (target
* >= this.nodeCount || source >= this.nodeCount || source < 0 || target < 0
* || cost <= 0) { return false; } if (source == target && cost != 0) {
* return false; } if (matrix[source][target] > 0) { matrix[source][target]
* = cost;
*
* } else { matrix[source][target] = cost; edgeCount++; }
* System.out.println("get successor of " + source + " : " + target + " : "
* + getEdgeCount()); return true; }
*/
/**
* Loescht einen Pfeil.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @return true wenn erfolgreich
*/
public boolean removeEdge(int source, int target) {
if (target >= this.nodeCount || source >= this.nodeCount || source < 0
|| target < 0) {
return false;
}
if (matrix[source][target] == minuseins) {
return false;
}
if (source == target) {
return false;
}
if (matrix[source][target] > 0) {
edgeCount--;
}
return true;
}
/**
* Prueft ob ein Knoten im Graphen vorhanden.
*
* @param node
* Knoten
* @return Wahrheitswert
*/
public boolean containsNode(int node) {
if (node >= this.matrix.length || node < 0) {
return false;
} else {
return true;
}
}
/**
* Prueft ob ein Pfeil im Graphen.
*
* @param source
* Startknoten
* @param target
* Zielknoten
* @return Wahrheitswert
*/
public boolean containsEdge(int source, int target) {
if (target >= this.nodeCount || source >= this.nodeCount || source < 0
|| target < 0 || matrix[source][target] <= 0) {
return false;
} else {
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 (target >= this.nodeCount || source >= this.nodeCount || source < 0
|| target < 0) {
return -1;
} else {
return matrix[source][target];
}
}
public String toString() {
String s = "";
if (this.matrix == null || this.matrix.length == 0) {
return "empty graph";
}
for (int i = 0; i < this.matrix.length; i++) {
for (int j = 0; j < this.matrix.length; j++) {
s += this.matrix[i][j] + " ";
}
s += "\n";
}
return s;
}
}
es dient zu Graphen
und dazu habe ich die Breitensuche
Java:
public class BFS {
/**
* Diese Methode soll mittels Breitensuche pruefen, ob ein Weg vom
* Startknoten source zum Zielknoten target existiert.
*
* @param graph
* Simple Graph
* @param source
* Start Node
* @param target
* End Node
* @return
*/
public static boolean search(ISimpleGraph graph, int source, int target) {
if (graph == null) {
//System.out.println("bfs search graph null");
return false;
}
// System.out.println("graph: \n" + graph + "\n source: " + source +
// " target: " + target);
if (target < 0 || source < 0 || source >= graph.getNodeCount()
|| target >= graph.getNodeCount()) {
// System.out.println("bfs search failed node count:" +
// graph.getNodeCount() + " source: " + source + " target: " +
// target);
return false;
}
if (source == target) {
return true;
}
LinkedList<Integer> queue = new LinkedList<Integer>();
LinkedList<Integer> visited = new LinkedList<Integer>();
queue.add(Integer.valueOf(source));
visited.add(Integer.valueOf(source));
while (!queue.isEmpty()) {
// System.out.println("search queue: " + queue);
int c = queue.remove().intValue();
if (c == target) {
return true;
}
if (graph.getSuccessors(c) != null) {
for (int i = 0; i < graph.getSuccessors(c).length; i++) {
int x = graph.getSuccessors(c)[i];
if (!visited.contains(x)) {
queue.add(Integer.valueOf(x));
visited.add(Integer.valueOf(x));
}
}
}
}
//System.out.println("bfs no path found");
return false;
}
der Fehler taucht bei dem Test wenn es 4 edge geaddet (hinzugefügt) werden nehmt man getEdgeCount und es soll 3 sein aber es zeigt 15
z.b
Java:
System.out.println(y.addEdge(1 , 2 , 2.0));
System.out.println(y.addEdge(1 , 3 , 3.0));
System.out.println(y.addEdge(3 , 2 , 4.0));
System.out.println(y.addEdge(1 , 3 , 4.0));
wo kann es daran liegen
Zuletzt bearbeitet von einem Moderator: