在java中的Bron Kerbosch实现

我正在使用gephi在java中实现Bron Kerbosch，但结果中的问题并不正确，给出了列表n1，n2，n3，n4，n5，n6，n7，n8，n9 应打印N2，N3，N5，N7，N8，N9，但它打印 N1 N2 N3 N5 N9 和所使用的代码是：在java中的Bron Kerbosch实现

import java.io.File; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.Vector; 

import javax.swing.JFileChooser; 
import javax.swing.filechooser.FileFilter; 
import javax.swing.filechooser.FileNameExtensionFilter; 

import org.gephi.graph.api.DirectedGraph; 
import org.gephi.graph.api.GraphController; 
import org.gephi.graph.api.GraphModel; 
import org.gephi.graph.api.Node; 
import org.gephi.io.importer.api.Container; 
import org.gephi.io.importer.api.ImportController; 
import org.gephi.io.processor.plugin.DefaultProcessor; 
import org.gephi.project.api.ProjectController; 
import org.gephi.project.api.Workspace; 
import org.openide.util.Lookup; 


public class maxCliqueTest { 
    private static Vector<Node> BestFound; 
    public static Vector<Node> FindMaxClique(DirectedGraph g,Vector<Node> P,Vector<Node> R,Vector<Node> X){ 
     if(P.size()==0 && X.size()==0){ 
      return R; 
     } 
     int i=0; 
     while(i<P.size()){ 
      Node v=P.elementAt(i); 

      R.add(v); 
      FindMaxClique(g,Intersection(g,P,v),R,Intersection(g,X,v)); 
      P.remove(v); 
      X.add(v); 
     } 
     return null; 
    } 
    public static Vector<Node> Intersection(DirectedGraph g,Vector<Node> T,Node n){ 
     int i=0; 
     Vector<Node> v=new Vector<Node>(); 
     while(i<T.size()){ 
      if(g.isAdjacent(T.elementAt(i), n)){ 
       System.out.println(T.elementAt(i).getLabel()); 
       v.add(T.elementAt(i)); 

      } 
      i+=1; 
     } 
     return v; 

    } 

    public static void main(String[] args) throws IOException { 
     ProjectController pc = Lookup.getDefault().lookup(ProjectController.class); 
     pc.newProject(); 
     Node[] s = null; 
     Workspace workspace = pc.getCurrentWorkspace(); 
     JFileChooser fileChose=new JFileChooser(); 
     File fichie; 
     ImportController importController = Lookup.getDefault().lookup(ImportController.class); 
      Container container; 
     FileFilter filter = new FileNameExtensionFilter("graphml fichier", "graphml"); 
     fileChose.addChoosableFileFilter(filter); 

     int ret = fileChose.showDialog(null, "Open file"); 
     if (ret == JFileChooser.APPROVE_OPTION) { 
       fichie = fileChose.getSelectedFile(); 
         try 
         { 
          container = importController.importFile(fichie); 
          container.getLoader().setAllowAutoNode(false); 
         //Force DIRECTED 

          importController.process(container, new DefaultProcessor(), workspace); 
          GraphModel graphModel = Lookup.getDefault().lookup(GraphController.class).getGraphModel(); 
          DirectedGraph directedGraph = graphModel.getDirectedGraph(); 
          System.out.println(
            "Nodes: " 
            +directedGraph.getNodeCount()+ 
            " Edges: " 
            +directedGraph.getEdgeCount()); 
          int i=0; 
          Vector<Node> R = new Vector<Node>() ,X = new Vector<Node>(),P = new Vector<Node>(); 
          for(Node n : directedGraph.getNodes().toArray()){ 
          P.add(n); 

          } 
         Vector<Node> j=FindMaxClique(directedGraph,P,R,X); 
         int k=0; 
         while(k<j.size()){ 
          System.out.println(j.get(k).getLabel()); 
          k+=1; 
         } 


         //Don’t create missing nodes 
         } 
         catch(Exception ex) { 
          ex.printStackTrace(); 

         } 
      } 

    } 



}

在哪里我做错了什么？一阵搜索，并回答狩猎

文件中使用graph.graphml

