Как использовать поиск графа MongoDB?

Question

Это примеры документов из моей коллекции, скажем, она называется bus_routes:

{
   "_id":{
      "$oid":"56e9b39c732b6122f878576ba"
   },
   "src_busStop":"A",
   "dst_busStop":"B",
   "bus":"7318 FAF"
}

{
   "_id":{
      "$oid":"56e9b39c732b6122f878576bb"
   },
   "src_busStop":"B",
   "dst_busStop":"C",
   "bus":"7319 FAF"
}

{
   "_id":{
      "$oid":"56e9b39c732b6122f878576bc"
   },
   "src_busStop":"C",
   "dst_busStop":"D",
   "bus":"7320 FAF"
}

Я хочу выбрать все соединения (все шины) между городами A и D, где максимальное количество переводов - 3. Думаю, мне следует использовать $graphLookup, но я не знаю, как это реализовать. Заранее спасибо.

Answer 1

Оператор graphLookup лучше всего работает при наличии единственного пути через граф.

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

На этих этапах вы получите все маршруты, начинающиеся с буквы "A".

maxDepth:2 вернется до 3 передачи, restrictSearchWithMatch:{dst:{$ne:"A"}} будет игнорировать любые маршруты, которые возвращаются к «A».

     {$match:{src_busStop:"A"}},
     {$graphLookup:{
        from:"bus_routes",
        startWith:"$dst_busStop",
        connectFromField:"dst_busStop",
        connectToField:"src_busStop",
        as:"routes",
        maxDepth:2,
        depthField:"transfers",
        restrictSearchWithMatch:{dst:{$ne:"A"}}
     }}

Обратите внимание, что не существует простого способа ограничить это путями, заканчивающимися на "D". Массив "route", который заполняется graphLookup, будет содержать все документы "bus_routes", которые могут быть достигнуты в течение 3 передач из "A".

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

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

Вот пример конвейера для поиска маршрутов от «A» до «D». Это немного грубо для меня, но у меня пока нет более элегантного решения. Шаги:

1. Выбор всех маршрутов, исходящих из начальной точки
2. Сохранение исходного документа в поле «маршрут» для последующего использования
3. Поиск всех исходящих маршрутов со следующей достижимой станции сохраните в поле «firstxfer»
4. Откатите первые предложения, чтобы мы могли рассмотреть каждый маршрут отдельно
5. Отменить все маршруты, которые go вернулись туда, откуда они пришли
6. Повторите 3-5, чтобы сгенерировать второй и третий.
7. Объедините исходный документ и каждый документ переноса в обратном порядке в поле «маршрут».
8. Сократите массив, исключив любые маршруты после пункт назначения достигнут, и в обратном порядке
9. Сгруппируйте с помощью addToSet для устранения дублирующих маршрутов
10. Снова раскрутите маршруты, чтобы мы могли отсортировать
11. Добавьте количество маршрутов, необходимое в " поле "Автобусы"
12. Сортировка так, чтобы самые короткие маршруты были на первом месте

db.bus_routes.aggregate([
    {$match:{src_busStop:"A"}},
    {$addFields:{route:["$$ROOT"]}},
    {$lookup:{from:"bus_routes",localField:"dst_busStop",foreignField:"src_busStop",as:"firstxfer"}},
    {$unwind:"$firstxfer"},
    {$match:{"firstxfer.dst_busStop":{$ne:"A"}}},
    {$addFields:{firstxfer:{$cond:[{$eq:["D","$firstxfer.src_busStop"]},[],"$firstxfer"]}}},
    {$lookup:{from:"bus_routes",localField:"firstxfer.dst_busStop",foreignField:"src_busStop",as:"secondxfer"}},
    {$unwind:"$secondxfer"},
    {$match:{"secondxfer.dst_busStop":{$ne:"A"}}},
    {$addFields:{secondxfer:{$cond:[{$eq:["D","$secondxfer.src_busStop"]},[],"$secondxfer"]}}},
    {$lookup:{from:"bus_routes",localField:"secondxfer.dst_busStop",foreignField:"src_busStop",as:"thirdxfer"}},
    {$unwind:"$thirdxfer"},
    {$addFields:{thirdxfer:{$cond:[{$eq:["D","$thirdxfer.src_busStop"]},[],"$thirdxfer"]}}},
    {$project:{
        route:["$thirdxfer","$secondxfer","$firstxfer","$route"]
    }},
    {$match:{"route.dst_busStop":"D"}},
    {$project:{
        route:{
            $reduce:{
                input:"$route",
                initialValue:[],
                in:{$cond:[
                           {$or:[{$eq:["D","$$this.dst_busStop"]},{$gt:[{$size:"$$value"},0]}]},
                           {$concatArrays:[["$$this"],"$$value"]},
                           "$$value"
                           ]}
            }
        }
    }},
    {$group:{
        _id:null,
        route:{$addToSet:"$route"}
    }},
    {$unwind:"$route"},
    {$addFields:{ buses:{$size:"$route"}}},
    {$sort:{buses:1}}
])

Я настроил набор тестовых данных на Playground до продемонстрировать это.