# Graphen Bibliothek



## flashdog (24. Nov 2008)

Hallo,
gibt es eine Graphen Bibliothek die clique-detection algorithmen beinhaltet?

Viele Grüße


----------



## Wildcard (24. Nov 2008)

Draw2D/GEF


----------



## Marco13 (24. Nov 2008)

JGraphT: http://www.jgrapht.org/javadoc/org/jgrapht/alg/BronKerboschCliqueFinder.html


----------



## flashdog (1. Apr 2009)

Danke fuer den Link. Der Bron-Kerbosch-Algorithmus hoert sich gut an.

Wie baut man einen Graphen deren Knoten in 3D Raum liegen und die Kanten die Abstaende sind?


----------



## Marco13 (1. Apr 2009)

Was die Knoten sind, ist egal. Ansonten wäre das "nur" ein WeightedGraph (z.B. SimpleWeightedGraph...)


----------



## flashdog (3. Apr 2009)

Den SimpleWeightedGraph Klasse habe ich gefunden ( SimpleWeightedGraph (JGraphT : a free Java graph library) )

Ich verstehen noch nicht warum die Knoten egal sind. Leider verstehe ich auch nicht wie ich die Punkte von denen ich die Koordinaten (x,y,z) kenne in einen Graphen uebertragen kann und anschliessend den Bron-Kerbosch uebergeben kann?


----------



## Marco13 (4. Apr 2009)

Die Knoten sind "egal", weil es ja nur um die Kanten(längen) geht. Trotzdem macht es natürlich Sinn (bzw. ist am einfachsten und saubersten) auch gleich die passenden Knoten zu verwenden, da die Kantenlängen ja aus dem Abstand der Knoten berechnet werden.

Ich gehe jetzt davon aus, dass du sowas hast wie

```
class Vertex
{
    float x,y,z;
}
class Edge
{
    float length; 
    
    public Edge(Vertex v0, Vertex v1)
    {
        this.length = ... Abstand von v0 zu v1
    }

    float getLength() 
    { 
        return length;
    }
}
```

Dann müßte man das ganze eigentlich grob so aufziehen können: (Das ist ungetestet, und nur nach einem kurzen Blick auf die API-Doku hingeschrieben)

```
EdgeFactory<Vertex,Edge> ef = new EdgeFactory<Vertex,Edge>()
{
    public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
    {
        return new Edge(sourceVertex, targetVertex);
    }
};

WeightedGraph<Vertex, Edge> g = new SimpleWeightedGraph<Vertex,Edge>(ef)
{
    // Bin gerade nicht sicher, ob die wirklich so überschrieben werden muss ....????
    @Override
    public double getEdgeWeight(Edge e)
    {
        return e.getLength();
    }
};

// Alle Vertices hinzufügen
g.addVertex(v0);
g.addVertex(v1);
...
g.addVertex(vn);

// Alle Kanten hinzufügen
g.addEdge(v0, v1);
g.addEdge(v0, v2);
...
g.addEdge(vi, vj);


// Und los...:

BronKerboschCliqueFinder<Vertex, Edge> cf = new BronKerboschCliqueFinder<Vertex, Edge>(g);
Collection<Set<Vertex>> cliques = cf.getAllMaximalCliques() 
for (Set<Vertex> clique : cliques)
{
    System.out.println("Clique: "+clique);
}
```

Wenn's nicht klappt, sag' bescheid (und stell' möglichst präzisere Fragen als die letzte.....)


----------



## flashdog (5. Apr 2009)

Danke für den Code, aber soweit bin ich noch nicht um ihn benutzen zu können.

Im Internet habe ich diese Anleitung gefunden:
	
	
	
	





```
Step 1:
Form the Correspondence Graph („Assiociation graph“,
„Product graph“) from the two graphs.

Step 2:
Search for Cliques (= completely connected subgraph, which is
not contained in any other completely connected subgraph) in
the Correpondence Graph by “backtracking tree search” .
```

Wenn ich dein Code richtig verstehe ist EdgeFactory das gleiche wie ein Correspondence Graph.

Mein Problem ist wie ich aus den folgenden zwei Dateien: 
	
	
	
	





```
-12.285   2.063   9.794
 -2.337   6.744  -3.154
 -7.488  -5.187  -0.625
 30.019  -4.321  -7.372
 -2.943  -0.511   1.767
  5.784  -0.667  -3.078
  4.206  -0.400  -2.165
 16.062 -17.972  -3.801
  2.597   1.580 -16.423
 -1.667   0.000   0.000
  2.937   0.199  -1.095
 -6.073  16.212 -12.253
  1.226  -0.922 -11.367
```


```
36.560  44.908   5.262
 22.714  45.752  15.887
 11.093  34.779  20.840
 -0.186  21.166  17.398
  0.545  23.430   6.821
  3.705  25.429   4.163
 15.788   9.537   2.953
 11.178  22.344  11.096
 18.239  44.079   7.063
 22.351  44.977  -6.660
 13.065  31.245   7.933
 23.320  24.842   1.224
 20.988  34.756   8.729
 26.812  24.470  14.967
 32.623  23.473  12.960
 25.486  36.045  11.442
 26.015  34.055  -5.984
 27.225  25.032   5.988
 16.709  30.446  10.922
 18.333  20.597  -8.511
```

welche jeweils ein Graph repräsentieren sollen, diese Graphen bauen kann die man anschließend an EdgeFactory übergeben kann?


----------



## Marco13 (5. Apr 2009)

Unabhängig von deinem konkreten Problem (der Code bezog sich nur darauf, wie man für einen Graphen diesen Algorithmus anwendet - was du vorher machen musst, um deine(n) Graphen in die gewüschte Form zu bringen, musst du wissen) :

Die Datei zeilenweise einlesen, aus jeder Zeile einen Vertex machen, und die so einfügen, wie oben beschrieben...


----------



## flashdog (7. Apr 2009)

Dake für dein Tipp. Habe angefangen zu programmieren und bekomme vollgenden Fehler:
	
	
	
	





```
Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	The method add(Vertex) in the type ArrayList<Vertex> is not applicable for the arguments (Edge)

	at BronKerbosh01.creatEdges(BronKerbosh01.java:35)
	at BronKerbosh01.main(BronKerbosh01.java:47)
```

Der Code sieht wie folgt aus:
	
	
	
	





```
class Vertex {
	int no;
	float x,y,z;
}
```


```
class Edge {
	float length; 
	Vertex v0, v1;

	public Edge(Vertex v0, Vertex v1) {
		this.v0 = v0;
		this.v1 = v1;
		this.length = getLength(); //Abstand von v0 zu v1
	}

	float getLength() { 
		float temp = ((v0.x - v1.x) * (v0.x - v1.x)) + ((v0.y - v1.y) * (v0.y - v1.y))
				+ ((v0.z - v1.z) * (v0.z - v1.z)); 
		float length = (float) Math.sqrt(temp);
		return length;
	}
}
```


```
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
import java.util.Set;
import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

public class BronKerbosh01 {

	/**
	 * @param args
	 * @throws IOException 
	 */
	static void creatVertex(String fileName, ArrayList<Vertex> vertexList) throws IOException{
		Scanner diskScanner = new Scanner(new File(fileName));
		while (diskScanner.hasNext()) {
			Vertex vertex = new Vertex();
			vertex.no = diskScanner.nextInt();
			vertex.x = diskScanner.nextFloat();
			vertex.y = diskScanner.nextFloat();
			vertex.z = diskScanner.nextFloat();
			vertexList.add(vertex);
		}
	}	
	
	static void creatEdges(ArrayList<Vertex> vertexList, ArrayList<Vertex> edgesList){
		for (int i = 0; i < vertexList.size(); i++){
			if (i <  vertexList.size()) break;
			else {
				Edge edge = new Edge(vertexList.get(i), vertexList.get(i+1));
				edgesList.add(edge);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
//		String file1 = "c1.txt";
		String file1 = "c2.txt";
		ArrayList<Vertex> vertexes1 = new ArrayList<Vertex>();
		creatVertex(file1, vertexes1);
		
		ArrayList<Vertex> edges1 = new ArrayList<Vertex>();
		creatEdges(vertexes1, edges1);
		for (int i = 0; i < vertexes1.size(); i++){
			System.out.println(vertexes1.get(i).no + " " + vertexes1.get(i).x + " " + 
					vertexes1.get(i).y + " " + vertexes1.get(i).z);
		}
		
/*		EdgeFactory<Vertex,Edge> ef = new EdgeFactory<Vertex,Edge>()
		{
		    public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
		    {
		        return new Edge(sourceVertex, targetVertex);
		    }
		};

		WeightedGraph<Vertex, Edge> g = new SimpleWeightedGraph<Vertex,Edge>(ef)
		{
		    // Bin gerade nicht sicher, ob die wirklich so überschrieben werden muss ....????
		    @Override
		    public double getEdgeWeight(Edge e)
		    {
		        return e.getLength();
		    }
		};

		// Alle Vertices hinzufügen
		g.addVertex(v0);
		g.addVertex(v1);
		...
		g.addVertex(vn);

		// Alle Kanten hinzufügen
		g.addEdge(v0, v1);
		g.addEdge(v0, v2);
		...
		g.addEdge(vi, vj);


		// Und los...:

		BronKerboschCliqueFinder<Vertex, Edge> cf = new BronKerboschCliqueFinder<Vertex, Edge>(g);
		Collection<Set<Vertex>> cliques = cf.getAllMaximalCliques(); 
		for (Set<Vertex> clique : cliques)
		{
		    System.out.println("Clique: "+clique);
		}*/
	}	
}
```

Wie bekomme ich diesen Fehler weg und bin ich auf den richtigen weg um das Programm zum laufen zu bekommen?


----------



## Marco13 (7. Apr 2009)

Er sagt ja ganz klar, dass in Zeile 35 was nicht stimmt.

... ArrayList<Vertex> edgesList)
...
edgesList.add(edge); *//Zeile 35*