<?xml version="1.0" encoding="UTF-8"?><graphml xmlns="http://graphml.graphdrawing.org/xmlns"> 
<key attr.name="label" attr.type="string" for="node" id="label"/> 
<key attr.name="Edge Label" attr.type="string" for="edge" id="edgelabel"/> 
<key attr.name="weight" attr.type="double" for="edge" id="weight"/> 
<key attr.name="Edge Id" attr.type="string" for="edge" id="edgeid"/> 
<key attr.name="r" attr.type="int" for="node" id="r"/> 
<key attr.name="g" attr.type="int" for="node" id="g"/> 
<key attr.name="b" attr.type="int" for="node" id="b"/> 
<key attr.name="x" attr.type="float" for="node" id="x"/> 
<key attr.name="y" attr.type="float" for="node" id="y"/> 
<key attr.name="size" attr.type="float" for="node" id="size"/> 
<graph edgedefault="undirected"> 
<node id="n1"> 
<data key="label">n1</data> 
<data key="size">10.0</data> 
<data key="r">255</data> 
<data key="g">0</data> 
<data key="b">0</data> 
<data key="x">149.36537</data> 
<data key="y">36.526653</data> 
</node> 
<node id="n2"> 
<data key="label">n2</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">66.46559</data> 
<data key="y">-222.63277</data> 
</node> 
<node id="n3"> 
<data key="label">n3</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">-342.35153</data> 
<data key="y">68.50529</data> 
</node> 
<node id="n4"> 
<data key="label">n4</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">-21.092024</data> 
<data key="y">115.7537</data> 
</node> 
<node id="n5"> 
<data key="label">n5</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">297.1616</data> 
<data key="y">-269.26038</data> 
</node> 
<node id="n6"> 
<data key="label">n6</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">-162.95857</data> 
<data key="y">-384.95587</data> 
</node> 
<node id="n7"> 
<data key="label">n7</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">-167.34999</data> 
<data key="y">215.14323</data> 
</node> 
<node id="n8"> 
<data key="label">n8</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">356.55112</data> 
<data key="y">255.99077</data> 
</node> 
<node id="n9"> 
<data key="label">n9</data> 
<data key="size">10.0</data> 
<data key="r">0</data> 
<data key="g">0</data> 
<data key="b">255</data> 
<data key="x">-175.79152</data> 
<data key="y">184.92937</data> 
</node> 
<edge source="n1" target="n2"> 
<data key="edgeid">0</data> 
<data key="edgelabel">e1</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n3"> 
<data key="edgeid">1</data> 
<data key="edgelabel">e2</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n4"> 
<data key="edgeid">2</data> 
<data key="edgelabel">e3</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n5"> 
<data key="edgeid">3</data> 
<data key="edgelabel">e4</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n6"> 
<data key="edgeid">4</data> 
<data key="edgelabel">e5</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n7"> 
<data key="edgeid">5</data> 
<data key="edgelabel">e6</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n8"> 
<data key="edgeid">6</data> 
<data key="weight">1.0</data> 
</edge> 
<edge source="n1" target="n9"> 
<data key="edgeid">7</data> 
<data key="weight">1.0</data> 
</edge> 
</graph> 
</graphml>

来源

2016-05-30 sdx11

你能描述勒布朗Kerbosch算法对我们来说，懒惰所以用户？ –

@LajosArpad该算法在给定图中找到最大集团 – sdx11

你称为集团又如何测量它？你测量节点的数量，顶点的数量，还是你有顶点的权重？ –

后，我发现它：

import java.io.File; 
import java.io.IOException; 
import java.util.Arrays; 
import java.util.Vector; 
import javax.swing.JFileChooser; 
import javax.swing.filechooser.FileFilter; 
import javax.swing.filechooser.FileNameExtensionFilter; 

import org.gephi.graph.api.DirectedGraph; 
import org.gephi.graph.api.GraphController; 
import org.gephi.graph.api.GraphModel; 
import org.gephi.graph.api.Node; 
import org.gephi.io.importer.api.Container; 
import org.gephi.io.importer.api.ImportController; 
import org.gephi.io.processor.plugin.DefaultProcessor; 
import org.gephi.project.api.ProjectController; 
import org.gephi.project.api.Workspace; 
import org.openide.util.Lookup; 




public class maxCliqueTest { 
    private Vector<Node> listNoeud; 
    private Vector<Node> MaxClique; 
    private DirectedGraph g; 
     maxCliqueTest(){ 
      this.listNoeud=new Vector<Node>(); 
       this.MaxClique=new Vector<Node>(); 
     } 
     Vector<Node> getNbrs(Node v) { 

        Vector<Node> t=new Vector<Node>(); 
        t.addAll(Arrays.asList(g.getNeighbors(v).toArray())); 
      return t; 
     } 

     // Intersection of two sets 
     Vector<Node> intersect(Vector<Node> arlFirst,Vector<Node> arlSecond) { 
      Vector<Node> arlHold = new Vector<Node>(arlFirst); 
      arlHold.retainAll(arlSecond); 
      return arlHold; 
     } 

