Übung Grundbegriffe der Graphentheorie 1

Aus ProgrammingWiki

Archivierte Version vom 2015-10-25T15:05:00+00:00. Aktuelle Version

Programmiertechnische Umsetzung von Graph-Strukturen

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 gibt einen Graph-Generator 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 beiden Klassen können hier im Programming Wiki implementiert werden

import java.util.HashSet;

class GraphAdjMat implements IGraph{
	int[][] adjacency;
	public void setGraph(int[] vertices, Edge[] edges){
		adjacency = new int[vertices.length][vertices.length];
		if (edges != null){
			for(Edge e : edges){
				adjacency[e.v1][e.v2] = 1;
				adjacency[e.v2][e.v1] = 1;
			}
		}
	}
	public int[] getVertices(){
		int[] res = new int[adjacency.length];
		for(int i = 0; i < res.length; i++)
			res[i] = i;
		return res;
	}
	public Edge[] getEdges(){
		HashSet<Edge> res = new HashSet<Edge>();
		for(int i = 0; i < adjacency.length; i++){
			for(int j = i+1; j < adjacency.length; j++){
				if (adjacency[i][j] == 1)
					res.add(new Edge(i,j));
			}
		}
		if (res.size() > 0)
			return res.toArray(new Edge[res.size()]);
		return null;
	}
	public boolean isAdjacent(int v1, int v2){
		return adjacency[v1][v2] == 1;
	}
	public int getDegree(int vertex){
		int result = 0;
		for(int i = 0; i < adjacency.length; i++)
			if (adjacency[vertex][i] == 1)
				result++;
		return result;
	}
	public int getSize(){
		return adjacency.length*adjacency.length*4;
	}
}
class GraphAdjList implements IGraph{
	int[] neighborIndex;
	int[] neighbors;
	public void setGraph(int[] vertices, Edge[] edges){
		neighborIndex = new int[vertices.length];
		if (edges == null)
			neighbors = null;
		else{
			neighbors = new int[edges.length*2];
			int curIndex = 0;
			for(int v : vertices){
				neighborIndex[v] = curIndex; // Isolierte am Ende bekommen einen Index außerhalb von neighbors
				for(Edge e : edges){
					if (e.v1 == v)
						neighbors[curIndex++] = e.v2;
					if (e.v2 == v)
						neighbors[curIndex++] = e.v1;
				}
			}
		}
	}
	public int[] getVertices(){
		int[] res = new int[neighborIndex.length];
		for(int i = 0; i < res.length; i++)
			res[i] = i;
		return res;
	}
	public Edge[] getEdges(){
		if (neighbors == null) return null;
		HashSet<Edge> res = new HashSet<Edge>();
		for(int i = 0; i < neighborIndex.length; i++){
			int until = (i < (neighborIndex.length-1)) ? neighborIndex[i+1]-1 : neighbors.length-1;
			for(int j = neighborIndex[i]; j <= until; j++){
				Edge e = new Edge(i,neighbors[j]);
				if (!res.contains(e))
					res.add(e);
			}
		}
		if (res.size() > 0)
			return res.toArray(new Edge[res.size()]);
		return null;
	}
	public boolean isAdjacent(int v1, int v2){
		if (neighbors == null) return false;
		int until = (v1 < (neighborIndex.length-1)) ? neighborIndex[v1+1]-1 : neighbors.length-1;
		for(int j = neighborIndex[v1]; j <= until; j++){
			if (neighbors[j] == v2)
				return true;
		}
		return false;
	}
	public int getDegree(int vertex){
		if (neighbors == null) return 0;
		int until = (vertex < (neighborIndex.length-1)) ? neighborIndex[vertex+1]-1 : neighbors.length-1;
		return until - neighborIndex[vertex]+1;
	}
	public int getSize(){
		return neighborIndex.length*4 + (neighbors == null ? 0 : neighbors.length*4);
	}
}

Hier kann die Implementation geprüft werden

int COUNT_VERTEX = 10;
int COUNT_EDGE = 15;
GraphAdjMat gam = new GraphAdjMat();
if (GraphGenerator.generate(gam,COUNT_VERTEX,COUNT_EDGE)){
	for(int v1 = 0; v1 < COUNT_VERTEX; v1++){
		graph.getDegree(v);
		for(int v2 = 0; v2 < COUNT_EDGE; v2++){
			graph.isAdjacent(v1,v2);
	}
}

Übung Grundbegriffe der Graphentheorie 1

Programmiertechnische Umsetzung von Graph-Strukturen

Aufgabe

Hilfestellung

Suche