Flink Gelly Path/Trail Usecase

Question

Наша команда является новой для Gelly api. Мы стремимся реализовать простой пример использования, в котором будут перечислены все пути, происходящие из начальной вершины - например,

края входного файла CSV является 1,2 \ n2,3 \ n3,4 \ n1,5 \ n5,6

требуемая мощность будет (полный путь, который начинается с 1) 1, 2,3,4 \ n1,5,6

Может кому-то помочь.

Answer 1

Вы можете использовать один из Gelly's iteration abstractions, например. вертекс-центричные итерации. Начиная с исходной вершины, вы можете итеративно расширять пути, по одному прыжку за суперпец. После получения пути вершина добавляет свой идентификатор к пути и распространяет его на своих исходящих соседей. Если вершина не имеет исходящих соседей, то она печатает/сохраняет путь и не распространяет его дальше. Чтобы избежать циклов, вершина также может проверить, существует ли ее идентификатор в пути до распространения. Функция вычисления может выглядеть следующим образом:

public static final class ComputePaths extends ComputeFunction<Integer, Boolean, NullValue, ArrayList<Integer>> { 

    @Override 
    public void compute(Vertex<Integer, Boolean> vertex, MessageIterator<ArrayList<Integer>> paths) { 
     if (getSuperstepNumber() == 1) { 
      // the source propagates its ID 
      if (vertex.getId().equals(1)) { 
       ArrayList<Integer> msg = new ArrayList<>(); 
       msg.add(1); 
       sendMessageToAllNeighbors(msg); 
      } 
     } 
     else { 
      // go through received messages 
      for (ArrayList<Integer> p : paths) { 
       if (!p.contains(vertex.getId())) { 
        // if no cycle => append ID and forward to neighbors 
        p.add(vertex.getId()); 
        if (!vertex.getValue()) { 
         sendMessageToAllNeighbors(p); 
        } 
        else { 
         // no out-neighbors: print p 
         System.out.println(p); 
        } 
       } 
       else { 
        // found a cycle => print the path and don't propagate further 
        System.out.println(p); 
       } 
      } 
     } 
    } 
} 

В этом коде я предположил, что у вас есть предварительно обработанные вершины, чтобы отметить те, которые не имеют затраченных соседей с «истинной» стоимости. Вы можете, например, используйте graph.outDegrees(), чтобы найти их.

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