Übung Grundbegriffe der Graphentheorie 1

Aus ProgrammingWiki

Archivierte Version vom 2015-10-25T16:32:21+00:00. Aktuelle Version

Datenstrukturen für Graphen

Gegeben ist folgendes IGraph Interface mit einer Hilfsklasse Edge zur einfacheren Behandlung von Kanten

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;
	}
}

Aufgabe

Erstelle 2 Klassen die das IGraph Interface implementieren
1. als Adjazenzmatrix
2. als Adjazenzliste
Analysiere empirisch die Effizienz dieser beiden Datenstrukturen hinsichtlich
1. Speicherbedarf
2. Ermittlung des Knotengrades
3. Prüfung auf Adjazenz zweier Knoten

Hilfestellung

Es wird ein Graph-Generator bereitgestellt, der das IGraph Interface benutzt um zufällige Graphen zu erzeugen
Mit generate werden dem Graph g eine entsprechende Menge von Knoten (cntVertex) und Kanten (cntEdges) zur Initialisierung übergeben
Die richtige Umsetzung der Speicherung wird mit den Funktionen getVertices und getEdges automatisch geprüft

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;
	}
}

Die implementierte Klasse YourGraph könnte folgendermaßen mit einem Zufallsgraphen getestet werden

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

Übung Grundbegriffe der Graphentheorie 1

Datenstrukturen für Graphen

Aufgabe

Hilfestellung

Suche