Könnte man finden, aber gut: edgesList sollte eine List<Edge> sein, und keine List<Vertex>....




```
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
import java.util.*;
import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class Vertex {
    int no;
    float x,y,z;
    
    public Vertex(float x, float y, float z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    
    public String toString()
    {
        return "("+x+","+y+","+z+")";
    }
}

class Edge 
{
    float length; 
    Vertex v0, v1;

    public Edge(Vertex v0, Vertex v1) {
        this.v0 = v0;
        this.v1 = v1;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}

public class BronKerbosch01 
{
    public static void main(String[] args) throws IOException {
        
        EdgeFactory<Vertex,Edge> ef = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g = new SimpleWeightedGraph<Vertex,Edge>(ef)
        {
            // Bin gerade nicht sicher, ob die wirklich so überschrieben werden muss ....????
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g.addVertex(vertex);
            
        }
        
        Random random = new Random();
        List<Vertex> vertices = new ArrayList<Vertex>(g.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random.nextInt(vertices.size()); 
            int b = random.nextInt(vertices.size());
            if (a != b)
            {
                g.addEdge(vertices.get(a), vertices.get(b));
            }
        }
        
        BronKerboschCliqueFinder<Vertex, Edge> cf = new BronKerboschCliqueFinder<Vertex, Edge>(g);
        Collection<Set<Vertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<Vertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
}
```


----------



## flashdog (8. Apr 2009)

Danke, habe ich total übersehen. Ich werden dein Vorschlag gleich ausprobien.


----------



## schalentier (8. Apr 2009)

```
Arrays.toString( clique.toArray() );
```

oder die Ausgabe am Ende selbst machen (foreach( Vertex v : clique ) { .. })


----------



## Civilazi (8. Apr 2009)

Du solltest die toString() Methode von Vertex überschreiben, so wie oben schon von Marco gemacht. Dann steht da auf jeden Fall schonmal was Sinnvolles.


----------



## flashdog (9. Apr 2009)

Danke es funktioniert, aber wenn ich das richtig verstehe wird nur ein Graph erzeugt und dem Bron-Kerbosch übergeben, aber wie übergebt man zwei Graphen an Bron-Kerbosch so das ich erfahren kann welche Vertexe der beiden Graphen zusammen gehören?


----------



## Marco13 (9. Apr 2009)

Wenn er bei zwei Graphen eine Clique finden würde, die vertices aus beiden Graphen enthält, wäre irgendwas kaputt..... Entweder, es ist nur EIN Graph .. oder eben nicht...


----------



## flashdog (10. Apr 2009)

Marco du hast recht und es mir eingefallen, wenn man zwei Graphen hat muss man aus denen ein Association Graph: ( Modular product of graphs - Wikipedia, the free encyclopedia ) erzeugen.

Aber leider habe ich kein Association Graph in JGrapht gefunden. Weisst du vielleicht wie man so was baut?


----------



## Marco13 (10. Apr 2009)

Kann gut sein, dass es sowas nicht fertig gibt. Aber der Algorithmus steht ja (in Worten) auf der verlinkten Seite. Wieder Pseudocode

```
class DoubleVertex 
{
    Vertex v0, v1
}

Graph<Vertex, Edge> g0 = ... erster Eingabe-Graph
Graph<Vertex, Edge> g1 = ... zweiter Eingabe-Graph

// Alle vertices des Modular Products erstellen
Graph<DoubleVertex, SomeEdgeType> graph = ... irgendein passender graph-Typ
for (Vertex v0 : g0.vertexSet())
{
    for (Vertex v1 : g1.vertexSet())
    {
        graph.addVertex(new DoubleVertex(v0,v1));
    }
}

// Alle Kanten einfügen
List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
for (int i=0; i<list.size(); i++)
{
    for (int j=i+1; j<list.size(); j++)
    {
        DoubleVertex dv0 = list.get(i);
        DoubleVertex dv1 = list.get(j);
        
        if (Bedingung für Kanten ist wie auf der verlinkten Seite beschrieben erfüllt)
        { 
            graph.addEdge(dv0, dv1);
        }       

    }
}

// Mach' mir den Kerbosch ...
doit(graph);
```

