OrientDB所有路径之间

我想找到考虑通过OUT导航两个节点之间的任何长度的所有可能的路径只有边缘。

我正在使用shortestPath（），但它只返回一个路径。我搜索了很多，我找不到在OrientDB中做到这一点的本地课程。我已经在使用非本地类。但是，效率不够高。这里的一些shortespath代码：

s = " select expand(shortestpath(" + first_vertex.getId() + ", " + second_vertex.getId() + ", "+ direction +"))"; 
for (Vertex v : (Iterable<Vertex>) g.command(new OCommandSQL(s)).execute()){ 

      . . . 
. . . 

    }

是否有OrientDB任何本地的解决方案，因为它是在Neo4j的情况？

来源

2016-05-27 Questioner

您可以使用此代码

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 AllPaths { 

     private boolean stop=false; 
     private Vertex vertexFrom=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 AllPaths(OrientGraph g) { 
      this.g=g; 
     } 

     protected List<List<Vertex>> getPaths(String ridFrom, String ridTo) { 
      if(!check(ridFrom,ridTo)) 
       return paths; 
      vertexPreviousStep.add(vertexFrom); 
      List<Vertex> p=new ArrayList<Vertex>(); 
      p.add(vertexFrom); 
      paths.add(p); 
      int step=1; 
      do{ 
       stop=false; 
       for(Vertex v: vertexPreviousStep){ 
        List<Vertex> toAdd=new ArrayList<Vertex>(); 
        Iterable<Vertex> nodes = (Iterable<Vertex>) v.getVertices(Direction.OUT); 
        for(Vertex v1:nodes){ 
         toAdd.add(v1); 
         if(!v1.getId().toString().equals(ridTo)) 
          vertexCurrently.add(v1); 
        } 
        if(toAdd.size()!=0) 
         setPaths(v,toAdd,step); 
       } 
       change(); 
       step++; 
      }while(stop==true); 
      return cleanPaths(ridTo); 
     } 

     private boolean check(String ridFrom,String ridTo) { 
      boolean findFrom=false,findTo=false; 
      for(Vertex v:g.getVertices()){ 
       if(v.getId().toString().equals(ridFrom)){ 
        findFrom=true; 
        vertexFrom=v; 
       } 
       else if(v.getId().toString().equals(ridTo)) 
        findTo=true; 
      } 
      if(findFrom==false || findTo==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> 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 v1:toAdd){ 
         boolean vertexFound=false; 
         for(Vertex v2:list){ 
          if(v2.getId().toString().equals(v1.getId().toString())) 
           vertexFound=true; 
         } 
         if(vertexFound==false){ 
          List<Vertex> listVertex=new ArrayList<Vertex>(); 
          for(Vertex p:list) 
           listVertex.add(p); 
          listVertex.add(v1); 
          if(j==0){ 
           stop=true; 
           paths.set(i,listVertex); 
           j++; 
          } 
          else 
           paths.add(listVertex); 
         } 
        } 
       } 
      } 
     } 

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

     public static void main(String[] args) { 

      OrientGraph g=new OrientGraph("remote:localhost/MyDb"); 
      AllPaths paths=new AllPaths(g); 
      System.out.println(paths.getPaths("#9:0", "#9:8")); 

     } 
}

UPDATE

import java.util.ArrayList; 
import java.util.List; 
import com.orientechnologies.orient.client.remote.OServerAdmin; 
import com.tinkerpop.blueprints.Direction; 
import com.tinkerpop.blueprints.Edge; 
import com.tinkerpop.blueprints.Vertex; 
import com.tinkerpop.blueprints.impls.orient.OrientGraph; 

public class Main { 

    private boolean stop=false; 
    private List<Vertex> visitedNodesPreviousStep=new ArrayList<Vertex>(); 
    private List<Vertex> visitedNodeCurrently=new ArrayList<Vertex>(); 
    private List<List<Vertex>> path_vertex=new ArrayList<List<Vertex>>(); 
    private List<List<Edge>> path_edges=new ArrayList<List<Edge>>(); 
    private OrientGraph g; 
    int step=0; 

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

