# Ungerichtete Graphen



## m-r-t (7. Jan 2015)

Hi leute, ich muss die nachfolgende, für gerichtete Graphen entworfene Klasse Graph verwenden, um die Klasse UnGraph zu implementieren, die die selben Methoden (Hinzufügen/Entfernen/Zählen/Existenzprüfung von Kanten, Ausgabe der Adjazenzmatrix) für ungericchtete Graphen bereitstellt.

Dazu sollen wir das Prinzip der Vererbung nutzen!

Die Klasse Graph habe ich schonmal zum laufen gebracht:

```
public class Graph {

	private int n;
	private boolean[][] adj;
	private int edgecount = 0;
	
	public Graph( int n) {
		if(n < 0) {
			throw new IllegalArgumentException(
					"n must not be less than 0.");
		}
		this.n = n;
		this.adj = new boolean[n][n];
	}
	
private void checkVertex(int v) {
	if (v < 0 || v >= this.n) {
		throw new InvalidVertexException(
				v, this.n);
	}
}

public boolean hasEdge(int from, int to) {
	this.checkVertex(from);
	this.checkVertex(to);
	return this.adj[from][to];
}

public boolean addEdge(int from, int to) {
	this.checkVertex(from);
	this.checkVertex(to);
	if (!this.adj[from][to]) {
		this.adj[from][to] = true;
		this.edgecount++;
		return true;
	} else {
		return false;
	}
}

public boolean removeEdge(int from, int to) {
	this.checkVertex(from);
	this.checkVertex(to);
	if (this.adj[from][to]) {
		this.adj[from][to] = false;
		this.edgecount--;
		return true;
	} else {
		return false;
	}
}

public int countEdges() {
	return this.edgecount;
}

public String toString() {
	StringBuilder b = new StringBuilder();
	for (int i = 0; i < this.n; ++i) {
		for(int j = 0; j < this.n; ++j) {
		b.append(adj[i][j] ? '1' : '0');
		if (j < n - 1) {
			b.append(' ');
		}
	}
	b.append('\n');
}
return b.toString();

}

public static class InvalidVertexException
	extends IndexOutOfBoundsException {
  public InvalidVertexException (int v, int n) {
	  super("Vertex number"+ v + "is out of range [0," + (n-1) + "]");
  }
}

public static void main(String[] args) {
	Graph g = new Graph(5);
	g.addEdge(0, 1); g.addEdge(1, 3); g.addEdge(2, 1); g.addEdge(2, 4); g.addEdge(3, 4);
	System.out.println(g.countEdges() + "\n" + g.toString());
	try { g.removeEdge(5, 5); } catch (InvalidVertexException e) {
		System.out.println(e);
	}
}
}
```

Ausgabe:

5
0 1 0 0 0
0 0 0 1 0
0 1 0 0 1
0 0 0 0 1
0 0 0 0 0

Graph$InvalidVertexException: Vertex number5is out of range [0,4]


Nun muss ich es für ungerichtete Graphen ändern. Das heißt dann wenn ein Knoten in beide Richtungen erreichbar ist, wie z.B. g.addEdge(1, 3); g.addEdge(3, 1); dann wäre hier das der fall bei  1 und 3. Müsste dann neben der 0 und 1 eine 2 als ausgabe kommen? Wegen beiden Richtungen?

Bin ich gedanklich schonmal auf dem richtigen Weg? Und wo müsste ich anfangen um es im Code durchzusetzen?

Hoffe ihr könnt mir helfen! Vielen Dank im Voraus!


----------



## diggaa1984 (8. Jan 2015)

> Müsste dann neben der 0 und 1 eine 2 als ausgabe kommen? Wegen beiden Richtungen?
> Bin ich gedanklich schonmal auf dem richtigen Weg?



Nein es würde dennoch nur 0 und 1 in der Ausgabe enthalten sein, aber dafür mehr 1 als vorher.
Wenn ein gerichteter Graph 2 Knoten hat und es gibt eine Kante von Knoten 1 zu 2 dann sieht die Matrix so aus:
0 1
0 0

