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

Code:

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)

Code:

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:

Code:

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:

Code:

-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

Code:

 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:

Code:

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:

Code:

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

Code:

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;
	}
}

Code:

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>....

Code:

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

Code:

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

Code:

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:

Code:

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:

Code:

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

	at BronKerbosh02.main(BronKerbosh02.java:207)

Code:

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:

Code:

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.

Code:

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:

Code:

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.

Code:

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

Code:

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.

Code:

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:

Code:

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:

Code:

//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

Java:

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:

Java:

      	//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:

Java:

// 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.

Code:

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:

Code:

   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:

Code:

   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...

Java:

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.

	Titel	Forum	Antworten	Datum
G	Algorithmus Graphen	Java Basics - Anfänger-Themen	10	18. Mrz 2021
M	Berechnung der Reststrecke bei Graphen	Java Basics - Anfänger-Themen	1	23. Feb 2020
D	Zusammenhängenden Graphen für Gleisnetz erstellen	Java Basics - Anfänger-Themen	13	19. Feb 2020
S	Library fuer Graphen	Java Basics - Anfänger-Themen	3	26. Jan 2020
T	Collections Methode (Knoten hinzufügen) für Graphen	Java Basics - Anfänger-Themen	32	8. Jan 2020
M	Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen	Java Basics - Anfänger-Themen	11	19. Jun 2019
J	Graphen in Java zeichnen	Java Basics - Anfänger-Themen	11	11. Jul 2017
L	Graphen: Anzahl Knoten // Knoten in Array speichern	Java Basics - Anfänger-Themen	4	5. Jul 2017
U	Best Practice Graphen Tiefensuche Klassifizierung von Kanten "B","C","F"	Java Basics - Anfänger-Themen	2	9. Jun 2017
B	Java Graphen zeichnen - Brauche Hilfe	Java Basics - Anfänger-Themen	9	8. Nov 2015
M	Ungerichtete Graphen	Java Basics - Anfänger-Themen	21	7. Jan 2015
M	Best Practice Programmierstil Graphen-A*-Suche	Java Basics - Anfänger-Themen	5	17. Sep 2014
V	Graphen	Java Basics - Anfänger-Themen	1	20. Jun 2014
F	Graphen-Algorithmen	Java Basics - Anfänger-Themen	1	2. Jun 2014
D	Graphen abspeichern (Gewichte)	Java Basics - Anfänger-Themen	9	16. Jun 2012
W	Funktions-Graphen "zeichnen"	Java Basics - Anfänger-Themen	2	3. Nov 2010
	Graphen zeichnen	Java Basics - Anfänger-Themen	5	21. Apr 2009
	zwei adjazenzlisten für jeden knoten eines graphen sinnvoll?	Java Basics - Anfänger-Themen	17	17. Jan 2009
T	Graphen	Java Basics - Anfänger-Themen	11	30. Jun 2008
G	Graphen	Java Basics - Anfänger-Themen	3	7. Okt 2007
M	Graphen zusammenfügen	Java Basics - Anfänger-Themen	2	17. Jul 2007
E	Zu einem Graphen die Kantenbewertung geben	Java Basics - Anfänger-Themen	2	3. Okt 2006
J	Aus Graphen einen Spannbaum erzeugen	Java Basics - Anfänger-Themen	5	11. Jun 2006
M	Graphen (Tiefensuche)	Java Basics - Anfänger-Themen	2	16. Nov 2005
M	Spi in pi4j Bibliothek	Java Basics - Anfänger-Themen	45	9. Okt 2021
B	tar.gz in Eclipse als Bibliothek einbinden	Java Basics - Anfänger-Themen	3	20. Mrz 2021
G	eigene Bibliothek einbinden	Java Basics - Anfänger-Themen	1	19. Dez 2019
E	Best Practice Jar-file mit zwei Klassen und externer Bibliothek über Konsole erzeugen	Java Basics - Anfänger-Themen	13	10. Jul 2018
J	App.jar muss im Projekt App als Bibliothek vorhanden sein?!	Java Basics - Anfänger-Themen	1	20. Okt 2017
D	Bibliothek runterladen	Java Basics - Anfänger-Themen	1	19. Jul 2017
H	GSON-Bibliothek für eigene Programme benutzen	Java Basics - Anfänger-Themen	2	4. Sep 2016
M	Java Bibliothek Javadoc not found	Java Basics - Anfänger-Themen	1	4. Aug 2016
I	Science Bibliothek	Java Basics - Anfänger-Themen	3	26. Nov 2015
	Java Standard-Bibliothek	Java Basics - Anfänger-Themen	3	10. Jul 2015
