Ü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
<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
<code id="562cea9913501">
public class GraphChecker{
public static void main(String[] args){
GraphAdjMat gam = new GraphAdjMat();
GraphAdjList gal = new GraphAdjList();
for(int n = 250; n <= 5000; n+=250){
Check(gam,n,n*(n-1)/2 / 50);
}
for(int n = 250; n <= 5000; n+=250){
Check(gal,n,n*(n-1)/2 / 50);
}
}
static int COUNT_LOOP = 100; // Number of random input parameters are generated
static int TIME_FACTOR = 100; // Number of times a certain function call is repeated
static int COUNT_SAMPLES = 1; // Number of different graphs with the same vertex/edge count (only 1 with max edge count)
private static Random r = new Random();
static boolean Check(IGraph graph, int cntVertex, int cntEdge){
try{
long minDeg = Long.MAX_VALUE;
long maxDeg = 0;
long sumDeg = 0;
long minAdj = Long.MAX_VALUE;
long maxAdj = 0;
long sumAdj = 0;
for(int s = 0; s < COUNT_SAMPLES; s++){
if (!GraphGenerator.generate(graph,cntVertex,cntEdge))
System.out.println(graph.getClass().getSimpleName() + " generation failed!");
else{
for(int i = 0; i < COUNT_LOOP; i++){
// Measuring getDegree
int v = r.nextInt(cntVertex);
long start = System.nanoTime();
for(int t = 0; t < TIME_FACTOR; t++)
graph.getDegree(v);
long end = System.nanoTime();
long len = end - start;
minDeg = Math.min(minDeg,len);
maxDeg = Math.max(maxDeg,len);
sumDeg += len;
// Measuring isAdjacent
int i1 = r.nextInt(cntVertex);
int i2 = r.nextInt(cntVertex);
start = System.nanoTime();
for(int t = 0; t < TIME_FACTOR; t++)
graph.isAdjacent(i1,i2);
end = System.nanoTime();
len = end - start;
minAdj = Math.min(minAdj,len);
maxAdj = Math.max(maxAdj,len);
sumAdj += len;
}
}
}
System.out.println(graph.getClass().getSimpleName() + "\t" + cntVertex+"\t"+cntEdge+"\t"+graph.getSize()+"\t"+minDeg+"\t"+maxDeg+"\t"+(sumDeg/(COUNT_SAMPLES*COUNT_LOOP))+"\t"+minAdj+"\t"+maxAdj+"\t"+(sumAdj/(COUNT_SAMPLES*COUNT_LOOP)));
}
catch(Exception ex){
ex.printStackTrace();
return false;
}
return true;
}
}
</code>
<run id="562cea9913501">main</run>