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;
}
}
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);
}
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” .
-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
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)
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);
}*/
}
}
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);
}
}
}
Arrays.toString( clique.toArray() );
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);
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'
"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);
}
}
}
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'
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);
}
}
}
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)
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);
}
}
}
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);
}
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;
}
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);
}
}
}
//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
//Vertex einfügen
for (Vertex v0 : g0.vertexSet())
{
for (Vertex v1 : g1.vertexSet())
{
graph.addVertex(new DoubleVertex(v0,v1));
}
}
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 würden nur eingefügt, wenn zwei dieser DoubleVertices zufällig zwei gleich weit voneinander entfernte Vertices (aus zwei verschiedenen Graphen!) enhalten würden...
// 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");
}
}
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
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
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;
}
}