Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Привет.

В продолжне архивариуса https://www.sql.ru/forum/1282300/chetvergovyy-arhivarius

Возникла прикладная задача из двух частей.

Часть 1. Схлопывание мостов.

Дано: орграф произвольного вида. 50 тысяч вершин и примерно 260 тысяч рёбер.
По статистике которую я собирал каждая вершина имеет примерно 5 исходящих ребер.

Необходимо: программно удалить рёбра типа (4)->(5) как на картинке.
После удаления ребра - вершины (4) и (5) схлопываются и создаётся новая
вершина с новым идентификатором из свободных. Например (50000).


При этом входящие связи в (4) и исходящие из (5) сохраняются.

Часть 2. Разгон

Оптимизировать этот-же алгоритм с учотом мультипоточности.

Исходные данные.

Еще не готовы. Но я опубликую чуть позже набор ребер со связями в текстовом виде (CSV)

Картинке соотвествует примерно такой файл.
1,4
2,4
3,4
4,5
5,6
5,7
....

Ребра имеют ориентацию поэтому 1,4 и 4,1 это разные рёбра.

Приветствуется

- любая реализация на Java / Kotlin / Scala.
- мультипоточка, стримы, коллекции
- примитивы синхронизации

Go-go писать код.

К сообщению приложен файл. Размер - 45Kb
11 сен 20, 21:03    [22195620]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2311
mayton,

Схлопывать только вершины соединенные одной веткой? А какая скорость обработки должна быть по ТЗ? 50 тысяч вершин довольно небольшой объем там особо мультипоточность даром не упала так как все разместится в памяти все можно через хештейбл реализовать.
11 сен 20, 21:48    [22195632]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Попробуем.
11 сен 20, 21:49    [22195634]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Данные готовы. Первый том.

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part01.rar - 140Kb) cкачать
11 сен 20, 21:54    [22195636]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Второй

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part02.rar - 140Kb) cкачать
11 сен 20, 21:54    [22195637]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Хопа.

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part03.rar - 140Kb) cкачать
11 сен 20, 21:55    [22195638]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Еще

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part04.rar - 140Kb) cкачать
11 сен 20, 21:55    [22195639]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
И еще

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part05.rar - 140Kb) cкачать
11 сен 20, 21:55    [22195640]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Фух. Последний.

Пробуйте.

К сообщению приложен файл (war-and-society-1-2-3-4-simple-edges.sorted.part06.rar - 103Kb) cкачать
11 сен 20, 21:56    [22195642]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
UP. Any updates?
12 сен 20, 19:00    [22195925]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

Откуда: Bay Area, CA
Сообщений: 2311
mayton
UP. Any updates?


можно по подробней, какой файл финальный и сколько там данных?

На мой взгляд там довольно прозрачная структура данных намечается, все вершины где входящий один будут всхлопнуты, что довольно быстро определяется. по О натации алгоритм должен сработать за O(N+m) времени где m - число точек всхлапывания, N - все точки.

Не совсем ясно допускаются ли паралельные дуги и петли т.е. когда две точки графа соединены двумя одинаково ориентированными ребрами и когда дуга (ребро с направлением) делает петлю т.е. к примеру 4,4

Но вцелом очень козырная задача... редкая находка в наши дни борьбы за деньзнаки.
13 сен 20, 00:31    [22196003]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Я опубликовал финальный файл. В нем 48955 вершин и 258215 связей между ними.

Я пытался решать эту задачу используя матрицу смежности. В родительском топике. Но мне не хватило
памяти для массива. Произведения 50000 на 50000 давало величину в штуках больше чем индекс
массива в Java. И это только первое ограничение. И если массив я просто преодолел разбивая
матрицу на слои как торт. То второе ограничение - медленная скорость поиска смежных вершин
по матрице - я не преодолел.

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

Фрагмент вершины
public class Vertex implements Serializable {

    static final long serialVersionUID = 1L;

    // Key fields
    private String id;

    // Non-key fields
    private List<Edge> outgoingEdges = new ArrayList<>();
    private List<Edge> incomingEdges = new ArrayList<>();

    public Vertex(@NotNull String id) {
        this.id = id;
    }

    public Vertex() {
        // For serialization
    }

    // Incoming edges

