# Graph mit Swing zeichnen



## ioannis_m (16. Okt 2016)

Hallo zusammen, 

ich versuche einen Graphen mit numberV Knoten und numberE Kanten auf der Ebene zu zeichnen. Das Programm hängt gleich am Anfang ohne Fehlermeldung.


```
public interface Graph {
    int getV();
    int getE();
    boolean directed();
//    void insert(Edge e);
//    void remove(Edge e);
    boolean edge();
    AdjList getAdjList(int v);
}
```



```
import java.awt.Graphics;
import java.awt.Graphics2D;

public class SparseGraph implements Graph {


    private int numberV, numberE;
    private boolean digraph;
    private static class Node{
        int nodeName; Node next;
        Node(int nodeName, Node n){
            this.nodeName = nodeName; this.next = n;
        }
    }
   
    private static class Edge {
        int fromNodeName, toNodeName;
       
        Edge(int v, int w){
            this.fromNodeName = v;
            this.toNodeName = w;
        }
       
//        int v(){
//            return fromNodeName;
//        }
//       
//        int w(){
//            return toNodeName;
//        }

    }

   
    private Node adj[];
   
    public SparseGraph(int numberV, boolean flag) {
        this.numberV = numberV; digraph = flag;
        adj = new Node[numberV];
    }
    @Override
    public int getV() {
        return numberV;
    }

    @Override
    public int getE() {
        return numberE;
    }

    @Override
    public boolean directed() {
        return digraph;
    }

    public void insert(Edge givenEdge) {
        int fromNodeName = givenEdge.fromNodeName; int toNodeName = givenEdge.toNodeName;
        adj[fromNodeName] = new Node(toNodeName, adj[fromNodeName]);
        if (!directed())adj[toNodeName] = new Node(fromNodeName, adj[toNodeName]);
        numberE++;
    }

    public void remove(Edge givenEdge) {
        int fromNodeName = givenEdge.fromNodeName; int toNodeName = givenEdge.toNodeName;
       
       
        AdjLinkedList adjList = (AdjLinkedList) getAdjList(fromNodeName);// Search in the begNode list for endNode
        Node previousToCurrentNode = adjList.begNode();
       
        for (Node n = adjList.begNode();!adjList.end(); n = adjList.nextNode()){
            if (n.nodeName == toNodeName){
                previousToCurrentNode.next = n.next;    // Assign the current next Node to the previous next variable
                n.next = null;
            }
            previousToCurrentNode = n;
        }
       
        adjList = (AdjLinkedList) getAdjList(toNodeName);    // Search in the endNode list for begNode
        previousToCurrentNode = adjList.begNode();
       
        for (Node n = adjList.begNode();!adjList.end(); n = adjList.nextNode()){
            if (n.nodeName == fromNodeName){
                previousToCurrentNode.next = n.next;    // Assign the current next Node to the previous next variable
                n.next = null;
            }
            previousToCurrentNode = n;
        }
    }

    @Override
    public boolean edge() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public AdjList getAdjList(int v) {
        return new AdjLinkedList(v);
    }
        private class AdjLinkedList implements AdjList{
            private int v; private Node t;
            AdjLinkedList(int v) {
                this.v = v; t = null;
            }
            public int beg(){
                t = adj[v];
                return t == null ? -1 : t.nodeName;
            }
            public int next(){
                if (t != null) t = t.next;
                return t == null ? -1 : t.nodeName;
            }
            public boolean end(){
                return t == null;
            }
           
           
            public Node begNode(){
                t = adj[v];
                return t == null ? null : t;
            }
            public Node nextNode(){
                if (t != null) t = t.next;
                return t == null ? null : t;
            }
               
    }
       
    public Graph fillAndPlot(Graphics g, int numberE){
        Graphics2D g2 = (Graphics2D)g;
        this.numberE = numberE;
       
        for (int i = 0; i < getE(); i++){                // Fill the adj[numberV] array with random numberE edges
            int v = (int) (this.getV()*Math.random());
            int w = (int) (this.getV()*Math.random());
            this.insert(new Edge(v, w));
        }
       
        for (int v = 0; v < getV(); v++){                // Draw numberV random points
            int x1 = (int) (100*Math.random());
            int y1 = (int) (100*Math.random());
            g2.fillOval(x1, y1, 7, 7);
           
            AdjList a = getAdjList(v);                    // Draw numberE lines
            for (a.beg(); !a.end(); a.next()){
            int x2 = (int) (100*Math.random());
            int y2 = (int) (100*Math.random());
                g2.drawLine(x1, y1, x2, y2);
            }
        }
       
        return this;
    }
}
```



