OrientDBの非循環グラフのスパニングツリーを解く方法

Question

OrientDBで実装された非循環グラフのスパニングツリーを計算する必要があります。私が探しているスパニングツリーは、ルートからブランチまたはリーフに至る最長のパスだけを保持するように構築されています。たとえば、特定のブランチのツリールート&の間の直接リンク（エッジ）と、同じルートと同じブランチの間の複数のブランチを通過する第2のパスの間の選択肢がある場合は、後者のパス（エッジ）のみを保持する必要があります最終的なツリー（スパニングツリー:)を構築します。

OrientDBでこのスパニングツリーを計算するにはどうすればよいですか？ OrientDBのShortestPath（）やdijkstra（）と同様の機能がありますか？事前に多くのお手伝いをありがとうございます。 Javaで

よろしく

A.労働者

Answer 1

、あなたはより良いあなたが欲しいものを説明クーロン

import java.util.ArrayList; 
import java.util.List; 
import com.tinkerpop.blueprints.Direction; 
import com.tinkerpop.blueprints.Vertex; 
import com.tinkerpop.blueprints.impls.orient.OrientGraph; 

public class LongestPath { 

    private boolean stop=false; 
    private Vertex vertex_from=null; 
    private List<Vertex> vertexPreviousStep=new ArrayList<Vertex>(); 
    private List<Vertex> vertexCurrently=new ArrayList<Vertex>(); 
    private List<List<Vertex>> paths=new ArrayList<List<Vertex>>(); 
    private OrientGraph g; 

    public LongestPath(OrientGraph g) { 
     this.g=g; 
    } 

    protected List<Vertex> getPath(String rid_from, String rid_to) { 
     if(!checkIfExistsNodes(rid_from,rid_to)) 
      return new ArrayList<Vertex>(); 

     vertexPreviousStep.add(vertex_from); 

     List<Vertex> p=new ArrayList<Vertex>(); 
     Vertex from=g.getVertex(rid_from); 
     Vertex to=g.getVertex(rid_to); 
     p.add(from); 
     paths.add(p); 

     int step=1; 
     do{ 
      stop=false; 
      for(Vertex v: vertexPreviousStep){ 
       Vertex rid_previousVertex=v; 
       List<Vertex> rid_toAdd=new ArrayList<Vertex>(); 
       Iterable<Vertex> nodes = (Iterable<Vertex>) v.getVertices(Direction.OUT); 
       for(Vertex v1:nodes){ 
        rid_toAdd.add(v1); 
        String rid=v1.getId().toString(); 
        if(!rid.equals(rid_to)) // non sono arrivato al nodo finale 
         vertexCurrently.add(v1); 
       } 
       if(rid_toAdd.size()!=0) 
        setPaths(rid_previousVertex,rid_toAdd,step); 
      } 
      change(); 
      step++; 
     }while(stop==true); 
     cleanPaths(to); 
     return getLongestPath(); 
    } 

    private boolean checkIfExistsNodes(String rid_from,String rid_to) { 
     boolean find_from=false; 
     boolean find_to=false; 
     for(Vertex v:g.getVertices()){ 
      if(v.getId().toString().equals(rid_from)){ 
       find_from=true; 
       vertex_from=v; 
      } 
      else if(v.getId().toString().equals(rid_to)) 
       find_to=true; 
     } 
     if(find_from==false || find_to==false) 
      return false; 
     return true; 
    } 

    public void change(){ 
     vertexPreviousStep.clear(); 
     for(Vertex v:vertexCurrently) 
      vertexPreviousStep.add(v); 
     vertexCurrently.clear(); 
    } 

    private void setPaths(Vertex previousVertex,List<Vertex> rid_toAdd,int step) { 
     for(int i=0;i<paths.size();i++){ 
      List<Vertex> list=paths.get(i); 
      Vertex last=list.get(list.size()-1); 
      if(last.getId().toString().equals(previousVertex.getId().toString()) && list.size()==step){ 
       int j=0; 
       for(Vertex rid:rid_toAdd){ 
        boolean rid_found=false; 
        for(Vertex p:list){ 
         if(p.equals(rid)) 
          rid_found=true; 
        } 
        if(rid_found==false){ 
         List<Vertex> p2=new ArrayList<Vertex>(); 
         for(Vertex p:list) 
          p2.add(p); 
         p2.add(rid); 
         if(j==0){ 
          stop=true; 
          paths.set(i, p2); 
          j++; 
         } 
         else 
          paths.add(p2); 
        } 
       } 
      } 
     } 
    } 

    public void cleanPaths(Vertex to){ 
     for(int i=0;i<paths.size();i++){ 
      List<Vertex> list=paths.get(i); 
      if(!list.get(list.size()-1).equals(to)){ 
       paths.remove(i); 
       i--; 
      } 
     } 
    } 

    public List<Vertex> getLongestPath(){ 
     if(paths.size()==0) 
      return new ArrayList<Vertex>(); 
     else{ 
      List<Vertex> list=paths.get(0); 
      int max_size= list.size(); 
      for(int i=1;i<paths.size();i++){ 
       if(paths.get(i).size()>max_size){ 
        max_size=paths.get(i).size(); 
        list=paths.get(i); 
       } 
      } 
      return list; 
     } 
    } 

public static void main(String[] args) { 

    OrientGraph g=new OrientGraph("remote:localhost/39697129"); 
    LongestPath longest= new LongestPath(g); 
    String id_vertex_from="#9:0"; 
    String id_vertex_to="#10:1"; 
    List<Vertex> list=longest.getPath(id_vertex_from,id_vertex_to); 
    System.out.println(list); 
    g.shutdown(); 

    } 
}