G	eigene Bibliothek in Java importieren	Java Basics - Anfänger-Themen	5	3. Mai 2015
L	JDK installieren GUI-Bibliothek installieren	Java Basics - Anfänger-Themen	4	25. Mrz 2015
O	Eclipse Bibliothek standardmäßig einbinden	Java Basics - Anfänger-Themen	5	2. Okt 2014
M	Ist die Hamcrest Bibliothek auch schon in Junit 4.11 verfügbar?	Java Basics - Anfänger-Themen	1	18. Jul 2014
C	Jar Datei findet Bibliothek nicht	Java Basics - Anfänger-Themen	2	23. Mai 2014
B	Neue Bibliothek hinzufügen	Java Basics - Anfänger-Themen	2	22. Mai 2014
X	Clustering-Bibliothek	Java Basics - Anfänger-Themen	4	1. Mrz 2014
F	JAR als bibliothek einbinden	Java Basics - Anfänger-Themen	1	18. Dez 2013
S	Methode aus Bibliothek ausrufen	Java Basics - Anfänger-Themen	2	27. Okt 2013
B	JSF Bibliothek	Java Basics - Anfänger-Themen	6	15. Okt 2012
A	Meine erste Bibliothek erstellen	Java Basics - Anfänger-Themen	24	16. Mai 2012
K	Bibliothek per "Struktur" anlegen	Java Basics - Anfänger-Themen	5	6. Mai 2012
S	Externe Bibliothek zu Resources hinzufügen?	Java Basics - Anfänger-Themen	5	18. Feb 2012
S	Bibliothek in Eclipse einbinden	Java Basics - Anfänger-Themen	2	15. Feb 2012
F	Klassen Bibliothek erstellen für Anfänger	Java Basics - Anfänger-Themen	8	9. Mai 2011
B	Snowball Stemmer Bibliothek nutzen	Java Basics - Anfänger-Themen	8	7. Nov 2010
I	HUMath Bibliothek einbinden?!	Java Basics - Anfänger-Themen	4	2. Nov 2010
0	Objekte übers Netzwerk schicken? Bibliothek?	Java Basics - Anfänger-Themen	2	24. Okt 2009
T	Bibliothek erstellen	Java Basics - Anfänger-Themen	4	21. Aug 2009
	Externe Bibliothek OHNE IDE benutzen	Java Basics - Anfänger-Themen	5	29. Jul 2008
N	system-bibliothek bei eclipse einrichten	Java Basics - Anfänger-Themen	2	30. Mai 2008
P	Bibliothek wie zB. in Flash	Java Basics - Anfänger-Themen	2	15. Jan 2008
B	Links verfolgen -- Bibliothek nicht gefunden?	Java Basics - Anfänger-Themen	6	3. Dez 2006
G	hilfe! zusätzliche java bibliothek einbinden	Java Basics - Anfänger-Themen	3	13. Okt 2006
M	Spaltengrößen automatisch anpassen mit POI Bibliothek ?	Java Basics - Anfänger-Themen	4	10. Aug 2006
M	jar-Bibliothek mitgeben	Java Basics - Anfänger-Themen	9	7. Jun 2006
L	Java Bibliothek scheint zu fehlen	Java Basics - Anfänger-Themen	4	2. Feb 2006
	Integral unter Verwendung der Java-Bibliothek berechnen	Java Basics - Anfänger-Themen	10	21. Apr 2005

Graphen Bibliothek

Bekanntes Mitglied

Top Contributor

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Gesperrter Benutzer

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Top Contributor

Bekanntes Mitglied

Ähnliche Java Themen