Ist der Graph ungerichtet und jemand fügt eine Kante zwischen 1 und 2 ein, dann kommt folgendes raus:
0 1 
1 0

Somit wird angezeigt, dass es eine Kante von 1 zu 2 und von 2 zu 1 gibt.



> Und wo müsste ich anfangen um es im Code durchzusetzen?


 Das hast du doch selbst schon beantwortet:


> ch muss die nachfolgende, für gerichtete Graphen entworfene Klasse Graph verwenden, um die Klasse UnGraph zu implementieren, die die selben Methoden für ungericchtete Graphen bereitstellt.
> Dazu sollen wir das Prinzip der *Vererbung* nutzen! ... Das heißt dann wenn ein Knoten in beide Richtungen erreichbar ist, wie z.B. g.addEdge(1, 3); g.addEdge(3, 1);



Du nutzt bei der Vererbung ja die Prinzipien des gerichteten Graphen nur dass du beim ungerichteten Graphen beim hinzufügen und entfernen von Kanten noch ein wenig mehr zu tun hast als beim gerichteten Graph.

Vesuche es erst einmal selbst und zeige uns was du geschafft hast. Wenn du weiter Probleme hast beim Programmieren kann man ja helfen, aber versuchen solltest du es zunächst selbst.


----------



## minzee (8. Jan 2015)

Die Adjazenzmatrix ist auf https://de.wikipedia.org/wiki/Adjazenzmatrix ganz gut erklärt.


----------



## m-r-t (9. Jan 2015)

Hi, danke erstmal für eure antworten

ich fange wie folgt an:


```
import Graph.InvalidVertexException;


public class UnGraph extends Graph {

	
	
	
	public static void main(String[] args) {
		UnGraph g = new UnGraph(5);
		g.addEdge(0, 1); g.addEdge(1, 3); g.addEdge(3, 1); g.addEdge(2, 4); g.addEdge(3, 4);
		System.out.println(g.countEdges() + "\n" + g.toString());
		try { g.removeEdge(5, 5); } catch (InvalidVertexException e) {
			System.out.println(e);
		}

}
```



> Du nutzt bei der Vererbung ja die Prinzipien des gerichteten Graphen nur dass du beim ungerichteten Graphen beim hinzufügen und entfernen von Kanten noch ein wenig mehr zu tun hast als beim gerichteten Graph.



ich habe eine neue class angefangen und versuche es mit der Vererbung, nun muss ich hier nur noch die veränderten public boolean addEdge und public boolean removeEgde einfügen wegen den Kanten, richtig? Ist der Ansatz schonmal ok?


----------



## m-r-t (9. Jan 2015)

> Du nutzt bei der Vererbung ja die Prinzipien des gerichteten Graphen nur dass du beim ungerichteten Graphen beim hinzufügen und entfernen von Kanten noch ein wenig mehr zu tun hast als beim gerichteten Graph.



eine weitere frage habe ich noch. Muss ich noch was am Code ändern, also bei den Methoden? Mir ist noch nicht geläufig was ich beim ungerichteten Graphen beim hinzufügen und entfernen von kanten noch mehr machen muss. Denn die 1 fügt er ja ein wenn es verlangt wird wie z.B. g.addEdge(1, 3); g.addEdge(3, 1); .  Ich glaube das ich bei dieser aufgabe nur die vererbung hinkriegen muss bei class UnGraph ohne großartiges ändern des quelltextes ganz oben.


----------



## diggaa1984 (9. Jan 2015)

Also zu deinem vorherigen Post:
Vererbt hast du ja schon 

Die main-Methode kannst du im Graph belassen oder am besten noch in eine extra Klasse schreiben. Aber das ist egal. Ziel ist es ohne Änderungen an der main-Methode selbst (wie sie in Graph-Klasse vorliegt) den ungerichteten Graphen korrekt zu erzeugen.