So in etwa...


----------



## flashdog (12. Apr 2009)

Danke für den Code. Habe es in den vorherigen Code eingefügt (siehe unten).
Die Bedingung für ein Association graph:
	
	
	
	





```
any two vertices (u, v) and (u' , v' ) are adjacent in the modular product of G and H if and only if 
u is adjacent with u' and v is adjacent with v'
```
Diese Bedingung erfüllt neighborsOf oder neighborListOf ( NeighborIndex (JGraphT : a free Java graph library) ), leider was ich nicht genau welche für den unteren Code besser passt und wie man diese verwendet.

Mein zweites Problem ist folgendes:
	
	
	
	





```
"main" java.lang.Error: Unresolved compilation problem: 
	The constructor BronKerboschCliqueFinder<Vertex,Edge>(WeightedGraph<DoubleVertex,DoubleEdge>) is undefined

	at BronKerbosh02.main(BronKerbosh02.java:207)
```


```
import java.io.IOException;
import java.util.*;
import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class DoubleVertex {
	Vertex v0, v1;
	public int x;
	public int y;
	public int z;
	
  public DoubleVertex(Vertex v0, Vertex v1) {
		this.v0 = v0;
		this.v1 = v1;
	}

}

class DoubleEdge 
{
    float length; 
    DoubleVertex v0;
		DoubleVertex v1;

		public DoubleEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex) {
        this.v0 = sourceVertex;
        this.v1 = targetVertex;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}
class Vertex {
    int no;
    float x,y,z;
    
    public Vertex(float x, float y, float z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    
    public String toString()
    {
        return "("+x+","+y+","+z+")";
    }
}

class Edge 
{
    float length; 
    Vertex v0, v1;

    public Edge(Vertex v0, Vertex v1) {
        this.v0 = v0;
        this.v1 = v1;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}


public class BronKerbosh02 
{
    public static void main(String[] args) throws IOException {
        
        EdgeFactory<Vertex,Edge> ef0 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g0 = new SimpleWeightedGraph<Vertex,Edge>(ef0)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g0.addVertex(vertex);
            
        }
        
        Random random = new Random();
        List<Vertex> vertices0 = new ArrayList<Vertex>(g0.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random.nextInt(vertices0.size()); 
            int b = random.nextInt(vertices0.size());
            if (a != b)
            {
                g0.addEdge(vertices0.get(a), vertices0.get(b));
            }
        }
        
        //Second Graph
        EdgeFactory<Vertex,Edge> ef1 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g1 = new SimpleWeightedGraph<Vertex,Edge>(ef1)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g1.addVertex(vertex);
            
        }
        
        Random random2 = new Random();
        List<Vertex> vertices1 = new ArrayList<Vertex>(g1.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random2.nextInt(vertices1.size()); 
            int b = random2.nextInt(vertices1.size());
            if (a != b)
            {
                g1.addEdge(vertices1.get(a), vertices1.get(b));
            }
        }
        
        
     // Alle vertices des Modular Products erstellen
        EdgeFactory<DoubleVertex,DoubleEdge> Pef = new EdgeFactory<DoubleVertex,DoubleEdge>()
        {
            public DoubleEdge createEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex)
            {
                return new DoubleEdge(sourceVertex, targetVertex);
            }
        };        
        
        WeightedGraph<DoubleVertex, DoubleEdge> graph = new SimpleWeightedGraph<DoubleVertex,DoubleEdge>(Pef)
        {
          @Override
          public double getEdgeWeight(DoubleEdge e)
          {
              return e.getLength();
          }
      };
        for (Vertex v0 : g0.vertexSet())
        {
            for (Vertex v1 : g0.vertexSet())
            {
                graph.addVertex(new DoubleVertex(v0,v1));
            }
        }

        // Alle Kanten einfügen
        List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
        for (int i=0; i<list.size(); i++)
        {
            for (int j=i+1; j<list.size(); j++)
            {
                DoubleVertex dv0 = list.get(i);
                DoubleVertex dv1 = list.get(j);
                
                if (Bedingung für Kanten ist wie auf der verlinkten Seite beschrieben erfüllt)
                { 
                    graph.addEdge(dv0, dv1);
                }       

            }
        }
 
        BronKerboschCliqueFinder<Vertex, Edge> cf = new BronKerboschCliqueFinder<Vertex, Edge>(graph);
        Collection<Set<Vertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<Vertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
}
```


----------



## Marco13 (12. Apr 2009)

Wenn du auf DoubleEdge und DoubleVertex Clicquen finden willst, musst du das auch sagen
BronKerboschCliqueFinder<Vertex,Edge>(WeightedGraph<DoubleVertex,DoubleEdge>)
->
BronKerboschCliqueFinder<DoubleVertex,DoubleEdge>(WeightedGraph<DoubleVertex,DoubleEdge>)


----------



## flashdog (13. Apr 2009)

Danke werde es gleich ausprobieren.


----------



## flashdog (13. Apr 2009)

Danke für dein Lösungsvorschlag. Habe es in den vorherigen Code eingefügt (siehe unten).

Aber mir macht noch die Bedingung für ein Association graph problem:
	
	
	
	





```
any two vertices (u, v) and (u' , v' ) are adjacent in the modular product of G and H if and only if 
u is adjacent with u' and v is adjacent with v'
```
Diese Bedingung erfüllt neighborsOf oder neighborListOf ( NeighborIndex (JGraphT : a free Java graph library) ), leider was ich nicht genau welche für den unteren Code besser passt und wie man diese verwendet.