    protected List<List<Object>> getDistance(String starting_rid, String ending_rid,int depth) { 

     Vertex starting_node=g.getVertex(starting_rid); 
     Vertex ending_node=g.getVertex(ending_rid); 

     visitedNodesPreviousStep.add(starting_node); 

     List<Vertex> p1=new ArrayList<Vertex>(); 
     p1.add(starting_node); 
     path_vertex.add(p1); 

     step=1; 
     boolean found_node_to_be_added=false; 
     do{ 
      stop=false; 
      found_node_to_be_added=false; 
      for(Vertex v: visitedNodesPreviousStep){ 
       List<Edge> edges_to_be_added=new ArrayList<Edge>(); 
       List<Vertex> nodes_to_be_added=new ArrayList<Vertex>(); 
       Iterable<Edge> it_edge = (Iterable<Edge>) v.getEdges(Direction.OUT); 
       for(Edge e1:it_edge){ 
        Vertex v1=e1.getVertex(Direction.IN); 
        edges_to_be_added.add(e1); 
        nodes_to_be_added.add(v1); 
        String rid=v1.getId().toString(); 
        if(!rid.equals(ending_rid)){ // checking the current @rid isn't the ending 
         visitedNodeCurrently.add(v1); 
        } 
        else{ // ending node found 
         setPathFoundList(v,ending_node,step,e1); 
         //stop=true; 
        } 
       } 
       if(nodes_to_be_added.size()!=0 && stop==false){ 
        found_node_to_be_added=true; 
        setpath_vertex(v,nodes_to_be_added,edges_to_be_added); 
       } 
      } 
      if(found_node_to_be_added==false){ 
       stop=true; 
      } 
      //System.out.println("step = " + step + " " +path_vertex); 
      change(); 

      step++; 
     }while(stop==false && step<depth); 
     clean_vertex_path(ending_node); 
     return getShortestPathList(); 
    } 

    public void change(){ 
     visitedNodesPreviousStep.clear(); 
     for(Vertex v:visitedNodeCurrently) 
      visitedNodesPreviousStep.add(v); 
     visitedNodeCurrently.clear(); 
    } 

    private void setPathFoundList(Vertex node,Vertex ending_node,int step,Edge edge){ 
     for(int i=0;i<path_vertex.size();i++){ 
      List<Vertex> path=path_vertex.get(i); 
      Vertex last=path.get(path.size()-1); 
      if(last.getId().equals(node.getId()) && path.size()==step){ 
       path.add(ending_node); 
       List<Edge> edgesPath=path_edges.get(i); 
       edgesPath.add(edge); 
      } 
     } 
    } 

    private void setpath_vertex(Vertex node,List<Vertex> nodes_to_be_added,List<Edge> edges_to_be_added) { 
     for(int i=0;i<path_vertex.size();i++){ 
      List<Vertex> path=path_vertex.get(i); 
      Vertex last=path.get(path.size()-1); 
      if(last.getId().equals(node.getId())){ 
       int j=0; 
       for(int h=0;h<nodes_to_be_added.size();h++){ 
        boolean name_present=false; 
        for(Vertex p:path){ 
         if(p.getId().equals(nodes_to_be_added.get(h).getId())) 
          name_present=true; 
        } 
        if(name_present==false){ 
         List<Vertex> p2=new ArrayList<Vertex>(); 
         for(Vertex p:path) 
          p2.add(p); 
         p2.add(nodes_to_be_added.get(h)); 
         List<Edge> e2=new ArrayList<Edge>(); 
         if(step==1){ 
          e2.add(edges_to_be_added.get(h)); 
         } 
         else{ 
          List<Edge> edgesPath=path_edges.get(i); 
          for(Edge p1:edgesPath) 
           e2.add(p1); 
          e2.add(edges_to_be_added.get(h)); 
         } 
         if(j==0){ 
          path_vertex.set(i, p2); 
          if(step==1){ 
           path_edges.add(i, e2); 
          } 
          else{ 
           path_edges.set(i, e2); 
          } 
          j++; 
         } 
         else{ 
          path_vertex.add(p2); 
          path_edges.add(e2); 
         } 
        } 
       } 
      } 
     } 
    } 

    public void clean_vertex_path(Vertex ending_node_name){ 
     for(int i=0;i<path_vertex.size();i++){ 
      List<Vertex> path=path_vertex.get(i); 
      if(!path.get(path.size()-1).getId().equals(ending_node_name.getId())){ 
       path_vertex.remove(i); 
       path_edges.remove(i); 
       i--; 
      } 
     } 
    } 

