Übung Grundbegriffe der Graphentheorie 1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
==Programmiertechnische Umsetzung von Graph-Strukturen==
*Gegeben ist folgendes <tt>IGraph</tt> Interface mit einer Hilfsklasse <tt>Edge</tt> zur einfacheren Behandlung von Kanten
<code id="562cd860778ad">
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
===Hilfestellung===
*Es gibt einen Graph-Generator 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="562cd8607791a">
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 beiden Klassen können hier im Programming Wiki implementiert werden
<code id="562cea9913471">
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);
}
}
</code>
*Hier kann die Implementation geprüft werden
<run id="562ced38cc076">
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);
}
}</run>