    void addIncomingEdge(@NotNull Edge edge) {
        checkArgument(edge.getV2() != this, "Unable to link edge " + edge.toString() + " because of illegal V2 value");
        incomingEdges.add(edge);
    }
13 сен 20, 11:41    [22196069]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
По алгоритму. Что я еще не учел? Возможно кейсов схлопывания больше чем я нарисовал на картинке.
Возможно петли и циклы не запрещают нам это сделать. Я чуть позже приаттачу еще одну картинку
где есть частные случаи.
13 сен 20, 11:49    [22196074]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Alexander A. Sak
Member

Откуда: Омск
Сообщений: 1113
Базистам эту задачу решать можно?

Сделать таблицу WAR_AND_SEC(A number, B number), залить туда CSV, наделать апдейтов и выгрузить обратно.

Для H2 DB создание+загрузка выглядит так:
create table WAR_AND_SEC(a bigint, b bigint) as select * from csvread('PATH_TO_CSV', 'a,b')


Кандидаты на схлопывание:
select a, b from WAR_AND_SEC where a in (select a from WAR_AND_SEC group by a having count(*)=1)


Схлопывание - это обновление A и B новыми значениями плюс удаление записи.
13 сен 20, 12:20    [22196082]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Да. Да. Базистам это решать можно. Всем можно. Но я просто по инерции продолжал тему оптимизации текстовых
литературных графов. Просто сама постановка была настолько интересно что я решил ее очистить от ненужной
шелухи и выдать отдельным топиком как чистую алгоритмизацию на Java.

Реляционки обычно плохо справляются с графовыми задачами но если вы это сделаете - то у нас будет
еще и повод просто сравнить время отклика для двух одинаковых исходных данных в Pure-Java и H2-Java.
13 сен 20, 12:27    [22196086]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Еще несколько кейсов. На картинке.

Case (1)

Одно-направленная цепочка смежных вершин (chain) должна быть схлопнута в 1 вершину если нет
прочих входящих и исходящих ребер в середине этой цепочки.

Case (2)

Дву-направленная цепочка не схлопыватеся.

Case (3)

Вот такой вод ориентированный подграф схлопывает цепочки { 1->2->3 } и создает новую вершину 9
Это простой случай.

А вот с {3 -> 4 -> 5 -> 6 } несмотря на то что образуют цикл тем не менее могут быть схлопнуты в части
{4 -> 5-> 6 } т.к. топологически мы не нарушаем структуру которая была. Просто выбрасываем лишнее.

И на рисунке (4) - результат.

К сообщению приложен файл. Размер - 130Kb
13 сен 20, 13:45    [22196115]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Ну что. Идей нету? Брейншторм?

Algorithm: GraphEdgeSimplification-alg-0.1

1.Дано. Орграф. G(V,E),
2.Для всех ребер. Ei={Vin,Vout}, удалить ребро если вершины входящие
в Vin и исходящие из Vout дают в пересечении пустое множество.
3.Повторять пункт (2) для всех ребер пока граф изменяется.
13 сен 20, 21:06    [22196241]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Zzz79
Member

Откуда:
Сообщений: 805
mayton,вот и охота тебе этой дичью заниматься)

ты мне деда моего напоминаешь) уже давно телеки плоские,а он все в ламповых ковыряется,чего то там пояет,модернизирует)

ну вот твои эти графы ? нахуа они в современном программировании?так чисто на собесе собесера унизить?)

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

вся эта олд скул школа говно знаний - типо реляционой алгебры,хрень про бинарны дерьвья - она вся в прошлом ,как и пилоты ,которые руками штурвал крутили)

посади пилота из прошлого в современный боинг- он с места его не сдвинет) так и олд скул прогеры - тупо пасуют - у меня живой пример - чувак реально в IT 20 лет - но дуб дубом и скорей всего будет уволен
13 сен 20, 22:48    [22196263]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Сидение на этом форуме несет два смысла. Первое - это решать продуктовые проблемы. Чем ты занят.

И второе - это просто for fun. То чем занят я.
13 сен 20, 22:55    [22196265]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
забыл ник
Member

Откуда:
Сообщений: 3415
Zzz79,

Тебя просто к нормальным задачам не подпускают. Хотя ты прав в том что такие задачи достаются меньшинству. Но чтобы их получить нужно иметь некий уровень знаний.
14 сен 20, 00:09    [22196279]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10682
Zzz79
и охота тебе этой дичью заниматься)
Повторю ещё раз: "Сорок лет ума нет и не будет". И это - не про mayton
14 сен 20, 07:07    [22196312]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10682
забыл ник
просто к нормальным задачам не подпускают.
Просто фигни больше и кто-то должен делать и её.
14 сен 20, 07:08    [22196313]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

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

