Übung Grundbegriffe der Graphentheorie 1

Aus ProgrammingWiki

Archivierte Version vom 2015-10-25T16:16:14+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

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