> Muss ich noch was am Code ändern, also bei den Methoden? Mir ist noch nicht geläufig was ich beim ungerichteten Graphen beim hinzufügen und entfernen von kanten noch mehr machen muss.


Welchen wesentlichen Unterschied gibt es zwischen einem gerichteten und einem ungerichtetem Graphen?

Das sollte deine Basis sein. Und denk dran, mit super kannst du die Oberklasse ansprechen (Zb. den entsprechenden Konstruktor aufrufen, der dir ja schon einige Sachen vorinitialisiert).


```
public class UnGraph extends Graph {
      
    public UnGraph( int n) {
        super(n);
    }
     
    public boolean hasEdge(int from, int to) {
        //gibt es hier neues zu beachten?
    }
     
    public boolean addEdge(int from, int to) {
        //was gibt es hier zu beachten?
    }
     
    public boolean removeEdge(int from, int to) {
        //was gibt es hier zu beachten?
    }
     
    public int countEdges() {
        //hier auch?
    }
     
    public String toString() {
        //hier etwas neues, oder nicht?
    }
}
```


```
public class Main {

    public static void main(String[] args) {
        //Graph g = new Graph(5);
        Graph g = new UnGraph(5); //selber Algorithmus, andere Ausgabe nur durch Änderung der Implementierung!
        g.addEdge(0, 1); g.addEdge(1, 3); g.addEdge(2, 1); g.addEdge(2, 4); g.addEdge(3, 4);
        System.out.println(g.countEdges() + "\n" + g.toString());
        try { g.removeEdge(5, 5); } catch (InvalidVertexException e) {
            System.out.println(e);
        }
    }
}
```


----------



## m-r-t (10. Jan 2015)

hi, habe folgendes produziert. Ich hoffe ich sinke damit nicht tiefer, das mit der vererbung macht mich noch zu schaffen.
Es läuft fehlerfrei, aber weiß nicht ob es auch so sein soll vom Code her:


```
public class UnGraph extends Graph {
 
public UnGraph( int n) {
super(n);

}

 
public boolean hasEdge(int from, int to) {
	super.hasEdge(from,to);
	
	return super.hasEdge(from,to);
}

public boolean addEdge(int from, int to) {
	super.addEdge(from,to);
	
		
		return true;
	} 
	


public boolean removeEdge(int from, int to) {
	super.removeEdge(from,to);
	return true;
}

public int countEdges() {
	return super.countEdges();
}

public String toString() {
	super.toString();

return super.toString();

}

	 
public static void main(String[] args) {
//Graph g = new Graph(5);
Graph g = new UnGraph(5); //selber Algorithmus, andere Ausgabe nur durch Änderung der Implementierung!
g.addEdge(0, 1); g.addEdge(1, 3); g.addEdge(2, 1); g.addEdge(2, 4); g.addEdge(3, 4);
System.out.println(g.countEdges() + "\n" + g.toString());
try { g.removeEdge(5, 5); } catch (InvalidVertexException e) {
System.out.println(e);
}
}
}
```


----------



## diggaa1984 (10. Jan 2015)

Ok, damit hast du noch nichts gewonnen 
Mal sehen ob das klappt 

Frage:
*hasEdge:*
Beschreibe was die Methode im gerichteten Graphen (Graph) macht!
Reicht das aus für einen ungerichteten Graphen (UnGraph)?
Was müsste man ändern, wenn es nicht ausreicht?

*addEdge:*
Beschreibe was die Methode im gerichteten Graphen (Graph) macht!
Reicht das aus für einen ungerichteten Graphen (UnGraph)?
Was müsste man ändern, wenn es nicht ausreicht?

*removeEdge:*
Beschreibe was die Methode im gerichteten Graphen (Graph) macht!
Reicht das aus für einen ungerichteten Graphen (UnGraph)?
Was müsste man ändern, wenn es nicht ausreicht?

