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, например, вершинно-ориентированные итерации. Начиная с исходной вершины, вы можете итеративно расширять пути, один переход на супершаг. После получения пути вершина добавляет свой идентификатор к пути и передает его своим исходящим соседям. Если у вершины нет исходящих соседей, то она печатает / сохраняет путь и не распространяет его дальше. Чтобы избежать циклов, вершина может также проверить, существует ли ее ID в пути, перед распространением. Функция вычисления может выглядеть так:

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 для целых, но остерегайтесь затрат, если у вас плотный граф с большим диаметром. Если вам не нужны сами пути, но вы заинтересованы только в достижимости или кратчайших путях, то существуют более эффективные алгоритмы.