如何在 Orientdb 中找到短路径（边而不是顶点）

Question

我有这张图： A-->B, A-->C, B-->C, C-->D, A-->E

我想在java中找到"A"和"D"之间的最短路径。我用过：

s= select from ( select expand( shortestPath("+ first_vertex.getId() +", "+ second_vertex.getId() +").outE()))

    for (Edge edge : (Iterable<Edge>) g.command(
        new OCommandSQL(s)).execute()) {
            System.out.println(edge);
        }

我得到的问题不是想要的结果：

      A - B
      A - C
      A - E 
      C - D

当我关注顶点而不是边时，我得到了正确的短路径，它是： A -> C -> D

为什么 edges 不像我那样工作？

编辑：

Updated graph

当我有附加图像中的图形并且我想使用您的方法找到 "A" 和 "D" 之间的最短路径时，我仍然没有边：最短路径（顶点): A C D SHORTEST PATH (edge): SHORTEST PATH (vertex) 不应该是：A, F, E, D ?。如果我现在想找到 "D" 和 "A" 之间的最短路径，我也不会在您更新后获得任何优势。

Answer 1

仅使用 'select expand(shortestpath(...))' returns 个顶点。

从你的初始情况开始。

你的目标是提取形成最短路径的边（我想我明白了），所以得到以下结果：

一种方法是： - 找到最短路径（带顶点） - 获取最短路径的各个顶点，连接第一个顶点到最后一个顶点的边。

static final String REMOTE = "remote:localhost/";

static final String NOMEDB  = "shortpath";
static final String CURRENTPATH = REMOTE + NOMEDB;

public static void main(String[] args) throws IOException {
    OServerAdmin serverAdmin = new OServerAdmin(CURRENTPATH).connect("root", "root");

    OrientGraphNoTx g = new OrientGraphFactory(CURRENTPATH).getNoTx();

    showPath(g);
}

public static void showPath (OrientGraphNoTx  g) {
    String s = "";
    String V1 = "#12:0"; //Vertex A
    String V2 = "#12:3"; //Vertex D
    s= "select expand(shortestPath(" + V1 + ", " + V2+"))";

    Iterable<Vertex> result = g.command(new OSQLSynchQuery<Vertex>(s)).execute();
    List<OrientVertex> listaVertex = new ArrayList<OrientVertex>();
    CollectionUtils.addAll(listaVertex, result.iterator());

    List<String> out = new ArrayList<String>();
    List<String> in = new ArrayList<String>();
    List<String> edgePath = new ArrayList<String>();

    //for each vertices get edge out & in
    Iterable<Edge> tempOut;
    Iterable<Edge> tempIn;
    String singleIn = "";
    String singleOut = "";

    System.out.println("SHORTEST PATH (vertex):");
    for (int v=0; v<listaVertex.size(); v++) {
        System.out.print(listaVertex.get(v).getProperty("name")+ " " );
    }
    System.out.println("");

    for (int i=0; i<listaVertex.size(); i++) {

        tempOut = listaVertex.get(i).getEdges(Direction.OUT, "collega");
        tempIn = listaVertex.get(i).getEdges(Direction.IN, "collega");

        //get edge in
        for(Edge edgeIn : tempIn) {
            in.add(edgeIn.getId().toString());
        }

        //forech edge in, check if is in out
        for(int x=0; x<in.size(); x++) {
            singleIn = in.get(x);
            for(int z=0; z<out.size(); z++) {
                singleOut = out.get(z);
                if(singleIn.equals(singleOut)) {
                    edgePath.add(singleIn);
                }
            }
        }

        //to empty out list
        out.clear();

        //get edge out
        for(Edge edgeOut : tempOut) {
            out.add(edgeOut.getId().toString());
        }

        //to empty in list
        in.clear();

    }

    System.out.println("SHORTEST PATH (edge):");
    for (int ind=0; ind<edgePath.size(); ind++) {
        System.out.println(edgePath.get(ind));
    }

}