*countEdges:*
Beschreibe was die Methode im gerichteten Graphen (Graph) macht!
Reicht das aus für einen ungerichteten Graphen (UnGraph)?
Was müsste man ändern, wenn es nicht ausreicht?

Kleiner Tipp:

```
//wenn man eh nur die entsprechende super-Methode aufruft und nichts weiter macht, 
//dann brauchst du diese Methode auch nicht überschreiben. Sie ist dann implizit in UnGraph 
//durch die Oberklasse auch verfügbar.
public String toString() {
    //super.toString(); kannst du dir sparen, da du es beim return ja auch aufrufst.
    return super.toString();
}
```


----------



## m-r-t (10. Jan 2015)

hasEdge:
hier werden doch die Kanten gebildet, sofern die Knoten-Eingaben der Methode checkVertex passen dann sehe ich hier erstmal kein verbesserungsbedarf .

addEdge:
hier werden Kanten hinzugefügt sofern es sie nicht gibt, dann müsste man beim UnGraph erst gucken ob es in beide richtungen von z.B. 1 und 3 gibt, bevor er eine Kante hinzufügt.

removeEdge: hier werden Kanten entfernt, beim UnGraph müsste er dann entfernen wenns nur in eine Richtung ist.

countEdges: hier werden die Kanten gezählt, das müsste gleich bleiben.

Richtig?


----------



## diggaa1984 (10. Jan 2015)

m-r-t hat gesagt.:


> hasEdge:
> hier werden doch die Kanten gebildet, sofern die Knoten-Eingaben der Methode checkVertex passen dann sehe ich hier erstmal kein verbesserungsbedarf .


Wo ist der Unterschied zwischen "Kanten bilden" und "Kanten hinzufügen" (deine Formulierung für addEdge)?
Erklärung hasEdge: 
In der Methode hasEdge prüft er zunächst durch "checkVertex" ob die Knotenindizes im Bereich [0,n)
(inklusive 0, exklusive n). Wenn ja, dann gibt hasEdge zurück, ob eine Kante vom ersten zum zweiten Knoten verläuft.
Immer noch ok oder muss hier angepasst werden?



m-r-t hat gesagt.:


> addEdge:
> hier werden Kanten hinzugefügt sofern es sie nicht gibt, dann müsste man beim UnGraph erst gucken ob es in beide richtungen von z.B. 1 und 3 gibt, bevor er eine Kante hinzufügt.


Ja es werden Kanten hinzugefügt.
Was möchtest du beim UnGraph erst schauen? 
Richtig wäre für den Ungraph .. fügt jemand eine Kante von Knoten 1 zu Knoten 3 hinzu, somuss UnGraph sicherstellen, dass auch automatisch eine Kante von Knoten 3 zu Knoten 1 eingefügt wird, damit die Adjazenzmatrix stimmt.



m-r-t hat gesagt.:


> removeEdge: hier werden Kanten entfernt, beim UnGraph müsste er dann entfernen wenns nur in eine Richtung ist.


Da weiss ich nicht ganz ob ich dich da richtig verstanden habe ^^
Beim UnGraph gibt es ja nicht nur "eine Richtung". Es werden immer beide Richtungen garantiert. Das heisst beim Entfernen einer Kante von Knoten 1 zu 3 muss der ungerichtete Graph automatisch die Kante von Knoten 3 zu Knoten 1 entfernen. Sonst ist es nicht mehr korrekt.



m-r-t hat gesagt.:


> countEdges: hier werden die Kanten gezählt, das müsste gleich bleiben.
> Richtig?


Richtig


----------



## m-r-t (10. Jan 2015)

> Wenn ja, dann gibt hasEdge zurück, ob eine Kante vom ersten zum zweiten Knoten verläuft.
> Immer noch ok oder muss hier angepasst werden?



meinst du das er noch beachten muss, das vom zweiten Knoten zum ersten eine Kante verläuft, also in beide Richtungen?
Ansonsten komme ich echt nicht drauf, sry dafür, muss echt noch viel Wissen aufholen


----------



