OrientDB에서 비순환 그래프의 스패닝 트리를 만드는 방법

Question

OrientDB에서 구현되는 비순환 그래프의 스패닝 트리를 계산해야합니다. 내가 찾고있는 스패닝 트리는 루트에서 지점이나 잎으로 이어지는 가장 긴 경로 만 유지해야하는 것과 같이 구축되었습니다. 예를 들어 트리 루트 & 사이의 직접 링크 (에지)와 동일한 루트와 동일한 브랜치 사이의 여러 브랜치를 통과하는 두 번째 경로 사이에서 선택할 수있는 경우 후자의 경로 (가장자리) 만 유지해야합니다 최종 나무 (스패닝 트리 :)를 짓습니다.

OrientDB에서이 스패닝 트리를 어떻게 계산합니까? OrientDB의 ShortestPath() 또는 dijkstra()와 비슷한 기능이 손쉽게 사용할 수 있습니까? 많은 도움을 주셔서 미리 감사드립니다.

감사

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(); 

    } 
}