```
import java.awt.*;
import java.awt.Graphics2D;
import java.awt.geom.Arc2D;
import java.awt.geom.Line2D;
import java.awt.geom.QuadCurve2D;

import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class DrawingGraph extends JPanel{
    public void paintComponent(Graphics g){
        Graphics2D g2 = (Graphics2D)g;
//        g2.draw(new Line2D.Double(59.2d, 99.8d, 519.1d, 99.8d).getBounds());
//        g2.drawLine(120, 50, 360, 190);
//        g2.drawLine(180, 110, 500, 90);
        SparseGraph sparseGraph = new SparseGraph(5, false);
        sparseGraph.fillAndPlot(g2, 7);
//        g2.fillOval(150, 60, 7, 7);
//        System.out.println(this.getWidth());
//        g2.draw(new QuadCurve2D.Double(59.2d, 99.8d, 519.1d, 99.8d, 30, 30));
   
    }
private static void createAndShowGUI(){
    JFrame f = new JFrame("Demo");
    f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    f.setSize(600, 200);
    f.add(new DrawingGraph());
    f.setVisible(true);
    }

public static void main(String args[]){
    Runnable doCreateAndShowGUI = new Runnable(){
        public void run(){
            createAndShowGUI();
        }
    };
    SwingUtilities.invokeLater(doCreateAndShowGUI);
    }
}
```


Wäre für jeden Rat dankbar...

mfg
ioannis


----------



## Robat (16. Okt 2016)

Hey ioannis,

versuch mal mit dem Debugger zu arbeiten und raus zukriegen, wo dein Programm sich aufhängt. Dann könntest du uns mitteilen an welcher Stelle es ist, da es so recht schwer ist das raus zu finden.

Und einfach aus persönlichen Gründen mal die Frage:
Was ist _*AdjList*_ ?

Gruß
Robert


----------



## Meniskusschaden (16. Okt 2016)

Das hier sieht ziemlich verdächtig aus:

```
for (int i = 0; i < getE(); i++) { // Fill the adj[numberV] array with
                                            // random numberE edges
            int v = (int) (this.getV() * Math.random());
            int w = (int) (this.getV() * Math.random());
            this.insert(new Edge(v, w));
        }
```
Du fügst offenbar ohne Bedingung bei jedem Schleifendurchlauf eine neue Kante ein, so dass i niemals größer oder gleich getE() werden kann.


----------



## ioannis_m (16. Okt 2016)

Hallo Robert, 

die Datenstruktur hinter diesem dünnbesiedelten Graph ist eine array aus Listen, die die anschliessenden Knoten eines jeden Knoten repräsentieren sollen. AdjList ist der iterator der Klasse, der genau diese Knoten züruckgibt.

Ich habe die Methode print() hinzugefügt, das Problem scheint in der SparseGraph Klasse zu sein.


