Нептун - Как получить расстояние до всех узлов с пропорциональными весами gremlin

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

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    sack().
.....12>    sum()     

==>0.768170426065163         

Запрос начинается с Джейн и продолжается до тех пор, пока не будут проверены все пути к Джерри Д. По пути для каждого переходника поддерживается sack, содержащий вычисленные значения веса для каждой взаимосвязи, умноженные вместе. Вычисление в строке 6 находит все возможные значения веса ребра, исходящие из предыдущей вершины, и шаг math в строке 7 используется для деления веса на текущем ребре на эту сумму. В самом конце каждый из вычисленных результатов складывается в строке 12. Если вы удалите последний sum шаг, вы увидите промежуточные результаты.

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    sack()

==>0.2142857142857143
==>0.3508771929824561
==>0.2030075187969925   

Чтобы увидеть пройденные маршруты, к запросу можно добавить path шаг.

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','jerryd')).
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight'),
.....16>        sack()).fold()) 

==>[[jane,10,thomas,90,jerryd],0.2142857142857143]
==>[[jane,20,lisa,100,jerryd],0.3508771929824561]
==>[[jane,20,lisa,90,thomas,90,jerryd],0.2030075187969925]   

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

gremlin>  g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    until(has('name','thomas')).
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight'),
.....16>        sack()).fold())    

==>[[jane,10,thomas],0.3333333333333333]
==>[[jane,20,lisa,90,thomas],0.3157894736842105]  

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

g.withSack(1).V().
   has('name','jane').
   repeat(outE().
          sack(mult).
            by(project('w','f').
              by('weight').
              by(outV().outE().values('weight').sum()).
              math('w / f')).
          inV().
          simplePath()).
   until(has('name','thomas')).
   local(
     union(
       path().
         by('name').
         by('weight'),
       sack()).fold().tail(local)).  
    sum() 
  
==>0.6491228070175439  

Если что-то из этого неясно или я неправильно понял формулу, сообщите мне.

ИЗМЕНИТЬ, чтобы добавить

Чтобы найти результаты для всех людей, доступных от Джейн, мне пришлось немного изменить запрос. Знак unfold в конце предназначен только для облегчения чтения результатов.

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    emit().
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight').unfold(),
.....16>        sack()).fold()).
.....17>        group().
.....18>          by(tail(local,2).limit(local,1)).
.....19>          by(tail(local).sum()).
.....20>        unfold()

==>jerryd=0.768170426065163
==>wyd=0.23182957393483708
==>lisa=0.6666666666666666
==>thomas=0.6491228070175439    

На последнем group шаге в строке 17 результаты path используются для расчета общей благосклонности для каждого найденного уникального имени. Чтобы увидеть пути, вы можете запустить запрос, убрав group шаг.

gremlin> g.withSack(1).V().
......1>    has('name','jane').
......2>    repeat(outE().
......3>           sack(mult).
......4>             by(project('w','f').
......5>               by('weight').
......6>               by(outV().outE().values('weight').sum()).
......7>               math('w / f')).
......8>           inV().
......9>           simplePath()).
.....10>    emit().
.....11>    local(
.....12>      union(
.....13>        path().
.....14>          by('name').
.....15>          by('weight').unfold(),
.....16>        sack()).fold())

==>[jane,10,thomas,0.3333333333333333]
==>[jane,20,lisa,0.6666666666666666]
==>[jane,10,thomas,50,wyd,0.11904761904761904]
==>[jane,10,thomas,90,jerryd,0.2142857142857143]
==>[jane,20,lisa,90,thomas,0.3157894736842105]
==>[jane,20,lisa,100,jerryd,0.3508771929824561]
==>[jane,20,lisa,90,thomas,50,wyd,0.11278195488721804]
==>[jane,20,lisa,90,thomas,90,jerryd,0.2030075187969925]    

