Übung Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

<language>Java</language>
==Datenstrukturen für Graphen==
*Gegeben ist folgendes <tt>IGraph</tt> Interface mit einer Hilfsklasse <tt>Edge</tt> zur einfacheren Behandlung von Kanten
<code id="562d004e971ca">
interface IGraph{
	// provides vertices as numbers (ascending, 0-based)
	// and edges between them (edges can be null if there is none)
	void setGraph(int[] vertices, Edge[] edges);
	
	// checks if IGraph returns correct vertices and edges
	int[] getVertices(); // returns vertices ascending
	Edge[] getEdges(); // returns edges 
	
	boolean isAdjacent(int v1, int v2); // returns whether v1 is connected to v2
	int getDegree(int vertex); // returns the degree of a certain vertex
	int getSize(); // returns the size of the class properties
}
class Edge{
	public int v1;
	public int v2;
	public Edge(int v1, int v2){
		// from smaller to greater for improved comparison
		this.v1 = v1 < v2 ? v1 : v2;
		this.v2 = v1 < v2 ? v2 : v1;
	}
	@Override
	public int hashCode() {
		return v1*31+v2;
	}
	@Override
	public boolean equals(Object o){
		if(o instanceof Edge)
		{
			Edge e = (Edge) o;
			return (this.v1 == e.v1 && this.v2 == e.v2);
		}
		return false;
	}
}
</code>

===Aufgabe===
*Erstelle 2 Klassen die das <tt>IGraph</tt> Interface implementieren
*# als Adjazenzmatrix
*# als Adjazenzliste
*Analysiere empirisch die Effizienz dieser beiden Datenstrukturen hinsichtlich
*#Speicherbedarf
*#Ermittlung des Knotengrades
*#Prüfung auf Adjazenz zweier Knoten

===Hilfestellung===
*Es wird ein Graph-Generator bereitgestellt, der das <tt>IGraph</tt> Interface benutzt um zufällige Graphen zu erzeugen
*Mit <tt>generate</tt> werden dem Graph <tt>g</tt> eine entsprechende Menge von Knoten (<tt>cntVertex</tt>) und Kanten (<tt>cntEdges</tt>) zur Initialisierung übergeben
*Die richtige Umsetzung der Speicherung wird mit den Funktionen <tt>getVertices</tt> und <tt>getEdges</tt> automatisch geprüft
<code id="562d004e9724b">
import java.util.Random;
import java.util.HashSet;

class GraphGenerator{
	private GraphGenerator() { }
	private static Random r = new Random();
	// isolated vertices possible
	// no loops possible
	// only one edge between a certain vertex pair
	public static boolean generate(IGraph g, int cntVertex, int cntEdges){
		if (g == null || cntEdges > (long) cntVertex*(cntVertex-1)/2)
			return false;
		int[] v = new int[cntVertex];
		for(int i = 0; i < cntVertex; i++)
			v[i] = i;
		HashSet<Edge> edges = new HashSet<Edge>();
		while (edges.size() < cntEdges){
			int i1 = r.nextInt(cntVertex);
			int i2 = r.nextInt(cntVertex);
			while (i1 == i2)
				i2 = r.nextInt(cntVertex);
			Edge e = new Edge(i1, i2);
			if (!edges.contains(e))
				edges.add(e);
		}
		try{
			Edge[] ed = cntEdges > 0 ? edges.toArray(new Edge[cntEdges]) : null;
			g.setGraph(v, ed);
			int[] gVert = g.getVertices();
			if (gVert.length != v.length){
				System.out.println("Wrong vertex count");
				return false;
			}
			for(int i = 0; i < gVert.length; i++){
				if (v[i] != gVert[i]){
					System.out.println("Different vertex");
					return false;
				}
			}
			Edge[] gEd = g.getEdges();
			if ((gEd == null && ed != null) || (gEd != null && ed == null)){
				System.out.println("Different edge definition");
				return false;
			}
			if (ed != null){
				if (ed.length != gEd.length){
					System.out.println("Different edge count");
					return false;
				}
				for(Edge ge : gEd){
					if (!edges.contains(ge)){
						System.out.println("Different edge");
						return false;
					}
					edges.remove(ge);
				}	
			}
		}
		catch(Exception ex){
			ex.printStackTrace();
			return false;
		}
		return true;
	}
}
</code>
*Die implementierte Klasse <tt>YourGraph</tt> könnte folgendermaßen mit einem Zufallsgraphen getestet werden
<code id="562d004e972bd">
YourGraph graph = new YourGraph(); // instantiate your class
if (!GraphGenerator.generate(graph,10,15)) // generate a random graph with 10 vertices and 15 edges
	System.out.println(graph.getClass().getSimpleName() + " generation failed!");
int d = graph.getDegree(5); // determine degree of vertex 5
boolean b = graph.isAdjacent(3,8); // determine whether vertices 3 and 8 are connected
</code>