OrientDB：如何在忽略某些边的同时使用 dijkstra 函数查询图形

Question

我正在尝试从 orientdb 中查询数据，同时忽略一些边。

我的查询格式为：

select expand(dijkstra(#12:15,#12:20,'property','both'))

但如前所述，我想忽略图形的某些边缘。

有什么建议吗？

编辑

这是我的图形结构。站作为顶点 Image Click

路径为边 Image Click

非常感谢@Ivan Mainetti 的回答，我已经尝试测试 main()

这是我的 main()

 String nomeDb = "Demo2";
    try {
        System.out.println("Before connect OServerAdmin");
        OServerAdmin serverAdmin = new OServerAdmin("remote:128.199.xxx.xxx/"+nomeDb).connect("admin","password");
        System.out.println("After connect");
        if(serverAdmin.existsDatabase()){  // il db esiste
            System.out.println("in if");
            //connessione a db
            OrientGraph g = new OrientGraph("remote:128.199.xxx.xxx/"+nomeDb);
            DijkstraExcl d = new DijkstraExcl(g, "Path", "distance");
            Set<String> ex =new HashSet<String>();

            //------------------------------------------------
            Vertex start = g.getVertex("#12:6");
            Vertex end = g.getVertex("#12:11");
            ex.add("#13:0");
            Direction direction = Direction.OUT;
            System.out.println(d.getPath(start,end,direction,ex));
            System.out.println(d.getPathString(start,end,direction,ex));
            System.out.println(d.getWeight(start,end,direction,ex));
            //------------------------------------------------
            //chiude db
            g.shutdown();
        }
        else{
            System.out.println("Il database '"+ nomeDb + "' non esiste");
        }
        serverAdmin.close();
    } catch (IOException e) {
        e.printStackTrace();
    }

运行main() 之后的结果是

无

2147483647

忽略[#13:0]后的正确答案应该是

[#12:6,#12:8,#12:10,#12:11]

Answer 1

一种方法是利用 OrientDB 对 "Infinity" 的一些支持这一事实，如 "console.sh" 打字稿所示：

> select 1.0E400

----+------+--------
#   |@CLASS|1       
----+------+--------
0   |null  |Infinity
----+------+--------

> select eval('0 < 1.0E400')

----+------+----
#   |@CLASS|eval
----+------+----
0   |null  |true
----+------+----


> select -1.0E400

----+------+---------
#   |@CLASS|-1       
----+------+---------
0   |null  |-Infinity
----+------+---------

> select eval('0 < -1.0E400')

----+------+-----
#   |@CLASS|eval 
----+------+-----
0   |null  |false
----+------+-----

Answer 2

尝试以下具有参数 ridFrom、ridTo、属性、direction 和 excludeEdges 的 JS 函数。使用 Studio，您可以使用以下命令进行尝试：

select expand(result) from (select myFunction("12:6","12:11","distance","out","[#13:0]") as result)

边缘 "edge1" 和 "edge2" 被忽略。

var g=orient.getGraph();
var listEdges=excludeEdges.substring(1,excludeEdges.length-1).split(",");
var S=[], T=[] , id_weigth=[] , from , to , infinity = Number.MAX_VALUE;
step1();
step2();
return getPath();

// Initialization
function step1() {
    var selectFrom=g.command("sql","select from V where @rid ="+ ridFrom);
    var selectTo=g.command("sql","select from V where @rid ="+ ridTo);
    if(selectFrom.length>0 && selectTo.length>0){
        from=selectFrom[0]; 
        to=selectTo[0];     
        S.push(from);       
        var selectAll=g.command("sql","select from V"); 
        for (i=0;i<selectAll.length;i++) {
            if (selectAll[i].getId()!=from.getId())
                T.push(selectAll[i]);
        }
        var index=1;
        for (i=0;i<selectAll.length;i++) {
            var id = selectAll[i].getId();
            if (selectAll[i].getId()!= from.getId()) {
                id_weigth[index] = {id:id,weigth:infinity};
                index++;
            } 
            else  
                id_weigth[0] = {id:id,weigth:0};
        }
        setWeigth_Direction(from);
    }
}

// Assignment permanent label
function step2(){
    var stop = true;
    do {
        stop = true;
        for (i=0;i<T.length;i++) {
            var id = T[i].getId();
            for (j=0;j<id_weigth.length;j++) {
                if (id_weigth[j].id==id) {
                  if (id_weigth[j].weigth != infinity){
                        stop = false;
                  }
                }
            }
        }
        if (stop == true)
            break;
        else { 
            var index2 = 0; minWeigth = 0; j = null;
            for (i=0;i<T.length;i++) {
                var id = T[i].getId();
                for (m=0;m<id_weigth.length;m++) {
                    if (id_weigth[m].id==id) {
                        if (index2 == 0) {
                            minWeigth = id_weigth[m].weigth;
                            index2++;
                            j = T[i];
                        }    
                        else if (id_weigth[m].weigth < minWeigth) {
                            minWeigth = id_weigth[m].weigth;
                            j = T[i];
                        }
                    }
                }
            }
            T.splice(getPositionInT(j.getId()),1);
            S.push(j);
            if (T.length == 0)
                break;
            else
                step3(j);
        }
    } while (stop == false);
}

// Assignment temporary label
function step3(j) {
    setWeigth_Direction(j);
}

function setWeigth(vertex,direction1,direction2) {
    var edges=g.command("sql","select expand(" + direction1+"E()) from "+ vertex.getId());
    for(m=0;m<edges.length;m++){
        var myEdge=edges[m];;
        var idEdge = myEdge.getId().toString();
        var validEdge=true;
        for (s=0;s<listEdges.length;s++) {
            if(listEdges[s]==idEdge)
                validEdge=false;
        }
        if(validEdge==true){
            var myWeigth = myEdge.getProperty(property);
            var myVertex=g.command("sql","select expand("+ direction2 + ") from " +myEdge.getId());
            var id = myVertex[0].getId();
            if(vertex!=from){
                for (p=0;p<T.length;p++) {
                    if (T[p].getId()==id) {
                        var id_weight_i = getId_Weigth(id);
                        var id_weight_j = getId_Weigth(j.getId());
                        var weigthi = id_weight_i.weigth;
                        var weigthj = id_weight_j.weigth;
                        if (weigthi > weigthj + myWeigth) {
                            id_weight_i.weigth=weigthj + myWeigth;
                            id_weight_i.previous=vertex;
                        }
                    }
                }
            }
            else{
                for (q=0;q<id_weigth.length;q++) {
                    if (id_weigth[q].id==id) {
                        id_weigth[q].weigth=myWeigth;
                        id_weigth[q].previous=vertex;
                    }
                }
            }
        }
    }
}

function getId_Weigth(id) {
    for (l=0;l<id_weigth.length;l++) {
        if (id_weigth[l].id==id) 
            return id_weigth[l];
    }
    return null;
}

function getPath(){
    var validPath = true, temp = [], path = [];
    temp.push(to);
    var npm = getId_Weigth(to.getId());
    var v = npm.previous;
    while (v != from) {
        temp.push(v);
        if (v == null) {
            validPath = false;
            break;
        }
        npm = getId_Weigth(v.getId());
        v = npm.previous;
    }
    if (validPath == true) {
        temp.push(from);
        for (i = temp.length - 1; i >= 0; i--)
            path.push(temp[i]);
    } 
    return path;
}

function setWeigth_Direction(vertex){
    if (direction == "both"){
        setWeigth(vertex,"in","out");
        setWeigth(vertex,"out","in");
    }
    else if (direction == "in")
        setWeigth(vertex,"in","out");
    else
        setWeigth(vertex,"out","in");
}

function getPositionInT(id){
    for (l=0;l<T.length;l++) {
        if(T[l].getId()==id)
            return l;
    }
    return null;
}

Answer 3

我创建了这个 class 来查找 dijkstra 路径，包括按 rid 编号排除特定边列表的选项。

DijkstraExcl.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.tinkerpop.blueprints.Direction;
import com.tinkerpop.blueprints.Edge;
import com.tinkerpop.blueprints.Vertex;
import com.tinkerpop.blueprints.impls.orient.OrientGraph;

public class DijkstraExcl {

    private OrientGraph         g;          //grafh DB
    private Set<String>         S;          //visited rids
    private Set<String>         T;          //to visit rids
    private Map<String,Integer> f;          //f(i)     < @rid, weight_to_get_to_@rid >
    private Map<String,String>  J;          //J(i)     < @rid, previous_node_in_the_shortest_path >
    private String              eClass;     //edge class to use
    private String              prop;       //weight property to use on the edge

    public DijkstraExcl(OrientGraph g, String e, String p){
        this.g= g;
        this.eClass = e;
        this.prop = p;
        S = new HashSet<String>();
        T = new HashSet<String>();
        f = new HashMap<String,Integer>();
        J = new HashMap<String,String>();
    }


    //private methods

    //                  (Vertex start_vertex, Vertex dest_vertex, Direction.IN/OUT/BOTH, Set of edge rids to exclude) 
    private void findPath(Vertex startV, Vertex endV, Direction dir, Set<String> excludeEdgeRids){      

    //init
        S.clear();
        T.clear();
        f.clear();
        J.clear();

    //step1
        Iterator<Vertex> vertici = g.getVertices().iterator();
        while(vertici.hasNext()){
            Vertex ver = vertici.next();
            f.put(ver.getId().toString(), Integer.MAX_VALUE);
            T.add(ver.getId().toString());
        }
        f.put(startV.getId().toString(), 0);        //f(startV) = 0
        J.put(startV.getId().toString(), null);     //J(startV) = null
        T.remove(startV.getId().toString());        //startV visited => removed from T
        S.add(startV.getId().toString());           //                                and added in S



        Iterator<Vertex> near = startV.getVertices(dir, eClass).iterator();

        while(near.hasNext()){
            Vertex vicino = near.next();
            J.put(vicino.getId().toString(), startV.getId().toString());            //J(i) = startV
            f.put(vicino.getId().toString(), weight(startV.getId().toString(), vicino.getId().toString(),dir,excludeEdgeRids));     //f(i) = weight(startV, i)
        }

    //step2
        Boolean cont = false;
        Iterator<String> t = T.iterator();
        while(t.hasNext()){
            String i = t.next();
            if(f.get(i)!=Integer.MAX_VALUE){
                cont = true;
            }
        }
        while(cont){

            String j = startV.getId().toString();
            Integer ff = Integer.MAX_VALUE;
            t = T.iterator();
            while(t.hasNext()){
                String i = t.next();
                if(f.get(i)<=ff){
                    ff = f.get(i);
                    j = i;
                }
            }
            T.remove(j);
            S.add(j);
            if(T.isEmpty()){
                break;
            }

        //step3
            near = g.getVertex(j).getVertices(dir, eClass).iterator();

            while(near.hasNext()){
                Vertex vic = near.next();
                String i = vic.getId().toString();
                if( (T.contains(i)) && (f.get(i) > (f.get(j) + weight(j,i,dir,excludeEdgeRids))) ){
                    if(weight(j,i,dir,excludeEdgeRids)==Integer.MAX_VALUE){
                        f.put(i, Integer.MAX_VALUE);
                    }else{
                    f.put(i, (f.get(j) + weight(j,i,dir,excludeEdgeRids)));
                    }
                    J.put(i, j);
                }
            }

            //shall we continue?
            cont = false;
            t = T.iterator();
            while(t.hasNext()){
                String i = t.next();
                if(f.get(i)!=Integer.MAX_VALUE){
                    cont = true;
                }
            }
        }
    }

    private int weight(String rid_a, String rid_b, Direction dir, Set<String> excl){        //in case of multiple/duplicate edges return the lightest
        Integer d = Integer.MAX_VALUE;
        Integer dd;
        rid_b = "v["+rid_b+"]";

        if(excl==null){
            excl = new HashSet<String>();
        }
        Vertex a = g.getVertex(rid_a);

        Iterator<Edge> eS = a.getEdges(dir, eClass).iterator();
        Set<Edge> goodEdges = new HashSet<Edge>();
        while(eS.hasNext()){
            Edge e = eS.next();

            if((e.getProperty("out").toString().equals(rid_b) || e.getProperty("in").toString().equals(rid_b)) && !excl.contains(e.getId().toString())){
                goodEdges.add(e);
            }
        }
        Iterator<Edge> edges= goodEdges.iterator();
        while(edges.hasNext()){
            Edge e=edges.next();
                dd = e.getProperty(prop);
                if(dd<d){
                    d=dd;
                }
        }
        return d;
    }


    //public methods

    public List<Vertex> getPath (Vertex startV, Vertex endV, Direction dir, Set<String> exclECl){
        String j,i;
        List<Vertex> ppp = new ArrayList<Vertex>();
        List<Vertex> path = new ArrayList<Vertex>();

        findPath(startV, endV, dir, exclECl);
        i = endV.getId().toString();
        path.add(endV);
        if(f.get(endV.getId().toString()) == Integer.MAX_VALUE){
            return null;
        }
        while(!i.equals(startV.getId().toString())){
            j = J.get(i);
            if(j == null){
                return null;
            }
            path.add(g.getVertex(j));
            i = j;
        }
        for(int a=0, b=path.size()-1;a<path.size();a++, b--){
            ppp.add(a, path.get(b));
        }

        return ppp;
    }

    public List<String> getPathString (Vertex startV, Vertex endV, Direction dir, Set<String> exclECl){
        List<String> pathS = new ArrayList<String>();
        List<Vertex> path = getPath(startV, endV, dir, exclECl);

        if(path == null){
            return null;
        }
        for(Vertex v : path){
            pathS.add(v.getId().toString());
        }
        return pathS;
    }

    public Integer getWeight(Vertex startV, Vertex endV, Direction dir, Set<String> exclECl){
        findPath(startV, endV, dir,exclECl);
        return f.get(endV.getId().toString());
    }
}

她的是一个测试主：

public class test_dijkstra {

    public static void main(String[] args) {

        String nomeDb = "dijkstra_test";

        try {
            OServerAdmin serverAdmin = new OServerAdmin("remote:localhost/"+nomeDb).connect("root", "root");
            if(serverAdmin.existsDatabase()){  // il db esiste
                //connessione a db
                OrientGraph g = new OrientGraph("remote:localhost/"+nomeDb);
                DijkstraExcl d = new DijkstraExcl(g, "arco", "peso");
                Set<String> ex =new HashSet<String>();

                //------------------------------------------------
                Vertex start = g.getVertex("#9:0");
                Vertex end = g.getVertex("#9:5");
                ex.add("#12:4");
                Direction direction = Direction.BOTH;

                System.out.println(d.getPath(start,end,direction,ex));
                System.out.println(d.getPathString(start,end,direction,ex));
                System.out.println(d.getWeight(start,end,direction,ex));
                //------------------------------------------------

                //chiude db
                g.shutdown();
            }
            else{
                System.out.println("Il database '"+ nomeDb + "' non esiste");
            }
            serverAdmin.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }

}

及其输出：

[v[#9:0], v[#9:1], v[#9:2], v[#9:4], v[#9:5]]
[#9:0, #9:1, #9:2, #9:4, #9:5]
10

这是我的测试数据库的结构：

OrientDB：如何在忽略某些边的同时使用 dijkstra 函数查询图形

OrientDB: How to query a graph using dijkstra function while ignoring some edges

graph

dijkstra

orientdb