    public List<List<Object>> getShortestPathList(){ 
     List<List<Object>> resultList=new ArrayList<List<Object>>(); 
     if(path_vertex.size()==0) 
      return new ArrayList<List<Object>>(); 
     else{ 
      for(int i=0;i<path_vertex.size();i++){ 
       List<Object> result=new ArrayList<Object>(); 
       List<Vertex> path2= path_vertex.get(i); 
       List<Edge> edges2= path_edges.get(i); 
       for(int k=0;k<path2.size();k++){ 
        result.add(path2.get(k)); 
        if(k!=path2.size()-1) 
         result.add(edges2.get(k)); 
       } 
       resultList.add(result); 
      } 
     } 

     return resultList; 
    } 

    public static void main(String[] args) { 

     String remote="remote:localhost/"; 
     String DBname="ShortestPath"; 
     String currentPath=remote+DBname; 

     OServerAdmin serverAdmin; 
     try { 
      serverAdmin = new OServerAdmin(currentPath).connect("root", "root"); 
      if(serverAdmin.existsDatabase()){ 

       OrientGraph g=new OrientGraph(currentPath); 
       Main shortest2 = new Main(g); 
       System.out.println("SHORTEST PATH " + shortest2.getDistance("#9:0","#9:8",5)); 

      } 
     } 
     catch(Exception e){ 
     } 
    } 
}

希望它能帮助。

来源

2016-05-27 12:21:52

非常感谢。我已经使用过你的代码，但至少与Neo4j相比，它的确很慢。 – Questioner

@ Questioner速度差异有多大？ –

OrientDB中没有这样的函数，但是可以扩展shortestPath（）并避免在第一次出现时返回，而是继续找到找到的X个项目。 – Lvca

@ Lvca和@亚历山德罗

我用这个代码由 “卢卡斯” OrientDB get Edges with shortestPath()

我觉得效率和有用的。你在想什么？它检索两个节点之间的所有路径。我如何确定搜索深度，例如深度2,3,4等？

import java.util.ArrayList; 
import java.util.List; 


import com.orientechnologies.orient.client.remote.OServerAdmin; 
import com.tinkerpop.blueprints.Direction; 
import com.tinkerpop.blueprints.Edge; 
import com.tinkerpop.blueprints.Vertex; 
import com.tinkerpop.blueprints.impls.orient.OrientGraph; 

