gerichteter Graph aus einer Datei einlesen

N

nino2015

Mitglied
Hallo Profis,
ich bin sehr neu in Java. So bitte etwas geduld mit mir...
Ich habe folgendes PB: ich möchte einen gerichteten Graph aus einer Datei einlesen und der Graph danach ungerichtet machen. Die Datei hat folgendes Format:
// The file format is as follows:
// First line: number of nodes = n.
// Second line: number of arcs = m.
// Then n lines, one for each node, containing the coordinates of node id,
// id = 0,..., n-1. The format of each such line is
// "<id> <latitude> <longitude>".
// Then m lines, one for each arc. The format for each line is
// "<tail node id> <head node id> <distance in meters> <max speed (in km/h)>".
//
// Here is an example of a *directed* graph:
// 3
// 2
// 0 49.009 7.815
// 1 48.997 7.812
// 2 49.017 7.799
// 0 1 17 30
// 1 2 5 120
Ich habe folgender Code gestartet:
Code: 
  public void readFromFile(String fileName) {
    try{
        FileReader reader = new FileReader(filename);
        BufferedReader bufferedReader = new BufferedReader(reader);
       
        // Erste linie ist die Anzahl der Knoten
        numNode = Integer.parseInt(bufferedReader.readLine().trim());
        // Zweite linie ist die Anzahl der Kanten
        numArcs = Integer.parseInt(bufferedReader.readLine().trim());
        // ....
  }
    catch(Exception e) {
       e.printStackTrace();
    }
danke im Voraus.
 
Ehe du Daten lesen kannst, brauchst Du Datenstrukturen, die Du mit Werten füllen kannst.
Wie willst Du die Daten denn speichern?
Bezüglich Datentypen und Werten ist evtl. auch wichtig, dass dies genauer spezifiziert wird. (Ich habe im Augenblick das Gefühl, dass es auf triviale Arrays hinauslaufen wird und kein wirkliches Java-Programm gewünscht wird (sprich: keine Objektorientierung und so).

Du könntest also jetzt Klassen vorhalten für Nodes. Diese haben halt eine id, und die location. Und eine Menge von Verbindungen.
Die Klasse Node könnte eine Funktion Parse haben. Da Du eine Zuordnung von id -> Node brauchst, könntest Du die in einer Hashmap speichern.
Code: 
HashMap<Integer, Node> nodes = new HashMap<>();
for (int nodeCounter=0; nodeCounter < numNode; nodeCounter++) {
  Node node = Node.parse(bufferedReader.readLine());
  nodes.put(node.getId(), node);
}
for (int arcCounter=0; arcCounter < numArcs; arcCounter++) {
  Arc arc = Arc.parse(bufferedReader.readLine());
  nodes.get(arc.getTailNodeId()).addArc(arc);
}

So könnte es dann aussehen, wenn Du die entsprechenden Klassen für Node und Arc hättest. Die parse Funktionen würde ich so schreiben, dass die selbst den trim() machen. (Integer.parseInt kann keine Leerzeichen verkraften, aber das sollte unsere Routine können.)
 
Danke für deine schnelle Antwort. Du hast recht hier wird ein array angesprochen.
Es wurde vorgeschlagen:
Code: 
  // The adjacency list of each node.
  Array<Array<Arc>> adjacencyLists;

  // Information about each node.
  Array<Node> nodes
ich hatte die Klasse Node und Klasse Arc schon angefangen:
Java: 
/**
* Class for nodes
*/
class Node {
  public int nodeId;
  public float latitude;
  public float longitude;
  public Node(int id, float la, float lo) { // Constructor of each node
    nodeId = id;
    latitude = la;
    longitude = lo;
  }
}

/**
 * Klasse für Kanten aus Zielknoten "headNodeId", Gewicht "cost" und
 * Geschwingkeit "maxSpeed".
 * Der Startknoten der Kante ist implizit durch die Zugehoerigkeit
 * zu einer Adjazenzliste bestimmt.
 */
class Arc {
  public int headNodeId;
  public int cost; // Wegen test mit Saarland.graph. Sonst irrelevant.
  public int maxSpeed; // Wegen test mit Saarland.graph. Sonst irrelevant.
 
  /** Konstruktor für jede Kante.*/
  public Arc(int headNodeId, int cost, int maxSpeed) {
  this.headNodeId = headNodeId;
  this.cost = cost;
  this.maxSpeed = maxSpeed;
  }
}
 
Das ist doch schon ein guter Anfang.

Ein erster Punkt wäre noch eine Validierung der Daten. Sind die Daten, die gegeben sind, wirklich alle enthalten?
Das sehe ich im Augenblick nicht. So hat Arc ja zwei Node Ids. Davon sehe ich im Augenblick nur eine.

Die Daten könntest Du auch anders vorhalten. Statt der Node IDs kannst Du ja die Referenzen zu den Nodes hinterlegen.
Und die Nodes sollten evtl. wissen, was für Arcs sie betreffen, oder?

Als nächstes könntest Du den Klassen jeweils die Funktionen
Code: 
public static Node parseNode(String line)
public static Arc parseArc(String line)
implementieren. (Also parseNode in Node und parseArc in Arc.)

Das parseArc braucht evtl. (je nach Veränderung) noch mehr Informationen. Wenn Du Referenzen zu Nodes speichern willst, dann braucht es evtl. eine Map von NodeIds zu Nodes so dass Du die Nodes speichern kannst.

In den Funktionen müsstest Du dann halt den String verarbeiten und ein neues Objekt erstellen und zurück geben.

Konrad
 
kneitzel hat gesagt.:
in erster Punkt wäre noch eine Validierung der Daten. Sind die Daten, die gegeben sind, wirklich alle enthalten?
Das sehe ich im Augenblick nicht. So hat Arc ja zwei Node Ids. Davon sehe ich im Augenblick nur eine.
Zum Vergrößern anklicken....
Der Startknoten der Kante ist implizit durch die Zugehoerigkeit zu einer Adjazenzliste bestimmt. Aber ich weiss momemtan nicht wie ich das machen soll.🙁
kneitzel hat gesagt.:
Die Daten könntest Du auch anders vorhalten. Statt der Node IDs kannst Du ja die Referenzen zu den Nodes hinterlegen.
Und die Nodes sollten evtl. wissen, was für Arcs sie betreffen, oder?
Zum Vergrößern anklicken....

wie? hast du vielleicht einen Bsp?

kneitzel hat gesagt.:
Das parseArc braucht evtl. (je nach Veränderung) noch mehr Informationen. Wenn Du Referenzen zu Nodes speichern willst, dann braucht es evtl. eine Map von NodeIds zu Nodes so dass Du die Nodes speichern kannst.

In den Funktionen müsstest Du dann halt den String verarbeiten und ein neues Objekt erstellen und zurück geben
Zum Vergrößern anklicken....
Sollte ich die Lines spliten "\t" und in Array speichern? bitte um beispiele ich bin super schecht in der Programmierung.
Gruss Nino
 
Zuletzt bearbeitet:
Also Du brauchst in Arc keinen Startknoten, wenn der anderweitig vorgegeben ist. Dieses verschachtelte ArrayList verstehe ich im Augenblick nicht so ganz. Wenn da angedacht ist, dass halt adjacencyLists[0] zu nodes[0] gehört, dann ist zwar toll, dass verstanden wurde, dass eine Liste von Arcs zu einem Node gehört, aber die objektorientierte Umsetzung wurde offensichtlich nicht verstanden, denn zusammengehörende Daten würden ja immer gekapselt.

Also erst einmal einige ganz allgemeine Dinge:
- Wenn ich eine Verbindung zwischen Zwei Objekten habe, dann kann ich durchaus einfach die id speichern. Also von einem Mitarbeiter die Personalnummer oder so. Das kann sehr gut sein, wenn ich die Daten nicht im Speicher halten will um sie dann bei Bedarf erst z.B. aus einer Datenbank zu laden. Aber wenn ich die Objekte im Speicher habe, dann kann ich einfach eine Referenz speichern.
Code: 
public class Employee {
   private Department depatment; // Keine ID der Abteilung sondern eine Referenz auf die Abteilung.
   // ...
}
Sowas kann man in Arc auch machen und dann kann man direkt auf die Nodes (oder zumindest den Zielnode) zugreifen.
- Einsparen von Referenzen - Wenn Arc in einem Node ist, dann hat man da den StartNode. Aber es schadet generell nicht, die Daten auf beiden Seiten bereit zustellen. Arc kann auch durchaus eine Referenz auf den StartNode besitzen. Das kann ggf. manche Dinge vereinfachen. Ich hätte die Arc Klasse mit Start und Ziel Node versehen.
- Parsen von Text: Ja, String.split ist ein erster Anfang. Aber diesbezüglich musst Du halt recherchieren, was wie alles geht. Auch wie Du aus dem Text dann die eigentlichen Werte bekommst.
(Die Klassen der Datentypen haben dazu meist eine parse Funktion.)

Konrad
 
Was soll die Methode Parsen return? Ich stehe auf dem Schlau. siehe code:
Code: 
public class Node {
  public int nodeId;
  public float latitude;
  public float longitude;
 
  //Constructor of each node
  private Node(int id, float la, float lo) {
    this.nodeId = id;
    this.latitude = la;
    this.longitude = lo;
  }
  public static Node parseNode(String line) {
    String[] fields = line.split("\t");
    int id = Integer.parseInt(fields[0]);
    float la = Float.parseFloat(fields[1]);
    float lo = Float.parseFloat(fields[2]);
    return ???;
  }

Gruss Nino
 
neuer Knoten oder this wäre gut, je nach dem, ob Fabrik oder Konstruktor

Array<Array<Arc>> adjacencyLists;

sieht für mich eher nach einer Adjazenzmatrix aus

lies dir schnell mal durch, wie man aus einem DG einen UDG macht.
 
E= {u,v} für UDG und E =(u,v) für DG. Aber wie ich das umsetzen sollte weis ich momentan nicht. Ich will die eingelesen Knoten erstmal in einer ArrayListe<Arc> speichern und danach die adjazenzliste als ArrayList<ArrayListe<Arc>> an die Liste aller Knoten(ArrayListe<Arc>) anbinden. Ist der Einsatz richtig??? Wenn ja fehlt mir aber an Java Knowhow?
 
Die Variablen sollten immer einen sinnvollen, sprechenden Namen haben. Also "la" und "lo" würde ich zu vernünftigen Variablennamen umbenennen.
 
Erledigt la= latitude , lo=longitude.
Hier ist der Code für Arc:
Code: 
public class Arc {
  public int headNodeId;
  public int cost; // Wegen test mit Saarland.graph. Sonst irrelevant.
  public int maxSpeed; // Wegen test mit Saarland.graph. Sonst irrelevant.
  public int tailNodeId;
  
  /** Konstruktor für jede Kante.
   */
  public Arc(int headNodeId, int cost, int maxSpeed) {
    this.headNodeId = headNodeId;
    this.cost = cost;
    this.maxSpeed = maxSpeed;
  }
  public static Arc parseArc(String line) {
    String[] fields = line.split("\t");
    int  headNodeId = Integer.parseInt(fields[1]);
    int cost = Integer.parseInt(fields[2]);
    int maxSpeed = Integer.parseInt(fields[3]);
    return new Arc(headNodeId,cost,maxSpeed);
  }
  public Object getTailNodeId() {
    return tailNodeId;
  }
Der tailNodeId sollte eigentlich aus der Liste aller Knoten(ArrayListe<Arc>) entnommen werden. Wie ordne ich das zu.
 
So sieht momentan die Methode readFromFile aus:
Java: 
 public void readFromFile(String fileName) {
   
    // Liest die Datei linie für linie und speichert die info in einer Map.
    // die Map gibt zu einer Knoten-Id den Index an, an dem der Knoten
    // und die inzidenten Kanten in adjList abgelegt ist
    HashMap<Integer, Node> nodeIndex = new HashMap<Integer, Node>();

    try{
     
      FileReader reader = new FileReader(fileName);
      BufferedReader bufferedReader = new BufferedReader(reader);
     
      String line;
     
      while ((line = bufferedReader.readLine()) != null) {
       
        // First line is the number of Nodes
        numNode = Integer.parseInt(line);
       
        // Second line is the number of Edges.
        numArcs = Integer.parseInt(line);
       
        // lines of Nodes.
        for (int nodeCounter=0; nodeCounter < numNode; nodeCounter++) {
        nodeRef = Node.parseNode(line);
        nodeIndex.put((Integer) nodeRef.getId(), nodeRef);
        }
       
        // lines of Arcs.
        for (int arcCounter=0; arcCounter < numArcs; arcCounter++) {
        arcRef = Arc.parseArc(line);
        nodeIndex.get(arcRef.getTailNodeId()).addArc(arcRef);
        }
      }
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
 
Sieht doch gut aus, hast du mal getestet, ob:
keine Exception geprintet wird
und
indexNodeMap die gewünschten Elemente enthält
?

Der Rest sieht dann so aus:
Durchlaufe/Interiere alle Entities...
 
Also die Classe Arc hat zwar jetzt ein tailNodeId, aber die wird ja nicht gesetzt im Konstruktor und wird auch nicht mit gelesen? Wenn Du eine Zeile einliest, dann musst Du natürlich alle Werte einlesen!
 
Und die ganzen Reader sollten vielleicht auch einmal geschlossen werden, wenn die Einleselogik fertig ist...
 
Das ist ein guter Hinweis - evtl. einmal "try with resources" auf google suchen. Das ist in meinen Augen mit der sauberste Weg.
 
Ja, aber darüber lässt sich auch streiten, einfach ein close() auf den bufferedReader setzen, würd hier schon genügen...
 
hallo, das bekomme ich als ergebnis:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at Node.parseNode(Node.java:18)
at Graph.readFromFile(Graph.java:49)
at Graph.main(Graph.java:67)
Zum Vergrößern anklicken....
Im main habe einfach nur:
Java: 
  public static void main(String[] args) {
      Graph.readFromFile("SaarlandTest.txt");
  }
Der Fehler liegt anscheinend ind er Größe des Arrays:
Java: 
//at Node.parseNode(Node.java:18)
float latitude = Float.parseFloat(fields[1]);
//at Graph.readFromFile(Graph.java:49)
nodeRef = Node.parseNode(line);
// at Graph.main(Graph.java:67)#
Graph.readFromFile("SaarlandTest.txt");
 
Zuletzt bearbeitet:
Funktioniert denn dein split("\t") in parseNode ?? Ich würde es mit:

Code: 
line.split("\\s+");
machen. Das trennt bei whitespace, egal ob blank oder tab.
 
nino2015 hat gesagt.:
So sieht momentan die Methode readFromFile aus:
Zum Vergrößern anklicken....

Ich hätte das Einlesen auch so gemacht wie du:
Java: 
import java.io.*;
import java.util.*;

public class Temp {

    public static void main(String[] args) throws IOException {
        int i1, i2;
        HashMap<Integer, Node> map1 = new HashMap<Integer, Node>();
        HashMap<Integer, Arc> map2 = new HashMap<Integer, Arc>();

        BufferedReader reader = new BufferedReader(new StringReader(
                  "3\n"
                + "2\n"
                + "0 49.009 7.815\n"
                + "1 48.997 7.812\n"
                + "2 49.017 7.799\n"
                + "0 1 17 30\n"
                + "1 2 5 120"));
        i1 = Integer.parseInt(reader.readLine());
        i2 = Integer.parseInt(reader.readLine());
        for (int i = 0; i < i1; i++) {
            Node n = new Node(reader.readLine());
            map1.put(n.getFunc2(), n);
        }
        for (int i = 0; i < i2; i++) {
            Arc a = new Arc(reader.readLine());
            map2.put(a.getFunc2(), a);
        }
        reader.close();

        for (Map.Entry<Integer, Node> e : map1.entrySet()) {
            System.out.println("e = " + e);
        }
        for (Map.Entry<Integer, Arc> e : map2.entrySet()) {
            System.out.println("e = " + e);
        }

        //TODO
    }

    private static float func1(int f, int t) {
        return (float) (Math.random() * (t - f + 1) + f);
    }

    private static class Arc {

        int i1 = (int) func1(0, 1);
        int i2 = (int) func1(1, 2);
        int i3 = (int) func1(5, 17);
        int i4 = (int) func1(30, 120);

        private Arc(String string) {
            //TODO
        }

        private Integer getFunc2() {
            return i1;
        }

        @Override
        public String toString() {
            return "Arc{" + "i1=" + i1 + ", i2=" + i2 + ", i3=" + i3 + ", i4=" + i4 + '}';
        }
    }

    private static class Node {

        int i1 = (int) func1(0, 2);
        float f1 = func1(48, 49);
        float f2 = func1(7, 7);

        private Node(String string) {
            //TODO
        }

        private Integer getFunc2() {
            return i1;
        }

        @Override
        public String toString() {
            return "Node{" + "i1=" + i1 + ", f1=" + f1 + ", f2=" + f2 + '}';
        }
    }
}

Gibt dann aus:
Code: 
e = 0=Node{i1=0, f1=48.68379, f2=7.517006}
e = 1=Node{i1=1, f1=49.40827, f2=7.611507}
e = 2=Node{i1=2, f1=48.72167, f2=7.838958}
e = 0=Arc{i1=0, i2=1, i3=14, i4=65}
e = 1=Arc{i1=1, i2=2, i3=14, i4=99}

TODO: Das splitten der Zeile musst du machen.

TODO danach: Aus dem gerichteten Graph einen ungerichteten Graph machen, indem über Knoten und Kanten iteriert wird, nach einem Algorithmus dafür nachzulesen.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

gerichteter Graph
Antworten: 9
Type mismatch: cannot convert from Graph.Edge to ArrayList<Graph.Edge>
Antworten: 21
Graph einlesen
Antworten: 2
String aus einer Datei einlesen und in anderer Datei speichern
Antworten: 20
Hilfe bei einer GUI Programmierung mit Graph
Antworten: 30

Zurück
Oben