```
import java.io.IOException;
import java.util.*;

import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class DoubleVertex {
	Vertex v0, v1;
	public int x;
	public int y;
	public int z;
	
  public DoubleVertex(Vertex v0, Vertex v1) {
		this.v0 = v0;
		this.v1 = v1;
	}

}

class DoubleEdge 
{
    float length; 
    DoubleVertex v0;
		DoubleVertex v1;

		public DoubleEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex) {
        this.v0 = sourceVertex;
        this.v1 = targetVertex;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}
class Vertex {
    int no;
    float x,y,z;
    
    public Vertex(float x, float y, float z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    
    public String toString()
    {
        return "("+x+","+y+","+z+")";
    }
}

class Edge 
{
    float length; 
    Vertex v0, v1;

    public Edge(Vertex v0, Vertex v1) {
        this.v0 = v0;
        this.v1 = v1;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}


public class BronKerbosh02 
{
    public static void main(String[] args) throws IOException {
        
        EdgeFactory<Vertex,Edge> ef0 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g0 = new SimpleWeightedGraph<Vertex,Edge>(ef0)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g0.addVertex(vertex);
            
        }
        
        Random random = new Random();
        List<Vertex> vertices0 = new ArrayList<Vertex>(g0.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random.nextInt(vertices0.size()); 
            int b = random.nextInt(vertices0.size());
            if (a != b)
            {
                g0.addEdge(vertices0.get(a), vertices0.get(b));
            }
        }
        
        //Second Graph
        EdgeFactory<Vertex,Edge> ef1 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g1 = new SimpleWeightedGraph<Vertex,Edge>(ef1)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g1.addVertex(vertex);
            
        }
        
        Random random2 = new Random();
        List<Vertex> vertices1 = new ArrayList<Vertex>(g1.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random2.nextInt(vertices1.size()); 
            int b = random2.nextInt(vertices1.size());
            if (a != b)
            {
                g1.addEdge(vertices1.get(a), vertices1.get(b));
            }
        }
        
        
     // Alle vertices des Modular Products erstellen
        EdgeFactory<DoubleVertex,DoubleEdge> Pef = new EdgeFactory<DoubleVertex,DoubleEdge>()
        {
            public DoubleEdge createEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex)
            {
                return new DoubleEdge(sourceVertex, targetVertex);
            }
        };        
        
        WeightedGraph<DoubleVertex, DoubleEdge> graph = new SimpleWeightedGraph<DoubleVertex,DoubleEdge>(Pef)
        {
          @Override
          public double getEdgeWeight(DoubleEdge e)
          {
              return e.getLength();
          }
      };
        for (Vertex v0 : g0.vertexSet())
        {
            for (Vertex v1 : g0.vertexSet())
            {
                graph.addVertex(new DoubleVertex(v0,v1));
            }
        }

        // Alle Kanten einfügen
        List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
        for (int i=0; i<list.size(); i++)
        {
            for (int j=i+1; j<list.size(); j++)
            {
                DoubleVertex dv0 = list.get(i);
                DoubleVertex dv1 = list.get(j);
                
//                if (Bedingung für Kanten ist wie auf der verlinkten Seite beschrieben erfüllt)
//                { 
//                    graph.addEdge(dv0, dv1);
//                }       

            }
        }
 
        BronKerboschCliqueFinder<DoubleVertex, DoubleEdge> cf = 
        	new BronKerboschCliqueFinder<DoubleVertex,DoubleEdge>(graph);
        
        Collection<Set<DoubleVertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<DoubleVertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
}
```


----------



## Marco13 (13. Apr 2009)

Ob zwei vertices in einem Graphen adjazen sind, kann man mit Graph (JGraphT : a free Java graph library) herausfinden.


----------



## flashdog (14. Apr 2009)

Danke, für den Tipp, aber leider bekomme ich diese Fehlermeldung:
	
	
	
	





```
Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	The method containsEdge(DoubleVertex, DoubleVertex) is undefined for the type BronKerbosh02

	at BronKerbosh02.main(BronKerbosh02.java:200)
```
Ich habe verschiedenes ausprobiert, aber leider bekommen ich den Fehler nicht weg.

```
import java.io.IOException;
import java.util.*;

import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class DoubleVertex {
	Vertex v0, v1;
	public int x;
	public int y;
	public int z;
	
  public DoubleVertex(Vertex v0, Vertex v1) {
		this.v0 = v0;
		this.v1 = v1;
	}

}

class DoubleEdge 
{
    float length; 
    DoubleVertex v0;
		DoubleVertex v1;

		public DoubleEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex) {
        this.v0 = sourceVertex;
        this.v1 = targetVertex;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}
class Vertex {
    int no;
    float x,y,z;
    
    public Vertex(float x, float y, float z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    
    public String toString()
    {
        return "("+x+","+y+","+z+")";
    }
}

class Edge 
{
    float length; 
    Vertex v0, v1;

    public Edge(Vertex v0, Vertex v1) {
        this.v0 = v0;
        this.v1 = v1;
        this.length = computeLength(); //Abstand von v0 zu v1
    }

    private float computeLength() 
    {
        float dx = v0.x - v1.x;
        float dy = v0.y - v1.y;
        float dz = v0.z - v1.z;
        return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
    }
    float getLength() 
    {
        return length;
    }
}


public class BronKerbosh02 
{
    public static void main(String[] args) throws IOException {
        
        EdgeFactory<Vertex,Edge> ef0 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g0 = new SimpleWeightedGraph<Vertex,Edge>(ef0)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g0.addVertex(vertex);
            
        }
        
        Random random = new Random();
        List<Vertex> vertices0 = new ArrayList<Vertex>(g0.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random.nextInt(vertices0.size()); 
            int b = random.nextInt(vertices0.size());
            if (a != b)
            {
                g0.addEdge(vertices0.get(a), vertices0.get(b));
            }
        }
        
        //Second Graph
        EdgeFactory<Vertex,Edge> ef1 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g1 = new SimpleWeightedGraph<Vertex,Edge>(ef1)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
        for (int i=0; i<10; i++)
        {
            Vertex vertex = new Vertex((float)Math.random(),(float)Math.random(),(float)Math.random());
            g1.addVertex(vertex);
            
        }
        
        Random random2 = new Random();
        List<Vertex> vertices1 = new ArrayList<Vertex>(g1.vertexSet());
        for (int i=0; i<50; i++)
        {
            int a = random2.nextInt(vertices1.size()); 
            int b = random2.nextInt(vertices1.size());
            if (a != b)
            {
                g1.addEdge(vertices1.get(a), vertices1.get(b));
            }
        }
        
        
     // Alle vertices des Modular Products erstellen
        EdgeFactory<DoubleVertex,DoubleEdge> Pef = new EdgeFactory<DoubleVertex,DoubleEdge>()
        {
            public DoubleEdge createEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex)
            {
                return new DoubleEdge(sourceVertex, targetVertex);
            }
        };        
        
        WeightedGraph<DoubleVertex, DoubleEdge> graph = new SimpleWeightedGraph<DoubleVertex,DoubleEdge>(Pef)
        {
          @Override
          public double getEdgeWeight(DoubleEdge e)
          {
              return e.getLength();
          }
      };
        for (Vertex v0 : g0.vertexSet())
        {
            for (Vertex v1 : g0.vertexSet())
            {
                graph.addVertex(new DoubleVertex(v0,v1));
            }
        }

        // Alle Kanten einfuegen
        List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
        for (int i=0; i<list.size(); i++)
        {
            for (int j=i+1; j<list.size(); j++)
            {
                DoubleVertex dv0 = list.get(i);
                DoubleVertex dv1 = list.get(j);
                
                if (containsEdge(dv0,dv1))
                { 
                    graph.addEdge(dv0, dv1);
                }       

            }
        }
 
        BronKerboschCliqueFinder<DoubleVertex, DoubleEdge> cf = 
        	new BronKerboschCliqueFinder<DoubleVertex,DoubleEdge>(graph);
        
        Collection<Set<DoubleVertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<DoubleVertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
}
```
Wie bekommt man diesen Fehler weg?