public class myClass { 

private boolean stop=false; 
private List<Vertex> visitedNodesPreviousStep=new ArrayList<Vertex>(); 
private List<Vertex> visitedNodeCurrently=new ArrayList<Vertex>(); 
private List<List<Vertex>> path_vertex=new ArrayList<List<Vertex>>(); 
private List<List<Edge>> path_edges=new ArrayList<List<Edge>>(); 
private OrientGraph g; 
int step=0; 

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

protected List<Object> getDistance(String starting_rid, String ending_rid) { 

Vertex starting_node=g.getVertex(starting_rid); 
Vertex ending_node=g.getVertex(ending_rid); 

visitedNodesPreviousStep.add(starting_node); 

List<Vertex> p1=new ArrayList<Vertex>(); 
p1.add(starting_node); 
path_vertex.add(p1); 

step=1; 
boolean found_node_to_be_added=false; 
do{ 
stop=false; 
found_node_to_be_added=false; 
for(Vertex v: visitedNodesPreviousStep){ 
List<Edge> edges_to_be_added=new ArrayList<Edge>(); 
List<Vertex> nodes_to_be_added=new ArrayList<Vertex>(); 
Iterable<Edge> it_edge = (Iterable<Edge>) v.getEdges(Direction.OUT); 
for(Edge e1:it_edge){ 
Vertex v1=e1.getVertex(Direction.IN); 
edges_to_be_added.add(e1); 
nodes_to_be_added.add(v1); 
String rid=v1.getId().toString(); 
if(!rid.equals(ending_rid)){ // checking the current @rid isn't the ending 
visitedNodeCurrently.add(v1); 
} 
else{ // ending node found 
setPathFoundList(v,ending_node,step,e1); 
stop=true; 
} 
} 
if(nodes_to_be_added.size()!=0 && stop==false){ 
found_node_to_be_added=true; 
setpath_vertex(v,nodes_to_be_added,edges_to_be_added); 
} 
} 
if(found_node_to_be_added==false){ 
stop=true; 
} 
System.out.println("step = " + step + " " +path_vertex); 
change(); 

step++; 
}while(stop==false); 
clean_vertex_path(ending_node); 
return getShortestPathList(); 
} 

public void change(){ 
visitedNodesPreviousStep.clear(); 
for(Vertex v:visitedNodeCurrently) 
visitedNodesPreviousStep.add(v); 
visitedNodeCurrently.clear(); 
} 

private void setPathFoundList(Vertex node,Vertex ending_node,int step,Edge edge){ 
for(int i=0;i<path_vertex.size();i++){ 
List<Vertex> path=path_vertex.get(i); 
Vertex last=path.get(path.size()-1); 
if(last.getId().equals(node.getId()) && path.size()==step){ 
path.add(ending_node); 
List<Edge> edgesPath=path_edges.get(i); 
edgesPath.add(edge); 
} 
} 
} 

private void setpath_vertex(Vertex node,List<Vertex> nodes_to_be_added,List<Edge> edges_to_be_added) { 
for(int i=0;i<path_vertex.size();i++){ 
List<Vertex> path=path_vertex.get(i); 
Vertex last=path.get(path.size()-1); 
if(last.getId().equals(node.getId())){ 
int j=0; 
for(int h=0;h<nodes_to_be_added.size();h++){ 
boolean name_present=false; 
for(Vertex p:path){ 
if(p.getId().equals(nodes_to_be_added.get(h).getId())) 
name_present=true; 
} 
if(name_present==false){ 
List<Vertex> p2=new ArrayList<Vertex>(); 
for(Vertex p:path) 
p2.add(p); 
p2.add(nodes_to_be_added.get(h)); 
List<Edge> e2=new ArrayList<Edge>(); 
if(step==1){ 
e2.add(edges_to_be_added.get(h)); 
} 
else{ 
List<Edge> edgesPath=path_edges.get(i); 
for(Edge p1:edgesPath) 
e2.add(p1); 
e2.add(edges_to_be_added.get(h)); 
} 
if(j==0){ 
path_vertex.set(i, p2); 
if(step==1){ 
path_edges.add(i, e2); 
} 
else{ 
path_edges.set(i, e2); 
} 
j++; 
} 
else{ 
path_vertex.add(p2); 
path_edges.add(e2); 
} 
} 
} 
} 
} 
} 

public void clean_vertex_path(Vertex ending_node_name){ 
for(int i=0;i<path_vertex.size();i++){ 
List<Vertex> path=path_vertex.get(i); 
if(!path.get(path.size()-1).getId().equals(ending_node_name.getId())){ 
path_vertex.remove(i); 
path_edges.remove(i); 
i--; 
} 
} 
} 

public List<Object> getShortestPathList(){ 
List<Object> result=new ArrayList<Object>(); 
if(path_vertex.size()==0) 
return new ArrayList<Object>(); 
else{ 
List<Vertex> path=path_vertex.get(0); 
int min_size= path.size(); 
for(int i=0;i<path_vertex.size();i++){ 
if(path_vertex.get(i).size()<=min_size){ 
List<Vertex> path2= path_vertex.get(i); 
List<Edge> edges2= path_edges.get(i); 
for(int k=0;k<path2.size();k++){ 
result.add(path2.get(k)); 
if(k!=path2.size()-1) 
result.add(edges2.get(k)); 
} 
} 
} 
} 
return result; 
} 

public static void main(String[] args) { 

String remote="remote:localhost/"; 
String DBname="Stack36794694"; 
String currentPath=remote+DBname; 

OServerAdmin serverAdmin; 
try { 
serverAdmin = new OServerAdmin(currentPath).connect("root", "root"); 
if(serverAdmin.existsDatabase()){ 

OrientGraph g=new OrientGraph(currentPath); 
myClass shortest2 = new myClass(g); 
System.out.println("SHORTEST PATH " + shortest2.getDistance("#9:0","#9:5")); 

} 
} 
catch(Exception e){ 
} 
} 
}

来源

2016-05-27 21:24:37 Questioner

我已通过修改LucaS的代码更新了我的答案 –

OrientDB所有路径之间

回答

相关问题