你得到的结果是这样的：

A --#13:1--> C --13:4--> D

编辑 1

绝对是一个改进：

//forech edge in, check if is in out
        boolean finded = false;                        //*******new
        for(int x=0; x<in.size(); x++) {
            singleIn = in.get(x);
            for(int z=0; z<out.size(); z++) {
                singleOut = out.get(z);
                if(singleIn.equals(singleOut)) {
                    edgePath.add(singleIn);
                    finded = true;          //*******new
                    break;              //*******new
                }
            } 
            if(finded)break;                //*******new
        }

避免不必要的检查。

编辑 2

在结果中添加了边缘标签。

public static void showPath (OrientGraphNoTx  g) {
    String s = "";
    String V1 = "#12:0"; //Vertex A
    String V2 = "#12:3"; //Vertex D
    s= "select expand(shortestPath(" + V1 + ", " + V2+"))";

    Iterable<Vertex> result = g.command(new OSQLSynchQuery<Vertex>(s)).execute();
    List<OrientVertex> listaVertex = new ArrayList<OrientVertex>();
    CollectionUtils.addAll(listaVertex, result.iterator());

    List<String> out = new ArrayList<String>();
    List<String> in = new ArrayList<String>();
    List<String> inLabel = new ArrayList<String>();
    List<String> edgePath = new ArrayList<String>();

    //per ogni vertice recupera archi uscenti ed entranti
    Iterable<Edge> tempOut;
    Iterable<Edge> tempIn;
    String singleIn = "";
    String singleOut = "";

    System.out.println("SHORTEST PATH (vertex):");
    for (int v=0; v<listaVertex.size(); v++) {
        System.out.print(listaVertex.get(v).getProperty("name")+ " " );
    }
    System.out.println("");

    for (int i=0; i<listaVertex.size(); i++) {

        tempOut = listaVertex.get(i).getEdges(Direction.OUT, "collega");
        tempIn = listaVertex.get(i).getEdges(Direction.IN, "collega");

        //get edge in
        for(Edge edgeIn : tempIn) {
            in.add(edgeIn.getId().toString());  //list edge id
            inLabel.add(edgeIn.getLabel());     // list edge label
        }

        //forech edge in, check if is in out
        boolean finded = false;
        for(int x=0; x<in.size(); x++) {
            singleIn = in.get(x);
            for(int z=0; z<out.size(); z++) {
                singleOut = out.get(z);
                if(singleIn.equals(singleOut)) {
                    edgePath.add(singleIn);   //in edgePath[position] = id
                    edgePath.add(inLabel.get(x));   //in edgePAth[position+1] = label
                    finded = true;
                    break; 
                }
            } 
            if(finded)break;    
        }

        //to empty out list
        out.clear();

        //get edge out
        for(Edge edgeOut : tempOut) {
            out.add(edgeOut.getId().toString());
        }

        //to empty in list
        in.clear();

    }

    System.out.println("SHORTEST PATH (edge):");
    for (int ind=0; ind<edgePath.size(); ind=ind+2) {  //ind+2 so i get id[position x] and label [position x+1] 
        System.out.println("id:"+edgePath.get(ind)+", Label:"+edgePath.get(ind+1));
    }

}

这是结果：

编辑 3

加上新的顶点，图形应该是这样的。（这是正确的吗？）

从这张图开始，我们有：

1) 从 "A" 到 "D" 最短路径（顶点）：是 A-C-D（对你而言正确）最短路径（边）：是 edgeA-C，edgeC-D

2) 从 "D" 到 "A" 最短路径（顶点）：是 D-C-A（对你正确）最短路径（边）：是 edgeD-C，edgeC-A（是你的#11:4，#11:1）

使用代码，自动提取最短路径（使用orient的特定功能），从而提取该路径中包含的边。手册中唯一的内容是我输入了 V1 和 V2 RID 顶点开始和结束。

编辑 4