```
import java.awt.Graphics;
import java.awt.Graphics2D;

public class SparseGraph implements Graph {


    private int numberV, numberE;
    private boolean digraph;
    private static class Node{
        int nodeName; Node next;
        Node(int nodeName, Node n){
            this.nodeName = nodeName; this.next = n;
        }
    }
   
    private static class Edge {
        int fromNodeName, toNodeName;
       
        Edge(int v, int w){
            this.fromNodeName = v;
            this.toNodeName = w;
        }
       
//        int v(){
//            return fromNodeName;
//        }
//       
//        int w(){
//            return toNodeName;
//        }

    }

   
    private Node adj[];
   
    public SparseGraph(int numberV, boolean flag) {
        this.numberV = numberV; digraph = flag;
        adj = new Node[numberV];
    }
    @Override
    public int getV() {
        return numberV;
    }

    @Override
    public int getE() {
        return numberE;
    }

    @Override
    public boolean directed() {
        return digraph;
    }

    public void insert(Edge givenEdge) {
        int fromNodeName = givenEdge.fromNodeName; int toNodeName = givenEdge.toNodeName;
        adj[fromNodeName] = new Node(toNodeName, adj[fromNodeName]);
        if (!directed())adj[toNodeName] = new Node(fromNodeName, adj[toNodeName]);
        numberE++;
    }

    public void remove(Edge givenEdge) {
        int fromNodeName = givenEdge.fromNodeName; int toNodeName = givenEdge.toNodeName;
       
       
        AdjLinkedList adjList = (AdjLinkedList) getAdjList(fromNodeName);// Search in the begNode list for endNode
        Node previousToCurrentNode = adjList.begNode();
       
        for (Node n = adjList.begNode();!adjList.end(); n = adjList.nextNode()){
            if (n.nodeName == toNodeName){
                previousToCurrentNode.next = n.next;    // Assign the current next Node to the previous next variable
                n.next = null;
            }
            previousToCurrentNode = n;
        }
       
        adjList = (AdjLinkedList) getAdjList(toNodeName);    // Search in the endNode list for begNode
        previousToCurrentNode = adjList.begNode();
       
        for (Node n = adjList.begNode();!adjList.end(); n = adjList.nextNode()){
            if (n.nodeName == fromNodeName){
                previousToCurrentNode.next = n.next;    // Assign the current next Node to the previous next variable
                n.next = null;
            }
            previousToCurrentNode = n;
        }
    }

    @Override
    public boolean edge() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public AdjList getAdjList(int v) {
        return new AdjLinkedList(v);
    }
        private class AdjLinkedList implements AdjList{
            private int v; private Node t;
            AdjLinkedList(int v) {
                this.v = v; t = null;
            }
            public int beg(){
                t = adj[v];
                return t == null ? -1 : t.nodeName;
            }
            public int next(){
                if (t != null) t = t.next;
                return t == null ? -1 : t.nodeName;
            }
            public boolean end(){
                return t == null;
            }
           
           
            public Node begNode(){
                t = adj[v];
                return t == null ? null : t;
            }
            public Node nextNode(){
                if (t != null) t = t.next;
                return t == null ? null : t;
            }
               
    }
       
    private void fill(int numberE){
        this.numberE = numberE;
       
        for (int i = 0; i < getE(); i++){                // Fill the adj[numberV] array with random numberE edges
            int v = (int) (this.getV()*Math.random());
            int w = (int) (this.getV()*Math.random());
            this.insert(new Edge(v, w));
        }

    }
       
    public Graph fillAndPlot(Graphics g, int numberE){
        Graphics2D g2 = (Graphics2D)g;
        fill(numberE);

        for (int v = 0; v < getV(); v++){                // Draw numberV random points
            int x1 = (int) (100*Math.random());
            int y1 = (int) (100*Math.random());
            g2.fillOval(x1, y1, 7, 7);
           
            AdjList a = getAdjList(v);                    // Draw numberE lines
            for (a.beg(); !a.end(); a.next()){
            int x2 = (int) (100*Math.random());
            int y2 = (int) (100*Math.random());
                g2.drawLine(x1, y1, x2, y2);
            }
        }
       
        return this;
    }
   
    public void print(){
        for (int i = 0; i < getV(); i++){
            System.out.print(i + ": ");
            AdjList a = getAdjList(i);
            for (int j = a.beg(); !a.end(); j = a.next()){
                System.out.print(j + " ");
            }
            System.out.println("");
        }
    }
   
    public static void main (String args[]){
        SparseGraph sG = new SparseGraph(20, false);
        System.out.println(sG.numberV);
        sG.fill(34);
        System.out.println(sG.numberE);
//        sG.print();
    }
}
```

Mit der Zeile


```
sG.fill(34);
```

bekomme ich die Fehlermeldung


```
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at SparseGraph.insert(SparseGraph.java:58)
    at SparseGraph.fill(SparseGraph.java:135)
    at SparseGraph.main(SparseGraph.java:174)
```


----------



## Robat (16. Okt 2016)

Also,..

Die Ecception sollte relative selbsterklärend sein, deswegen geh ich da jetzt nicht weiter drauf ein.

Habe jetzt dein QC fix überflogen und gesehen, dass du relative viele Objekte erzeugst. Das kann ein Grund sein warum du auf diese Exception stößt.
Versuch mal dein QC durch zu gehen und Instanzen die du nicht brauchst zu löschen Sodass du unnötigen Speicher frei machst.

Für weitere Infos einfach mal outofmemory exception bei Google eingeben ;-)


----------



## Meniskusschaden (16. Okt 2016)

Das Problem ist noch immer dasselbe, wie in meinem vorigen Post beschrieben. Irgendwann ist der Speicher dann eben voll.


----------



## ioannis_m (16. Okt 2016)

Hallo Meniskusschaden, 

ich übergebe der Methode den Parameter numberE und somit setze ich die Instanzvariable numberE, die wiederum getE() zurückgibt (-eben sollte?)..


----------



## Meniskusschaden (16. Okt 2016)

Und mit jedem Aufruf von insert() erhöhst du numberE dann um eins.


----------



## ioannis_m (16. Okt 2016)

Ach ja, habe es gerade gerafft...

Vielen Dank an beide.

Gute Nacht
ioannis


----------

