Обход на основе нескольких вершин

У меня есть граф в OrientDB с вершинами Area и Place с ребрами visited. Ваш средний путь составляет Area > visited > Place > visited > Place > visited > Place > visited > Place и так далее. Он отслеживает, какие места посетил пользователь после предыдущего. visited содержит ГГГГммДД datestamp.

Я пытаюсь узнать все Area вершин на основе произвольных Place вершин за определенный день - т.е. я хочу знать, из каких областей пользователи пришли в определенное место после посещения определенного места сначала.

Переход от любого отдельного Place на пути был бы легким, но мне нужно следовать по пути только для определенного datestamp. Что я сделал, так это то, что я создал индекс для datestamp, чтобы быстро получить дневные visited ребра, а затем нашел тот, у которого есть in к первому Place. Однако теперь я не могу понять, как создать быстрый запрос, который находит все Area вершин на основе первого Place, а также убеждается, что путь содержит и второй Place. Я могу получить путь между первым и вторым Place через shortestPath(), но у меня все еще есть та же проблема с расширением пути для включения Area вершин.

Я нашел некоторую теорию по этому вопросу, но если бы кто-нибудь мог указать мне правильное направление, как использовать OrientDB для этого вместо чистой теории графов, я был бы очень признателен - я работаю над этим на прошлой неделе. Первоначально это было сделано с помощью грубой силы путем обхода всего и последующего выбора, но по мере роста базы данных это явно не является устойчивым.


graph graph-traversal orientdb
person jimmy    schedule 03.12.2015    source источник
comment
Можете добавить скрин схемы? Можете ли вы объяснить это лучше, пожалуйста?   -  person Michela Bonizzi    schedule 03.12.2015
comment
Можете ли вы уточнить, что вы не понимаете в схеме? Это все в первом абзаце, и, честно говоря, я не знаю, как объяснить это лучше, не зная, что непонятно. Это две вершины Area и Place и посещенное ребро, соединяющее Area с Place и Place с Place.   -  person jimmy    schedule 03.12.2015
comment
Что содержит место? Ссылка на пользователя? Сама метка времени? Или временная метка на краях?   -  person Luigi Dell'Aquila    schedule 03.12.2015
comment
Place — это статическая запись места, например, Bob's Hamburger Joint. Площадь — это статическая запись для такой географической области, как Бронкс, штат Нью-Йорк. Временные метки существуют только в краях и создаются при посещении пользователем Places. Ссылка на пользователя также находится по краям, но я не хотел приводить ее здесь, потому что в этом случае мы объединяем все пути независимо от пользователя, чтобы создать список областей на основе произвольных мест.   -  person jimmy    schedule 03.12.2015

Ответы (3)


arrow_upward
0
arrow_downward

Я создал три вершины «Область», «Место» и «Пользователь», а также два «посещенных» и «размещенных» ребра, где метка даты является свойством «посещенного» края. Таким образом, вам не нужно каждый раз вставлять пользователя в качестве свойства на краю.

введите здесь описание изображения

person LucaS    schedule 04.12.2015

arrow_upward
0
arrow_downward

Редактировать

Попробуйте эту функцию JavaScript с тремя параметрами (места, дата, свойство)

var g=orient.getGraph();
var myPlaces=places.substring(1,places.length-1).split(",");
var b=g.command("sql","select from Area");
var result=[];
if(checkPlaces){
    for(i=0;i<b.length;i++){
        var listPlaces=[];
        for(ind=0;ind<myPlaces.length;ind++){
            listPlaces.push(myPlaces[ind]);
        }
        if(search(b[i],listPlaces)){
            result.push(b[i]);
        }
    }
}
return result;

function checkPlaces() {
    for(index=0;index<myPlaces.length;index++){
        var place=g.command("sql","select from Place where "+ propertyPlace + "='"+myPlaces[index]+"'");
        if(place.length==0){
            return false;
        }
    }
    return true;
}

function checkDate(edge){
  var datestamp=edge.getRecord().field("datestamp");
  var year=datestamp.getYear()+1900;
  var month=datestamp.getMonth()+1;
  var day=datestamp.getDate();
  var app=date.split("-");
  var myYear=parseInt(app[0]);
  var myMonth=parseInt(app[1]);
  var myDay=parseInt(app[2]);
  if(year==myYear && month==myMonth && day==myDay){
    return true;
  }
  return false;
}


function search(v,places){
    var edge=v.getRecord().field("out_visited"); 
    if(edge!=null){
        var edgeIterator=edge.iterator();
        while(edgeIterator.hasNext()){
            var edge = edgeIterator.next();
            if (checkDate(edge)) {
                var v1 = edge.field("in");
                if(v1!=null){
                    var name = v1.field(propertyPlace);
                    for(j=0;j<places.length;j++){
                        if(name==(places[j])) {
                            places.splice(j, 1);
                            break;
                        }   
                    }
                    if(places.length==0){ 
                        return true;
                    }
                    else if(search(v1,places)){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

Используя следующую команду

select expand(result) from (select myFunction("[place1,place2]","2015-12-03","name") as result)

Дайте мне знать, если это работает

person Alessandro Rota    schedule 03.12.2015
comment
Да, именно так. Однако проблема немного сложнее. Иногда у меня есть несколько мест в качестве требований, и мне нужно получить только те области, где эти места находятся на пути. Например, если бы у меня были place1 и place2 в качестве требований к местам, а отметка времени 2015-12-03, я должен получить только area1. - person jimmy; 03.12.2015
comment
Место 2 и место 1 должны быть посещены последовательно или нет - person Alessandro Rota; 04.12.2015

arrow_upward
0
arrow_downward

Это не решение именно этой проблемы, а обходной путь, который я придумал. Вдохновленный Orientdb получает последнюю вершину из каждого путь при обходе по свойству ребра

Я изменил структуру, так что Area теперь создается для каждого посещения, а не является статическим, и также включает временную метку yyyymmdd. Теперь я могу использовать Area для запуска запроса и использовать visited ребер для получения Place вершин только на определенную дату.

Вот запрос:

SELECT $path, $depth FROM (
    TRAVERSE * FROM (
        SELECT outE('visited') FROM (
            SELECT EXPAND(rid) FROM INDEX:area.dt WHERE key = 20151205
        )
    ) WHILE (@class = 'visited' AND dt = 20151205) OR @class = 'place') 
WHERE @class = 'place' AND NOT (outE() contains (dt=20151205))

Это возвращает правильные пути с вершинами и ребрами, чтобы вы могли убедиться, что это только для определенного дня. Однако обратите внимание, что Area не содержится в пути, и мне все еще нужно выяснить, как это сделать, но если вы хотите, вы можете просто пройти первое ребро visited назад по пути и получить его таким образом.

person jimmy    schedule 06.12.2015