Answer 2

我创建了一个新答案，因为代码与之前的代码大不相同。使用此代码，您只需设置 StartNode (Vstart) & endNode (Vend)，以及 returns 方向为 'out'（与第一个节点相比）和方向为 'in' 的 ShortestPath（指边）（如果存在）总是与第一个节点进行比较。该操作基于提取从 orient 的 ShortestPath() 返回的顶点，因为这些顶点中的每一个控制边。

public class PathEdge {


    static final String REMOTE = "remote:localhost/";

    static final String NOMEDB  = "ShortestPath2";
    static final String CURRENTPATH = REMOTE + NOMEDB;

public static void main(String[] args) throws IOException {

    OServerAdmin serverAdmin = new OServerAdmin(CURRENTPATH).connect("root", "root");

    OrientGraphNoTx g = new OrientGraphFactory(CURRENTPATH).getNoTx();

    String Vstart   = "a";  //----- to set
    String Vend     = "d";  // ---- to set
    String queryClassName   = "Nodo";  //----- to set
    String queryProperty    = "name"; //----- to set
    String edgeNAme = "is_a";   //----- to set
    String direction = "'OUT'";  //----- to set "BOTH" (incoming and outgoing), "OUT" (outgoing) and "IN" (incoming)

    String query1 = "select from "+queryClassName+" where "+queryProperty+" = '"+Vstart+"'";
    Iterable<Vertex> start = g.command(new OSQLSynchQuery<Vertex>(query1)).execute();

    String query2 = "select from "+queryClassName+" where "+queryProperty+" = '"+Vend+"'";  
    Iterable<Vertex> end = g.command(new OSQLSynchQuery<Vertex>(query2)).execute();

    long startTime = System.currentTimeMillis();
    showPath(g, start.iterator().next().getId().toString(), end.iterator().next().getId().toString(), edgeNAme, direction);
    long estimatedTime = System.currentTimeMillis() - startTime;
    System.out.println("");
    System.out.println("TIME EXECUTE: "+estimatedTime+"ms");
}

public static void showPath (OrientGraphNoTx  g, String Vstart, String Vend , String edge, String direction) {

     String s = "";
     int position = 0;
     int maxsize = 0;

     s= "select expand(shortestPath(" + Vstart + ", " + Vend+", "+direction+"))";

    Iterable<Vertex> result = g.command(new OSQLSynchQuery<Vertex>(s)).execute();
    List<OrientVertex> listaVertex = new ArrayList<OrientVertex>();
    CollectionUtils.addAll(listaVertex, result.iterator());

    List<String> listPRECout = new ArrayList<String>();
    List<String> listPRECin = new ArrayList<String>();
    List<String> listFOLLout = new ArrayList<String>();
    List<String> listFOLLin = new ArrayList<String>();

    List<String> resultOut = new ArrayList<String>();
    List<String> resultIn = new ArrayList<String>();

    //per ogni vertice recupera archi uscenti ed entranti
    Iterable<Edge> tempOut;
    Iterable<Edge> tempIn;
    String singleIn = "";
    String singleOut = "";
    boolean finded = false;

    System.out.println("SHORTEST PATH (vertex [direction "+direction+"]):");
    for (int v=0; v<listaVertex.size(); v++) {
        System.out.print(listaVertex.get(v).getProperty("name")+ " " );
    }
    System.out.println("");
    System.out.println("");
    maxsize = listaVertex.size()-1;
    for (int v=0; v<maxsize; v++) {

        //--------FIRST VERTEX OF THE SHORTEST PATH
        tempOut = listaVertex.get(v).getEdges(Direction.OUT, edge);
        tempIn = listaVertex.get(v).getEdges(Direction.IN, edge);

        //set listPRECin 
        for(Edge edgeIn : tempIn) {
            listPRECin.add(edgeIn.getId().toString());  //position x   = rid
            listPRECin.add(edgeIn.getLabel());          //position x+1 = label
        }

        //set listPRECout 
        for(Edge edgeOut : tempOut) {
            listPRECout.add(edgeOut.getId().toString());  //position x   = rid
            listPRECout.add(edgeOut.getLabel());          //position x+1 = label
        }

        //--------SECOND VERTEX OF THE SHORTEST PATH
        tempOut = listaVertex.get(v+1).getEdges(Direction.OUT, edge);
        tempIn = listaVertex.get(v+1).getEdges(Direction.IN, edge);

        //set listFOLLin 
        for(Edge edgeIn : tempIn) {
            listFOLLin.add(edgeIn.getId().toString());  //position x   = rid
            listFOLLin.add(edgeIn.getLabel());          //position x+1 = label
        }

        //set listFOLLout 
        for(Edge edgeOut : tempOut) {
            listFOLLout.add(edgeOut.getId().toString());  //position x   = rid
            listFOLLout.add(edgeOut.getLabel());          //position x+1 = label
        }


        //------MATCH LOGIC
        //...compare PRECin with FOLLout
        finded = false;
        for(int i = 0; i<listPRECin.size(); i=i+2) {
            singleIn = listPRECin.get(i);
            for(int o = 0; o<listFOLLout.size(); o=o+2){
                singleOut = listFOLLout.get(o);
                if(singleIn.equals(singleOut)) {

                    //check is there a hole
                    if(v==0) {
                        resultIn.add(singleIn);  //rid
                        resultIn.add(listPRECin.get(i+1)); //label
                        finded = true;
                        break; 
                    } else if((v*2) == resultIn.size()) {
                        resultIn.add(singleIn);  //rid
                        resultIn.add(listPRECin.get(i+1)); //label
                        finded = true;
                        break; 
                    }
                }
            }
            if(finded)break;    
        }

        finded = false;
        //...compare PRECout with FOLLin
        for(int i = 0; i<listPRECout.size(); i=i+2) {
            singleOut = listPRECout.get(i);
            for(int o = 0; o<listFOLLin.size(); o=o+2){
                singleIn = listFOLLin.get(o);
                if(singleOut.equals(singleIn)) {
                    //check is there a hole
                    if(v==0) {
                        resultOut.add(singleOut);  //rid
                        resultOut.add(listPRECout.get(i+1)); //label
                        finded = true;
                        break; 
                    } else if((v*2) == resultOut.size()) {
                        resultOut.add(singleOut);  //rid
                        resultOut.add(listPRECout.get(i+1)); //label
                        finded = true;
                        break; 
                    }
                }
            }
            if(finded)break;    
        }

        //to empty out list
        listPRECin.clear();
        listPRECout.clear();    
        listFOLLin.clear();
        listFOLLout.clear();    

        //cheack if it's in the penultimate vertex
        position = v+1;
        if( position==maxsize) {
            break;
        }

    }


    System.out.println("SHORTEST PATH (edge, out direction):");
    if(resultOut.size()>0) {
        for (int ind=0; ind<resultOut.size(); ind=ind+2) {  //ind+2 so i get id[position x] and label [position x+1] 
            System.out.println("id:"+resultOut.get(ind)+", Label:"+resultOut.get(ind+1));
        }
    } else {
        System.out.println("No edge in this direction (OUT)");
    }

    System.out.println("");
    System.out.println("SHORTEST PATH (edge, in direction):");
    if(resultIn.size()>0) {
        for (int ind=0; ind<resultIn.size(); ind=ind+2) {  //ind+2 so i get id[position x] and label [position x+1] 
            System.out.println("id:"+resultIn.get(ind)+", Label:"+resultIn.get(ind+1));
        }
    }else {
        System.out.println("No edge in this direction (IN)");
    }

}

}

编辑 2

在 ShortestPath 函数中使用 'direction'。

如何在 Orientdb 中找到短路径（边而不是顶点）

how to find shortpath in Orientdb (edges instead of vertexes)

java

orientdb