     // Union of two sets 
     Vector<Node> union(Vector<Node> arlFirst,Vector<Node> arlSecond) { 
     Vector<Node> arlHold = new Vector<Node>(arlFirst); 
      arlHold.addAll(arlSecond); 
      return arlHold; 
     } 

     // Removes the neigbours 
     Vector<Node> removeNbrs(Vector<Node> arlFirst, Node v) { 
      Vector<Node> arlHold = new Vector<Node>(arlFirst); 
      arlHold.removeAll(getNbrs(v)); 
      return arlHold; 
     } 

     // Version with a Pivot 
     void Bron_KerboschWithPivot(Vector<Node> R, Vector<Node> P, 
       Vector<Node> X, String pre) { 


      if ((P.size() == 0) && (X.size() == 0)) { 
       printClique(R); 
       return; 
      } 
      // System.out.println(); 
      Vector<Node> P1 = new Vector<Node>(P); 
      // Find Pivot 
      Node u = getMaxDegreeVertex(union(P, X)); 

      //System.out.println("" + pre + " Pivot is " + (u.getLabel())); 
      //P = P/Nbrs(u) 
      P = removeNbrs(P, u); 

      for (Node v : P) { 
       R.add(v); 
       Bron_KerboschWithPivot(R, intersect(P1, getNbrs(v)), 
         intersect(X, getNbrs(v)), pre + "\t"); 
       R.remove(v); 
       P1.remove(v); 
       X.add(v); 
      } 
     } 

     Node getMaxDegreeVertex(Vector<Node> t) { 
      int i=0,temp=0; 
      Node n=null; 
      while(i<t.size()){ 
       if(g.getDegree(t.elementAt(i))>temp){ 
        temp=g.getDegree(t.elementAt(i)); 
        n=t.get(i); 
       } 
       i+=1; 
      } 
      return n; 
     } 

     void Bron_KerboschPivotExecute() { 

      Vector<Node> X = new Vector<Node>(); 
      Vector<Node> R = new Vector<Node>(); 
      Vector<Node> P = listNoeud; 
      Bron_KerboschWithPivot(R, P, X, ""); 
     } 

     void printClique(Vector<Node> r) { 


      if(this.MaxClique.isEmpty()) 
      { 

       for (Node v : r) { 
        this.MaxClique.add(v); 
       } 

      }else { 
       if(r.size()>this.MaxClique.size()){ 
       this.MaxClique.clear(); 
       for (Node v : r) { 
        this.MaxClique.add(v); 
       } 
       } 
      } 

     } 




    public static void main(String[] args) throws IOException { 
     ProjectController pc = Lookup.getDefault().lookup(ProjectController.class); 
     pc.newProject(); 
     Node[] s = null; 
     Workspace workspace = pc.getCurrentWorkspace(); 
     JFileChooser fileChose=new JFileChooser(); 
     File fichie; 
     ImportController importController = Lookup.getDefault().lookup(ImportController.class); 
      Container container; 
     FileFilter filter = new FileNameExtensionFilter("graphml fichier", "graphml"); 
     fileChose.addChoosableFileFilter(filter); 

     int ret = fileChose.showDialog(null, "Open file"); 
     if (ret == JFileChooser.APPROVE_OPTION) { 
       fichie = fileChose.getSelectedFile(); 
         try 
         { 
          container = importController.importFile(fichie); 
          container.getLoader().setAllowAutoNode(false); 
          //Force DIRECTED 
          importController.process(container, new DefaultProcessor(), workspace); 
          GraphModel graphModel = Lookup.getDefault().lookup(GraphController.class).getGraphModel(); 
          DirectedGraph directedGraph = graphModel.getDirectedGraph(); 
          System.out.println(
            "Nodes: " 
            +directedGraph.getNodeCount()+ 
            " Edges: " 
            +directedGraph.getEdgeCount()); 
          int i=0; 
          maxCliqueTest m=new maxCliqueTest(); 
          m.g=directedGraph; 

          for(Node n : directedGraph.getNodes().toArray()){ 
          m.listNoeud.add(n); 

          } 
         m.Bron_KerboschPivotExecute(); 

         StringBuilder strBuild = new StringBuilder(); 

         strBuild.append("{"); 
         for (Node n:m.MaxClique) { 
         strBuild.append("" + (n.getLabel()) + ","); 
         } 
         if (strBuild.length() != 1) { 
         strBuild.setLength(strBuild.length() - 1); 
         } 
         strBuild.append("}"); 

         System.out.println("the max clique is :"+strBuild); 
         //Don’t create missing nodes 
         } 
         catch(Exception ex) { 
          ex.printStackTrace(); 

         } 
      } 

    } 



}

来源

2016-05-31 10:17:33 sdx11

在java中的Bron Kerbosch实现

回答

相关问题