Этот ответ довольно элегантен и лучше всего подходит для среды, связанной с Neptune и Python. Предлагаю вторую для справки, на случай, если другие столкнутся с этим вопросом. С того момента, как я увидел этот вопрос, я мог только представить, что он решается с помощью VertexProgram в режиме OLAP с GraphComputer. В результате мне было трудно думать об этом по-другому. Конечно, для использования VertexProgram требуется язык JVM, такой как Java, и он не будет работать напрямую с Neptune. Я полагаю, что моим ближайшим обходным решением было бы использовать Java, взять subgraph() из Нептуна и затем локально запустить пользовательский VertexProgram в TinkerGraph, что было бы довольно быстро.

В более общем смысле, без требований Python / Neptune преобразование алгоритма в VertexProgram - неплохой подход в зависимости от характера графика и количества данных, которые необходимо пройти. Поскольку по этой теме не так много контента, я подумал, что предлагаю здесь ядро ​​кода для этого. Это его внутренности:

        @Override
        public void execute(final Vertex vertex, final Messenger<Double> messenger, final Memory memory) {
            // on the first pass calculate the "total favor" for all vertices
            // and pass the calculated current favor forward along incident edges
            // only for the "start vertex" 
            if (memory.isInitialIteration()) {
                copyHaltedTraversersFromMemory(vertex);

                final boolean startVertex = vertex.value("name").equals(nameOfStartVertrex);
                final double initialFavor = startVertex ? 1d : 0d;
                vertex.property(VertexProperty.Cardinality.single, FAVOR, initialFavor);
                vertex.property(VertexProperty.Cardinality.single, TOTAL_FAVOR,
                        IteratorUtils.stream(vertex.edges(Direction.OUT)).mapToDouble(e -> e.value("weight")).sum());

                if (startVertex) {
                    final Iterator<Edge> incidents = vertex.edges(Direction.OUT);
                    memory.add(VOTE_TO_HALT, !incidents.hasNext());
                    while (incidents.hasNext()) {
                        final Edge incident = incidents.next();
                        messenger.sendMessage(MessageScope.Global.of(incident.inVertex()),
                                (double) incident.value("weight") /  (double) vertex.value(TOTAL_FAVOR));
                    }
                }
            } else {
                // on future passes, sum all the incoming "favor" and add it to
                // the "favor" property of each vertex. then once again pass the
                // current favor to incident edges. this will keep happening 
                // until the message passing stops.
                final Iterator<Double> messages = messenger.receiveMessages();
                final boolean hasMessages = messages.hasNext();
                if (hasMessages) {
                    double adjacentFavor = IteratorUtils.reduce(messages, 0.0d, Double::sum);
                    vertex.property(VertexProperty.Cardinality.single, FAVOR, (double) vertex.value(FAVOR) + adjacentFavor);

                    final Iterator<Edge> incidents = vertex.edges(Direction.OUT);
                    memory.add(VOTE_TO_HALT, !incidents.hasNext());
                    while (incidents.hasNext()) {
                        final Edge incident = incidents.next();
                        messenger.sendMessage(MessageScope.Global.of(incident.inVertex()),
                                adjacentFavor * ((double) incident.value("weight") / (double) vertex.value(TOTAL_FAVOR)));
                    }
                }
            }
        }

Вышеупомянутое затем выполняется как:

ComputerResult result = graph.compute().program(FavorVertexProgram.build().name("jane").create()).submit().get();
GraphTraversalSource rg = result.graph().traversal();
Traversal elements = rg.V().elementMap();

и что обход элементов дает:

{id=0, label=person, ^favor=1.0, name=jane, ^totalFavor=30.0}
{id=2, label=person, ^favor=0.6491228070175439, name=thomas, ^totalFavor=140.0}
{id=4, label=person, ^favor=0.6666666666666666, name=lisa, ^totalFavor=190.0}
{id=6, label=person, ^favor=0.23182957393483708, name=wyd, ^totalFavor=0.0}
{id=8, label=person, ^favor=0.768170426065163, name=jerryd, ^totalFavor=0.0}