## m-r-t (10. Jan 2015)

Wenn das geklärt wäre, bleibt die frage wie programmiere ich das, wo müsste ich anfangen?


----------



## diggaa1984 (10. Jan 2015)

m-r-t hat gesagt.:


> meinst du das er noch beachten muss, das vom zweiten Knoten zum ersten eine Kante verläuft, also in beide Richtungen?
> Ansonsten komme ich echt nicht drauf, sry dafür, muss echt noch viel Wissen aufholen



Das könnte man durchaus überprüfen um sicherzugehen .. aber falls in einem ungerichteten Graphen nur eine dieser 2 Kanten existiert, dann hast du quasi beim Aufbau was falsch gemacht  .. Durch die Prüfung auf beide Kanten, stellst du quasi sicher, dass andere Methoden korrekt sind.


----------



## diggaa1984 (10. Jan 2015)

m-r-t hat gesagt.:


> Wenn das geklärt wäre, bleibt die frage wie programmiere ich das, wo müsste ich anfangen?


Das Grundgerüst hatte ich dir ja gegeben .. nun musst du quasi mit den Antworten zu den einzelnen Methoden arbeiten. Was fehlt um den ungerichteten Graphen zu erzeugen, was aber nicht schon in der Superklasse umgesetzt ist! Das ist das Lernziel bei dieser Vererbung. Was kannst du von der Oberklasse alles nutzen um mit möglichst wenig Aufwand die Implementierung des ungerichteten Graphen zu realisieren. Ich bin gespannt auf deinen Versuch 

Ich helfe auch weiter aber jetzt bist du dran.

Wo fängt man an?
Unterschiedlich .. ich würde mit der addEdge anfangen und gleich bei der Ausgabe der Matrix gucken ob diese korrekt ist. Wenn, dann weiter zur nächsten Methode


----------



## m-r-t (10. Jan 2015)

ok danke für deine Hilfe, werde mir mühe geben

in der superklasse wird in eine richtung geprüft, also müsste ich bei UnGraph das genutzte in der superklasse so verbinden das es in beide richtungen getan wird...

so als erste Idee auf anhieb


----------



## m-r-t (11. Jan 2015)

So, habs mal endlich zu Ende gebracht. Ich habe den tipp bekommen alles in einer Klasse zu versuchen, habs mal gemacht und fiel mir einfacher. Sonst wäre  ich wohl noch länger dran.


```
class UnGraph extends Graph {
public UnGraph( int n) {
super(n);
}
public boolean hasEdge ( int from , int to ) {
this . checkVertex ( from ) ;

this . checkVertex ( to ) ;
return this . adj [ from ] [ to ] || this . adj [ to ] [ from ] ;
}
public boolean addEdge ( int from , int to ) {
this . checkVertex ( from ) ;
this . checkVertex ( to ) ;
if ( ! this . adj [ from ] [ to ] && ! this . adj [ to ] [ from ] ) {
this . adj [ from ] [ to ] = true ;
this . adj [ to ] [ from ] = true ;
this . edgecount++;
return true ;
} else {
return false ;
}
}
public boolean removeEdge ( int from , int to ) {
this . checkVertex ( from ) ;
this . checkVertex ( to ) ;
if ( this . adj [ from ] [ to ] && this . adj [ to ] [ from ] ) {
this . adj [ from ] [ to ] = false ;
this.adj [ to ] [ from ] = false ;
this.edgecount--;
return true ;
} else {
return false ;
}
}
public int countEdges ( ) {
return this.edgecount ;
}
}[/]

Funktioniert auch fehlerfrei, hoffe das es auch so richtig ist und wie es die aufgabe verlangt.
```


----------



## diggaa1984 (11. Jan 2015)

Da hast du ausser beim Konstruktor die Vererbung gekonnt ignoriert 
Ziel wäre es die super-Methoden zu nutzen, da diese ja schon die eigentlich Funktion (hinzufügen, entfernen und zählen von Kanten) bereitstellen 