Сложность "тупого рекурсивного" поиска маршрута прикидочно может достигать 50 000 (кол-во нод) x 5 (путей из каждой ноды) => до 50 - 250 тысяч рекурсий/циклов, и отжирать примерно столько же стека. Теоретически возможно тут нужно было бы 50 000 возводить в степень 5-ки, но это если искать все маршруты. Нам же нужен только факт, что такой маршрут есть, т.е. если мы повторно входим в ноду, то поиск сразу же прекрашаем.

Результат работы массив из 5 ячеек, есть ли (сколько) маршрутов в соседние ячейки. Плюс временный массив на 50 000 элементов, где хранится были ли мы уже в этой ноде.

Таких поисков нужно запускать 50 000 раз.

Поскольку схлопывание может быть рекурсивным (например граф вырождается в банальное кольцо), алгоритм возможно рекурсивно запускать до 50 000 раз.

Время работы одного прогона на Java (при оптимизации), я бы оценил от 10 000 секунд, т.е. где-то 3-10 часов (железо уровня AWS tiny instance) для одного прогона. Но это без рекурсивного схлопывания. При многопроцессорности кратно меньше.

Для рекурсивном схлопывание, наверное, нужно посчитать один раз матрицу N x N ( 50 x 50 = 2 500 000 000 элементов) кол-во маршрутов из A в B. Т.к. при схлопывание кол-во марщрутов из A и B изменится не должно (мне так кажется), то не нужно будет перевычислять маршруты.

Кол-во маршрутов из A в B нам интересно только 0 - нет маршрута, 1 - толкьо один маршрут, 2 - два и _более_ маршрута (схлопывать нельзя).
14 сен 20, 14:03    [22196566]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 9091
mayton

...
Фрагмент вершины
public class Vertex implements Serializable {
...
    private List<Edge> outgoingEdges = new ArrayList<>();
    private List<Edge> incomingEdges = new ArrayList<>();
...



Крайне не оптимально. Я бы вершины кодировал бы просто целым числом в массиве (т.е. до 2 млр. вершин), сответственно outgoingEdges, incomingEdges можно сделать просто

int[] outgoingVertex;

Аналогично и хранение результатов в стеке, все возвраты - тупо int. Объекты даром не нужны. Коллекции - только оптимизированные (не стандартные!) для работы с примитивными типами.
14 сен 20, 14:04    [22196567]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49367
Leonid Kudryavtsev
mayton

...
Фрагмент вершины
public class Vertex implements Serializable {
...
    private List<Edge> outgoingEdges = new ArrayList<>();
    private List<Edge> incomingEdges = new ArrayList<>();
...



Крайне не оптимально. Я бы вершины кодировал бы просто целым числом в массиве (т.е. до 2 млр. вершин), сответственно outgoingEdges, incomingEdges можно сделать просто

int[] outgoingVertex;

Аналогично и хранение результатов в стеке, все возвраты - тупо int. Объекты даром не нужны. Коллекции - только оптимизированные (не стандартные!) для работы с примитивными типами.

Разумно. Согласен. Я сейчас сразу менять код не буду. Иначе у меня 80% кода надо будет срочно переписать.

Но я ставлю.

TODO: Leonid proposes to get rid of Edges instead of primitives.


В чем был поинт хранения ребер как объектов. В базовой постановке https://www.sql.ru/forum/1282300/chetvergovyy-arhivarius
ребро хранило вес. Тоесть количество пробегов по нему. И здесь в этой задаче оптимизации оно стало рудиментом.
Хотя я планировал и вертексы и рёбра сделать генериками чтобы внутрь еще что-то кодкладывать. Разные метки
для алгоритмов типа дейсктры и возможно признак блокировки для мультипоточки.

При объектах (references) накладные расходы на храение - одинаковы что для вершин что для ребер.

Идентификатор vertex у меня был строковый. String. Он хранил токен. Или строку из литературного произведения.
А для данной постановки я просто искусственно очистил все id-шники и заменил их на sequence целых чисел.

Сообщение было отредактировано: 14 сен 20, 14:18
14 сен 20, 14:15    [22196582]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Java Ответить