Adjazezmatrix

[SaureKirsche]

Hallo liebe Forummitglieder,

ich habe ein kleines Problem, ich will einen Graphen in einer Adjazenzmatrix abspeichern.
Leider läuft es nicht so gut.

Ich lese von der txt.-Datei eine Zeile im Format v1:v2:Gewicht, also z.b. 2:3:5 ein. D.h. zwischen knoten 2 und 3 ist die Kante mit 5 gewichtet. So jetzt will ich das in meine Adjazenzmatrix abspeichern. Und mache AdMatrix [v1][v2]= Gewicht.

kriege aber eine Exception in thread "main" java.lang.NumberFormatException: For input string: "".

Was bedeutet das, wie kann ich meinen fehler beheben, oder wie speichert man allgemei graphen in eine Adjazenzmatrix ab???????

Vielen Dank für eure Hilfe

 

[Civilazi]

Allgemein ist die Idee für deine Entfernungsmatrix ja schonmal richtig, wobei ich das nicht Adjazenzmatrix nennen würde, aber das ist eine Def.-Sache.
Zeig doch mal exakt deinen Code, wenn da bei dir v1 und v2 Strings sind, kann das ja nicht klappen. Es sieht aber so aus, als würdest einen leeren String ("") in eine Zahl überführen wollen.
Also: Code zeigen

 

[Marco13]

Lass' dir mal vor JEDEM parseInt/parseDouble, das du machst, den String, den du parsen willst mit
System.out.println("Ich parse jetzt '"+denString+"'");
ausgeben. Wie zerlegst du denn die Eingabe in die Teilstrings, die du dann parsen willst?

 

[SaureKirsche]

Also nach längerem Testen habe ich es jetzt gelöst,
@ Civilazi, Du hattest Recht das Problem lag an einem leeren Strin
hier ist jetzt mein neuer Code:

import java.io.*;
import java.util.*;
import java.lang.*;

public class Graph {
	
	public static void main (String [] args){
		Graph test = new Graph();
		test.getGraph("input.txt");
	}

	public int n;  // Knotenanzahl
	public int m;  // Kantenanzahl
	static public int start, ziel;  // Startknoten, Zielknoten
	public int [][] matrix;			// Adjazenzmatrix
	
	public Graph (){}
	
	/* EINLESEN 
	Die Textdatei input.txt wird eingelesen und die Daten in eine Adjazenzmatrix gespeichert, 
	die Matrix soll dann später an die Methode getGraph übergeben werden. */
	
	public  int [][] getGraph (String datei){
		
		
		try {
		 	
	    	
			File input = new File(datei);
			FileReader in = new FileReader(input);
	        BufferedReader reader = new BufferedReader(in);
	        n = Integer.parseInt(reader.readLine()); // erste Zeile einlesen
	        m = Integer.parseInt(reader.readLine()); // zweite Zeile einlesen
	        start = Integer.parseInt(reader.readLine()); // Startknoten einlesen
	        ziel = Integer.parseInt(reader.readLine()); // Zielknoten einlesen
	       
	        matrix = new int [n][n]; // Bilde Adjazenzmatrix mit n Zeilen und n Spalten
	        	
	        	
	        	for (int k=0; k<n; k++){
	        		for (int l=0; l<n;l++){
	        				matrix[k][l]=0;
	        		 }
	        	} // Setze in dieser vorerst alle Einträge gleich Null
	        	
	        	 while(reader.ready()){ // Jetzt kommen Zeilen der Form v1:v2:Gewicht
	        		 
	        		 String s = reader.readLine();
	        		 String [] kante = s.split(":"); // Trenne zwischen ":" Doppelpunkt
	        		 
	        		 if (kante.length!=3) continue; // z.B. leere Zeilen sollen nicht eingelesen werden
	        		 
	        		 int v1= Integer.parseInt(kante[0]); //hier wird v1(s.oben) in ein Integer umgewandelt
	        		 int v2 = Integer.parseInt(kante[1]); // ."..v2..."...
	        		 int gewicht = Integer.parseInt(kante[2]); // Und das Gewicht wird ebenfalls in ein Integer umgewandelt
	        		 
	        		 /* Da nun bekannt ist , welche Knoten miteinander verbunden sind und wie die Kante dazwischen
	        		  * gewichtet ist, können wir die Adjazenzmatrix bilden:
	        		  */
	        		 //System.out.println(k1+""+k2+""+gewicht);
	        		 matrix [v1-1][v2-1] = gewicht; 
	        		 matrix [v2-1][v1-1] = gewicht;
	        		 
	        		 
	        		 //System.out.println(matrix[v2-1][v1-1]);
	    	        		
	        	
	        }
	        	
	        	for (int j =0; j<n;j++){
	        		System.out.println();
	        		for (int i =0; i<n; i++){
	        			
	        			System.out.print( matrix [j][i]);
	        		}
	        	}
	        reader.close();
	       
	        
	 }  
	 
	 catch (IOException e){ System.out.println ("Fehler beim Einlesen der Datei oder Datei nicht gefunden");}
	 
	 catch (NullPointerException e){ System.out.println(" NullPointerException in Einlesen ohne Struktur");}
		
		return matrix;
	}
	
}

 

[SaureKirsche]

Jetzt habe ich eine andere Frage:

das alles mache ich um am Ende einen Dijkstra Algorithmus programmieren zu können.

Ich will nun eine Doppelt verkettete Liste für die Front U,


Wir konnen daher die Menge U in C +1 doppelt verketteten Listen Eimer (0); : : : ; Eimer
(C) verwalten, wobei die Liste Eimer(k) alle Knoten v aus U enthalt, fur die gilt k =
dist(v) mod (C + 1): Zusatzlich benutzen wir wieder einen Zeiger assign(v); der von v
auf dasjenige Listenelement der Liste der Eimer zeigt, das v enthalt.
Eimer(0); : : : ;Eimer(i); : : : ;Eimer(C) mit
Dist(v) mod(C + 1) = i , v 2 Eimer (i)
- fuge ein: Fuge v in den Eimer Dist(v)mod(C + 1) ein.
- Finde Min: Sei i0 die Nummer des Eimers, der das letzte Minimum enthielt
i = 0
While Eimer ((i0 + i)mod(C + 1)) = ; und i  C do i = i + 1:
If i = C + 1
then Stop (Front ist leer)
else
das Minimum bendet sich im Eimer (i0 + i)mod(C + 1):
endif
- losche Min: Entferne das Minimum aus seinem Eimer.
- Verringere: Entferne v aus dem Eimer OldDist(v)mod(C + 1) und fuge v in den
Eimer NewDist(v)mod(C + 1) ein.

Jetzt verstehe ich aber nicht, soll jeder Eimer eine dopplt verkettete Liste sein und U die Menge der dp. verket. Listen und wenn ja, wie soll ich das realisieren???

Ich habe mir schon angeckukt, dass dopp. verkt. Listen in Java als LinkedList realisiert werden. Aber ich habe immer noch keine Ahnung wie ich das einsetzen soll?????????