Mal sehen ob du verstanden hast was ich meine.


----------



## m-r-t (11. Jan 2015)

hi meinst du evtl das hier, hatte es am anfang so rum versucht, dann fiel mir das umgehen wo ich dann die aufgabenstllung im eifer des gefechts wohl ignoriert habe 

public boolean hasEdge ( int from , int to ) {
super . hasEdge ( from,to ) ;


return super . adj [ from ] [ to ] || super . adj [ to ] [ from ] ;
}


----------



## diggaa1984 (11. Jan 2015)

```
public boolean hasEdge ( int from , int to ) {
     super . hasEdge ( from,to ) ;
    return super . adj [ from ] [ to ] || super . adj [ to ] [ from ] ;
}
```

nein das könnte optimistisch betrachtet eher so aussehen:

```
public boolean hasEdge ( int from , int to ) {
     return (super.hasEdge(from, to) && (super.hasEdge(to, from))) ;
}
```

Was hier noch nicht abgedeckt wird, ist ein fehlerhafter Aufbau des ungerichteten Graphen (zB. nur eine von 2 nötigen Kanten da). Aber wenn man davon ausgeht, dass alles stimmt, reicht das so oben.

Spannend wird ja nun die Verwendung der Super-Methoden für add und remove


----------



## m-r-t (11. Jan 2015)

ok, ja du hast recht bei add and remove wirds schwierig,

public boolean addEdge ( int from , int to ) {

if ( ! super.addEdge(from, to) && ! (super.addEdge(to, from))) {
....../ hier ist es spannend, kannst du mir vll einen tipp geben was ich beachten muss


----------



## diggaa1984 (11. Jan 2015)

Ok also was macht Graph bei addEdge?
* Prüft ob der erste Knotenindex gültig ist
* Prüft ob der zweite Knotenindex gültig ist
* Wenn Kante nicht existent, dann hinzufügen und edgeCount erhöhen
* Wenn Kante exisiert, dann passiert nichts

Was muss UnGraph machen?
* 2 Kanten statt nur einer hinzufügen damit quasi Hin und Rückweg da sind und somit die Ungerichtetheit umgesetzt ist.
* korrekten Wert für edgeCount sicherstellen

nun du nochmal


----------



## m-r-t (14. Jan 2015)

hi, da ich nicht ganz fertig gewroden bin, hatte ich dich aufgabe so abgegeben, damit ich wenigstens ein paar punkte bekomme, jetzt habe ich es zurückbekommen und volle Punktzahl bekommen(was mich sehr gewundert hat), deswegen will ich das mal so lassen da ich es so besser verstanden habe. Und mich den anderen aufgaben widmen, da die klausur sicher und schnell naht. Werde trotzdem zwischen durch mal versuchen es zu verstehen und darauf zurückkommen.
.

```
class UnGraph extends Graph {
public UnGraph( int n) {
super(n);
}
public boolean hasEdge ( int from , int to ) {
this . checkVertex ( from ) ;

this . checkVertex ( to ) ;
return this . adj [ from ] [ to ] || this . adj [ to ] [ from ] ;
}
public boolean addEdge ( int from , int to ) {
this . checkVertex ( from ) ;
this . checkVertex ( to ) ;
if ( ! this . adj [ from ] [ to ] && ! this . adj [ to ] [ from ] ) {
this . adj [ from ] [ to ] = true ;
this . adj [ to ] [ from ] = true ;
this . edgecount++;
return true ;
} else {
return false ;
}
}
public boolean removeEdge ( int from , int to ) {
this . checkVertex ( from ) ;
this . checkVertex ( to ) ;
if ( this . adj [ from ] [ to ] && this . adj [ to ] [ from ] ) {
this . adj [ from ] [ to ] = false ;
this.adj [ to ] [ from ] = false ;
this.edgecount--;
return true ;
} else {
return false ;
}
}
public int countEdges ( ) {
return this.edgecount ;
}
}[/]
```


----------