----------



## Marco13 (16. Apr 2009)

:autsch: Hm. Die Bedingung dafür, dass in diesen Association Graph eine Kante eingefügt wird, ist (im wesentlichen, schau das nochtmal genau nach) ja sowas wie dass zwischen den "Unter-Vertices" in ein EINGABEgraphen Kanten existieren (oder so) 

Kleiner wink: Wenn man da nur "containsEdge" hinschreiben müßte, hätte ich ja wohl einen Teufel getan und da _"Bedingung für Kanten ist wie auf der verlinkten Seite beschrieben erfüllt"_ hingeschrieben. Ein bißchen denken solltest du auch noch  

Aber gut. Die Bedingung würde dann GROB so ÄHNLICH aussehen wie sowas

```
Vertex v00 = doubleVertex0.getFirstVertex();
Vertex v01 = doubleVertex0.getSecondVertex();
Vertex v10 = doubleVertex1.getFirstVertex();
Vertex v11 = doubleVertex1.getSecondVertex();
if (g0.containsEdge(v00, v01) || g1.containsEdge(v10, v11))
{
    graph.addEdge(dv0, dv1);
}
```
aber schau nochmal genau nach, wie die Bedinung GENAU sein muss!


----------



## flashdog (1. Jun 2009)

Leider habe ich es nicht hin bekommen, so habe im Netz gesucht und habe etwas ähnliches gefunden ( http://www.math.ucsd.edu/~fan/graphdraw/llu/graphproduct/Graph.java ), aber leider weiss ich es nicht wie man verbindet.


```
public static Graph cartesianProduct(Graph g1, Graph g2){
        Graph g=new Graph();
        int x,y;
        for(int i=0;i<g1.getN();i++){
            for(int j=0;j<g2.getN();j++){
                x=(((Vertex) g1.vertices.get(i)).x
                  +((Vertex) g2.vertices.get(j)).x);
                y=(((Vertex) g1.vertices.get(i)).y
                  +((Vertex) g2.vertices.get(j)).y);
                g.add(new Vertex(x,y));
            }
        }
        
        for(int i=0;i<g1.getN();i++){
            for(int k=0;k<g2.getE();k++){
                Edge e = (Edge) g2.edges.get(k);
                x=g2.vertices.indexOf(e.u);
                y=g2.vertices.indexOf(e.v);
               // System.out.println("x="+x+" y="+y+ "i="+i);                
                Edge edge=new Edge(g.getVertex(i*g2.getN()+x), 
                               g.getVertex(i*g2.getN()+y));
                edge.color=e.color;
                g.add(edge);
            }
        }
               
        for(int i=0;i<g2.getN();i++){
            for(int k=0;k<g1.getE();k++){
                Edge e = (Edge) g1.edges.get(k);
                x=g1.vertices.indexOf(e.u);
                y=g1.vertices.indexOf(e.v);
                Edge edge=new Edge(g.getVertex(x*g2.getN()+i), 
                               g.getVertex(y*g2.getN()+i));
                edge.color=e.color;
                g.add(edge);
            }
        }
        return g;
    }
```

Wie könnte man alles zusammen verbinden?


----------



## flashdog (28. Jul 2009)

Eine Kante soll nur in den Association Graph eingefügt werden wenn es eine Kante in Graph 1 (a.txt) und Graph 2 (b.txt) gibt die in beiden Graphen die selbe länge (euklidische Distanz) haben.

Ich habe den Code modifiziert, aber leider bekomme ich es nicht hin:
	
	
	
	





```
import java.io.File;
import java.io.IOException;
import java.util.*;
import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class Vertex {
  int no;
  float x,y,z;
  
  public Vertex(int no, float x, float y, float z)
  {
  		this.no = no;
      this.x = x;
      this.y = y;
      this.z = z;
  }
  
  public String toString()
  {
      return "("+no+": "+x+","+y+","+z+")";
  }
}

class Edge 
{
  float length; 
  Vertex v0, v1;

  public Edge(Vertex v0, Vertex v1) {
      this.v0 = v0;
      this.v1 = v1;
      this.length = computeLength(); //Abstand von v0 zu v1
  }

  private float computeLength() 
  {
      float dx = v0.x - v1.x;
      float dy = v0.y - v1.y;
      float dz = v0.z - v1.z;
      return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
  }
  float getLength() 
  {
      return length;
  }
}

class DoubleVertex {
	Vertex v0, v1;
	
  public DoubleVertex(Vertex v0, Vertex v1) {
		this.v0 = v0;
		this.v1 = v1;
	}
  public String toString()
  {
      return "("+v0.no+","+v1.no+")";
  }
}

class DoubleEdge 
{
    float length; 
    DoubleVertex v0;
		DoubleVertex v1;

		public DoubleEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex) {
        this.v0 = sourceVertex;
        this.v1 = targetVertex;
    }
}

public class BronKerbosch 
{
    public static void main(String[] args) throws IOException {
      String fileNameTarget = "a.txt";
      String fileNameTemplate = "b.txt";
        EdgeFactory<Vertex,Edge> ef0 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g0 = new SimpleWeightedGraph<Vertex,Edge>(ef0)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
    		Scanner diskScanner = new Scanner(new File(fileNameTarget));
    		while (diskScanner.hasNext()) {
    			Vertex vertex = new Vertex(diskScanner.nextInt(), diskScanner.nextFloat(),diskScanner.nextFloat(),diskScanner.nextFloat());
    			g0.addVertex(vertex);
    		}
    		System.out.println(g0);
    		
        
        List<Vertex> vertices0 = new ArrayList<Vertex>(g0.vertexSet());
        
        //everything is conected to everything in graph 1
        for (int i = 0; i < vertices0.size(); i++){
        	for (int j = 0; j < vertices0.size(); j++){
        		if (i != j) 
        			g0.addEdge(vertices0.get(i), vertices0.get(j));
        	}
        }
        System.out.println(vertices0.size());
        
        //Second Graph
        EdgeFactory<Vertex,Edge> ef1 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g1 = new SimpleWeightedGraph<Vertex,Edge>(ef1)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
    		Scanner diskScanner2 = new Scanner(new File(fileNameTemplate));
    		while (diskScanner2.hasNext()) {
    			Vertex vertex = new Vertex(diskScanner2.nextInt(), diskScanner2.nextFloat(),diskScanner2.nextFloat(),diskScanner2.nextFloat());
    			g1.addVertex(vertex);
    		}

    			System.out.println(g1);

    		
        
        List<Vertex> vertices1 = new ArrayList<Vertex>(g1.vertexSet());
        
        //everything is conected to everything in graph 2
        for (int i = 0; i < vertices1.size(); i++){
        	for (int j = 0; j < vertices1.size(); j++){
        		if (i != j) 
        			g1.addEdge(vertices1.get(i), vertices1.get(j));
        	}
        }
        System.out.println(vertices1.size());
       
        
     // Alle vertices des Product graph erstellen
        EdgeFactory<DoubleVertex,DoubleEdge> Pef = new EdgeFactory<DoubleVertex,DoubleEdge>()
        {
            public DoubleEdge createEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex)
            {
                return new DoubleEdge(sourceVertex, targetVertex);
            }
        };        
        
        WeightedGraph<DoubleVertex, DoubleEdge> graph = new SimpleWeightedGraph<DoubleVertex,DoubleEdge>(Pef)
        {
//          @Override
//          public double getEdgeWeight(DoubleEdge e)
//          {
//              return e.getLength(); 
//          }
      	};
        for (Vertex v0 : g0.vertexSet())
        {
            for (Vertex v1 : g1.vertexSet())
            {
      				//Here must come vertex Similitary
                graph.addVertex(new DoubleVertex(v0,v1));
            }
        }

        // Alle Kanten einfügen
        List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
        for (int i=0; i<list.size(); i++)
        {
        	for (int j=i+1; j<list.size(); j++)
        	{
//        		if(i !=j){
        			DoubleVertex dv0 = list.get(i);
        			DoubleVertex dv1 = list.get(j);

        			//Calculate distance in DoubleVertex0 
        			double dv0x = dv0.v0.x - dv0.v1.x;
        			double dv0y = dv0.v0.y - dv0.v1.y;
        			double dv0z = dv0.v0.z - dv0.v1.z;
        			double dv0Dist = Math.sqrt(dv0x*dv0x+dv0y*dv0y+dv0z*dv0z);

        			//Calculate distance in DoubleVertex1 
        			double dv1x = dv1.v0.x - dv1.v1.x;
        			double dv1y = dv1.v0.y - dv1.v1.y;
        			double dv1z = dv1.v0.z - dv1.v1.z;
        			double dv1Dist = Math.sqrt(dv1x*dv1x+dv1y*dv1y+dv1z*dv1z);

        			System.out.print(dv0.v0.no + " " + "dv0Dist: " + dv0Dist + " " + 
        					dv1.v1.no + " " + " dv1Dist: " + dv1Dist);
        			
        			if(dv0Dist == dv1Dist) {
        				System.out.println(" yes");
        				graph.addEdge(dv0, dv1);
        			}
        			else System.out.println(" no");
        		}
//        	}
        }
   
        BronKerboschCliqueFinder<DoubleVertex, DoubleEdge> cf = 
        	new BronKerboschCliqueFinder<DoubleVertex,DoubleEdge>(graph);
        Collection<Set<DoubleVertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<DoubleVertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
}
```
*UPDATE:*

```
//a.txt
 6     -22.407  55.690  17.682
 7     -21.695  47.136  11.355
 8      -6.266  53.544   6.447
 9     -17.585  49.348   6.859
10     -22.885  58.190   6.584
11     -21.368  65.753   4.449
13     -20.703  75.341   2.991

//b.txt
 1        14.566  55.361  10.273
 2        26.928  51.739  16.185
 3        13.379  55.253   7.685
 4        18.626  45.916   1.163
 5        17.509  48.320  16.029
 6        27.712  54.998   3.054
 7        21.317  49.180  -3.188
 8        31.618  35.732   0.842
 9        25.337  44.362  -4.810
10        32.765  51.323  -6.464
11        40.767  51.288  -6.602
12        51.074  37.488 -15.101
13        50.356  52.858  -6.302
14        59.300  60.079  -4.904
15        41.650  62.155  -9.739
16        47.626  61.260 -17.202
17        55.686  61.356 -11.098
```

Wie fügt man Kanten die in Beiden Graphen die selbe länge (Euclidische Distanz) haben in den Association Graph ein?


----------



## Marco13 (28. Jul 2009)

Habe es jetzt nicht getestet, so beim drüberschauen KÖNNTE das stimmen, aber die Abfrage
if (dv0Dist == dv1Dist) ...
wird mit Sicherheit in die Hose gehen: Dort werden double-Werte verglichen, und die unterscheiden sich praktisch immer durch winzigSTe Rundungsfehler. Die Abfrage müßte zumindest lauten
if (Math.abs(dv0Dist-dv1Dist)<1e-4) { ... }
oder so. Um Zweifelsfall solltest du dir die Längen aber auch mal mit System.out.println ausgeben lassen. Vielleicht SIND sie ja einfach nicht gleich


----------



## flashdog (28. Jul 2009)

```
if (Math.abs(dv0Dist-dv1Dist)<1e-4) { ... }
```
 hat leider nicht geholfen. Z.B. 37.19787036251791 taucht in beiden Graphen auf wird aber leider nicht erkannt da die Kanten nicht mit einander verglichen werden. Die Ausgabe habe ich angehängt.

Was mache ich falsch?


----------



## Marco13 (28. Jul 2009)

Hab' gerade nicht so viel Zeit, aber... die Kantenlängen der einzelnen Graphen spielen da im Moment keine Rolle: Es werden DoubleVertices erstellt, die jeweils einen Vertex aus dem einen und einen Vertex aus dem anderen Graphen enthalten. Kanten würden nur eingefügt, wenn zwei dieser DoubleVertices zufällig zwei gleich weit voneinander entfernte Vertices (aus zwei verschiedenen Graphen!) enhalten würden...


----------



## flashdog (29. Jul 2009)

Danke für deine Antwort. Alle DoubleVertices werden hier erstellt:

```
//Vertex einfügen
      	for (Vertex v0 : g0.vertexSet())
      	{
      		for (Vertex v1 : g1.vertexSet())
      		{
      			graph.addVertex(new DoubleVertex(v0,v1));
      		}
      	}
```



> Kanten würden nur eingefügt, wenn zwei dieser DoubleVertices zufällig zwei gleich weit voneinander entfernte Vertices (aus zwei verschiedenen Graphen!) enhalten würden...


Dies habe ich versucht wie folgt zu implementieren, aber ich hab kein Zugriff auf die Kantenlängen in der Edge Klasse bekommen und habe diese noch mal berechnet:

```
// Kanten einfügen
      	List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
      	for (int i=0; i<list.size(); i++)
      	{
      		for (int j=i+1; j<list.size(); j++)
      		{
      			DoubleVertex dv0 = list.get(i);
      			DoubleVertex dv1 = list.get(j);

      			//Calculate distance in DoubleVertex0 
      			double dv0x = dv0.v0.x - dv0.v1.x;
      			double dv0y = dv0.v0.y - dv0.v1.y;
      			double dv0z = dv0.v0.z - dv0.v1.z;
      			double dv0Dist = Math.sqrt(dv0x*dv0x+dv0y*dv0y+dv0z*dv0z);

      			//Calculate distance in DoubleVertex1 
      			double dv1x = dv1.v0.x - dv1.v1.x;
      			double dv1y = dv1.v0.y - dv1.v1.y;
      			double dv1z = dv1.v0.z - dv1.v1.z;
      			double dv1Dist = Math.sqrt(dv1x*dv1x+dv1y*dv1y+dv1z*dv1z);

      			System.out.print(dv0.v0.no + " " + "dv0Dist: " + dv0Dist + " " + 
      					dv1.v1.no + " " + " dv1Dist: " + dv1Dist);

      			//if(dv0Dist == dv1Dist) {
      			if (Math.abs(dv0Dist-dv1Dist)<1e-4) {
      				System.out.println(" yes");
      				graph.addEdge(dv0, dv1);
      			}
      			else System.out.println(" no");
      		}
      	}
```

Vielleicht ist die neu Berechnung der Kanten falsch und man kann vielleicht irgendwie Zugriff auf die Edge Klasse bekommen. Leider weiss ich nicht weiter?


----------



## Marco13 (29. Jul 2009)

Ich habe gesehen, wie du die DoubleVertices erstellst, und ich habe gesehen, wie du die """Kanten"""längen berechnest. Deswegen habe ich die obige Antwort geschrieben, und dabei u.a. erwähnt, dass das, was dort berechnet wird, nicht wirklich Kantenlängen sind...


----------



## flashdog (29. Jul 2009)

Leider weiss ich nicht wie ich die wirklichen Kantenlängen berechnen kann. Wenn du vielleicht ein wenig Zeit hättest könntest du mir bitte dabei helfen die richtigen Kantenlängen zu berechnen.


----------



## Marco13 (29. Jul 2009)

Leider ist mir (und vermutlich/anscheinend auch anderen) nicht klar, was du überhaupt willst. Du hast zwei Graphen. Einer hat Knoten A,B,C,D, und der andere E,F,G,H.  Diese Knoten sind durch Kanten verbunden. 

Hier das ganze mal als Matrix aufgeschrieben: Zwischen A und B ist eine Kante der Länge 6, zwischen A und C eine der Länge 3... usw.


```
A B C D
A   6 3 4
B     7 5
C       2
D


  E F G H
E   2 3 5 
F     4 6
G       8
H
```


Daraus erstellst du jetzt einen Graphen mit "DoubleVertices". Jeder einzelne Vertex dieses Graphen besteht also aus jeweils einem Vertex des ersten und einem Vertex des zweiten Graphen. Das ganze wieder als Matrix:

```
AE AF AG AH BE BF BG BH BE BF BG BH BE BF BG BH 
AE 
AF 
AG 
AH 
BE 
BF 
BG 
BH 
BE 
BF 
BG 
BH 
BE 
BF 
BG 
BH
```

So. Und WANN soll dort nun WO eine Kante WELCHER länge eingefügt werden?


----------



## flashdog (30. Jul 2009)

Als Matrix müsste dies wie folgt aussehen:

```
AE AF AG AH BE BF BG BH BE BF BG BH BE BF BG BH CE CF CG CH DE DF DG DH 
AE                                                       3 
AF                      6                                            4
AG 
AH 
BE                                                                      5
BF 
BG 
BH 
BE 
BF 
BG 
BH 
BE 
BF 
BG 
BH
CE                                                                2
CF
CG
CH
DE
DF                                                 
DG 
DH
```
Aber leider weiss ich nicht wie man es programmiert.


----------



## Marco13 (30. Jul 2009)

Also lautet die Regel: Zwischen zwei DoubleVertices (x,y) und (z,w) soll eine Kante der Länge a existieren, wenn
(x oder y) UND (z und w)  
eine Kante der Länge a haben???? (<-Fragezeichen)

Wenn das so sein soll, kreigt man das bestimmt hin. Was auch immer damit dann... modelliert wird :bahnhof:


----------



## flashdog (30. Jul 2009)

Genau, das ist die Bedingung, aber leider weiss ich nicht wie man es programmiert.


----------



## Marco13 (30. Jul 2009)

Sooo, damit wäre die Mittagspause auch rum.

Das ist aber ziemlich langweilig: JEDER doubleVertex ernthält einen vertex vom Graphen 0 und einen vom Graphen 1. In beiden Graphen sind alle vertices mit allen anderen verbunden. D.h. wenn dort irgendwelche Kanten gleich lang sind, werden u.U. sehr, sehr viele Kanten in den finalen Graphen eingefügt, d.h. die Cliquenberechnung dauert SEHR lange. Um dem ganzen auch nur einen HAUCH von Übersichtlichkeit zu verpassen, würde ich dir dringend empfehlen, wenigstens die Nummern, die in den vertices gespeichert sind, eindeutig zu machen (so hat man eine Kante zwischen Vertex 6 und Vertex 6 :autsch: )

Hier mal ein bißchen code - *das ist nur schnell hingehackt* - aber so vom Ansatz her hilft's ja vielleicht...

```
import java.io.File;
import java.io.IOException;
import java.util.*;

import org.jgrapht.EdgeFactory;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.SimpleWeightedGraph;

class Vertex {
  int no;
  float x,y,z;
  
  public Vertex(int no, float x, float y, float z)
  {
        this.no = no;
      this.x = x;
      this.y = y;
      this.z = z;
  }
  
  public String toString()
  {
      return "("+no+": "+x+","+y+","+z+")";
  }
}

class Edge 
{
  float length; 
  Vertex v0, v1;

  public Edge(Vertex v0, Vertex v1) {
      this.v0 = v0;
      this.v1 = v1;
      this.length = computeLength(); //Abstand von v0 zu v1
  }

  private float computeLength() 
  {
      float dx = v0.x - v1.x;
      float dy = v0.y - v1.y;
      float dz = v0.z - v1.z;
      return (float) Math.sqrt(dx*dx+dy*dy+dz*dz);
  }
  float getLength() 
  {
      return length;
  }
  
  public String toString()
  {
      return "Edge "+v0+"-"+v1+" length "+getLength();
  }
  
}

class DoubleVertex {
    Vertex v0, v1;
    
  public DoubleVertex(Vertex v0, Vertex v1) {
        this.v0 = v0;
        this.v1 = v1;
    }
  public String toString()
  {
      return "("+v0.no+","+v1.no+")";
  }
  
  public double distance()
  {
      double dv1x = v0.x - v1.x;
      double dv1y = v0.y - v1.y;
      double dv1z = v0.z - v1.z;
      double dv1Dist = Math.sqrt(dv1x*dv1x+dv1y*dv1y+dv1z*dv1z);
      return dv1Dist;
      
  }
}

class DoubleEdge 
{
    float length; 
    DoubleVertex v0;
        DoubleVertex v1;

        public DoubleEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex) {
        this.v0 = sourceVertex;
        this.v1 = targetVertex;
    }
}

public class BronKerbosch 
{
    private static final float epsilon = 1e-2f;
    
    public static void main(String[] args) throws IOException 
    {
        
      String fileNameTarget = "a.txt";
      String fileNameTemplate = "b.txt";
        EdgeFactory<Vertex,Edge> ef0 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g0 = new SimpleWeightedGraph<Vertex,Edge>(ef0)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
            Scanner diskScanner = new Scanner(new File(fileNameTarget));
            while (diskScanner.hasNext()) {
                Vertex vertex = new Vertex(diskScanner.nextInt(), diskScanner.nextFloat(),diskScanner.nextFloat(),diskScanner.nextFloat());
                g0.addVertex(vertex);
            }
            System.out.println(g0);
            
        
        List<Vertex> vertices0 = new ArrayList<Vertex>(g0.vertexSet());
        
        //everything is conected to everything in graph 1
        for (int i = 0; i < vertices0.size(); i++){
            for (int j = 0; j < vertices0.size(); j++){
                if (i != j) 
                    g0.addEdge(vertices0.get(i), vertices0.get(j));
            }
        }
        System.out.println(vertices0.size());
        
        //Second Graph
        EdgeFactory<Vertex,Edge> ef1 = new EdgeFactory<Vertex,Edge>()
        {
            public Edge createEdge(Vertex sourceVertex, Vertex targetVertex)
            {
                return new Edge(sourceVertex, targetVertex);
            }
        };

        WeightedGraph<Vertex, Edge> g1 = new SimpleWeightedGraph<Vertex,Edge>(ef1)
        {
            @Override
            public double getEdgeWeight(Edge e)
            {
                return e.getLength();
            }
        };
        
            Scanner diskScanner2 = new Scanner(new File(fileNameTemplate));
            while (diskScanner2.hasNext()) {
                Vertex vertex = new Vertex(diskScanner2.nextInt(), diskScanner2.nextFloat(),diskScanner2.nextFloat(),diskScanner2.nextFloat());
                System.out.println("read "+vertex);
                g1.addVertex(vertex);
            }

                System.out.println(g1);

            
        
        List<Vertex> vertices1 = new ArrayList<Vertex>(g1.vertexSet());
        
        //everything is conected to everything in graph 2
        for (int i = 0; i < vertices1.size(); i++){
            for (int j = 0; j < vertices1.size(); j++){
                if (i != j) 
                    g1.addEdge(vertices1.get(i), vertices1.get(j));
            }
        }
        System.out.println(vertices1.size());
       
        
        System.out.println("Edges of g0");
        for (Edge edge : g0.edgeSet())
        {
            System.out.println(edge);
        }
        
        System.out.println("Edges of g1");
        for (Edge edge : g1.edgeSet())
        {
            System.out.println(edge);
        }
        
        for (Edge edge0 : g0.edgeSet())
        {
            for (Edge edge1 : g1.edgeSet())
            {
                if (Math.abs(edge0.getLength() - edge1.getLength()) < epsilon)
                {
                    System.out.println("Equal: ");
                    System.out.println(edge0);
                    System.out.println(edge1);
                }
            }
        }
        
        
     // Alle vertices des Product graph erstellen
        EdgeFactory<DoubleVertex,DoubleEdge> Pef = new EdgeFactory<DoubleVertex,DoubleEdge>()
        {
            public DoubleEdge createEdge(DoubleVertex sourceVertex, DoubleVertex targetVertex)
            {
                return new DoubleEdge(sourceVertex, targetVertex);
            }
        };        
        
        WeightedGraph<DoubleVertex, DoubleEdge> graph = new SimpleWeightedGraph<DoubleVertex,DoubleEdge>(Pef)
        {
//          @Override
//          public double getEdgeWeight(DoubleEdge e)
//          {
//              return e.getLength(); 
//          }
        };

        for (Vertex v0 : g0.vertexSet())
        {
            for (Vertex v1 : g1.vertexSet())
            {
                    //Here must come vertex Similitary
                graph.addVertex(new DoubleVertex(v0,v1));
            }
        }

        // Alle Kanten einfügen
        List<DoubleVertex> list = new ArrayList<DoubleVertex>(graph.vertexSet());
        for (int i=0; i<list.size(); i++)
        {
            for (int j=i+1; j<list.size(); j++)
            {
//              if(i !=j)
                {
                    DoubleVertex dv0 = list.get(i);
                    DoubleVertex dv1 = list.get(j);

                    Set<Edge> edges00 = g0.edgesOf(dv0.v0);
                    Set<Edge> edges01 = g0.edgesOf(dv1.v0);
                    Set<Edge> edges0 = new HashSet<Edge>();
                    edges0.addAll(edges00);
                    edges0.addAll(edges01);
                        
                    Set<Edge> edges10 = g1.edgesOf(dv0.v1);
                    Set<Edge> edges11 = g1.edgesOf(dv1.v1);
                    Set<Edge> edges1 = new HashSet<Edge>();
                    edges1.addAll(edges10);
                    edges1.addAll(edges11);
                    
                    for (Edge edge0 : edges0)
                    {
                        Edge edge1 = findEdgeWithLength(edges1, edge0.getLength());
                        if (edge1 != null)
                        {
                            if (graph.getEdge(dv0, dv1) == null)
                            {
                                System.out.println("For DoubleVertex ");
                                System.out.println("    "+dv0.v0);
                                System.out.println("    "+dv0.v1);
                                System.out.println("and DoubleVertex ");
                                System.out.println("    "+dv1.v0);
                                System.out.println("    "+dv1.v1);
                                System.out.println("In g0 found  edge "+edge0);
                                System.out.println("In g1 exists edge "+edge1);
                                System.out.println("Adding edge to graph");
                                graph.addEdge(dv0, dv1);
                            }
                            break;
                        }
                        else
                        {
                            //System.out.println("No matching edge for edge "+edge0);
                        }
                    }
                }
            }
        }
   
        BronKerboschCliqueFinder<DoubleVertex, DoubleEdge> cf = 
            new BronKerboschCliqueFinder<DoubleVertex,DoubleEdge>(graph);
        Collection<Set<DoubleVertex>> cliques = cf.getAllMaximalCliques(); 
        for (Set<DoubleVertex> clique : cliques)
        {
            System.out.println("Clique: "+clique);
        }
    }   
    
    
    private static Edge findEdgeWithLength(Collection<Edge> edges, float length)
    {
        for (Edge edge : edges)
        {
            if (Math.abs(edge.getLength() - length) < epsilon)
            {
                return edge;
            }
        }
        return null;
    }
    
}
```


----------



## flashdog (31. Jul 2009)

Vielen Dank werde es gleich ausprobieren.


----------

