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

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

В продолжне архивариуса 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
Сообщений: 2296
mayton,

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

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

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

К сообщению приложен файл (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
Сообщений: 48895
Второй

К сообщению приложен файл (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
Сообщений: 48895
Хопа.

К сообщению приложен файл (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
Сообщений: 48895
Еще

К сообщению приложен файл (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
Сообщений: 48895
И еще

К сообщению приложен файл (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
Сообщений: 48895
Фух. Последний.

Пробуйте.

К сообщению приложен файл (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
Сообщений: 48895
UP. Any updates?
12 сен 20, 19:00    [22195925]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

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


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

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

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

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

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

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

Сделать таблицу 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
Сообщений: 48895
Да. Да. Базистам это решать можно. Всем можно. Но я просто по инерции продолжал тему оптимизации текстовых
литературных графов. Просто сама постановка была настолько интересно что я решил ее очистить от ненужной
шелухи и выдать отдельным топиком как чистую алгоритмизацию на Java.

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

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

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
Сообщений: 48895
Ну что. Идей нету? Брейншторм?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность "тупого рекурсивного" поиска маршрута прикидочно может достигать 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

Откуда:
Сообщений: 8927
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
Сообщений: 48895
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]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

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


На скорую рука как-то так. Правда цепочки типа 1->2->3->4 коллапсируют в пустое множество

import scala.annotation.tailrec

val data = {
  scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
    .map { l =>
      val arr = l.split(",").map(_.toInt)
      arr(0) -> arr(1)
    }.toArray
}



@tailrec
def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {
  val inputs = data.groupBy(_._2).map { case (k, v) => k -> v.map(_._1) }
  val outputs = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

  val singleLinks = outputs.filter(_._2.length == 1).filter{case (from,Array(to)) => Array(from).toList == inputs(to).toList }.map { case (from, Array(to)) => from -> to}

  if (singleLinks.isEmpty) {
    return data
  }

  val newData = collection.mutable.HashSet[(Int, Int)]()

  data.foreach { case (from, to) =>
    // нашли связь 1вых->1вх
    if (singleLinks.get(from) == Option(to)) {
      // перенести исходящие узлы удаляемго узла к преды дущему
      outputs.get(to).foreach { outs =>
        outs.foreach { out =>
          newData.add((from, out))
        }
      }
    } else {
      if (!singleLinks.exists { case (f, t) => (t == from)} ) {
        newData.add((from, to))
      }
    }
  }

  processGraph(newData.toArray)

}

processGraph(data)
14 сен 20, 15:15    [22196650]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

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

Я думаю что мы можем уйти от рекурсии с глубиной 50 тысяч и DFS. Я надеялся что последовательно удаляя 1 ребро за другим
мы будем быстро возвращаться на старт. И вместо 50 тыщ уровней стека просто получить столько же обычных вызвово.

Из оптимизаций. Ээээ... новые вершины - вряд-ли будут давать позитивный эффект в схлопываниях и смежные с ними ребра можно
забросить в отстойник. В какую-то очередь где мы вернемся к ним не скоро. Или как-то промаркировать их
как неудаляемые (immortal).
14 сен 20, 15:17    [22196652]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

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

Хм.... кольцо. Это интересная вещь. Надо подумать.

Скорее всего - невозможно в рамках базовой постановки. Или мне надо будет решить где в этом кольце начало и где конец.
Чтобы правильно соединить все ID вершин участников кольца.
14 сен 20, 15:23    [22196661]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80, спасибо. Я посмотрю. Пока у нас нету тест кейса. Но я думаю сегодня-завтра сделаю учебный набор из 10-20 ребер
чтоб конять тривиальные проверки.
14 сен 20, 15:26    [22196663]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

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

Хм.... кольцо. Это интересная вещь. Надо подумать.

На мой взгляд кольцо должно схлопнутся в одну ноду. Или я не правильно понял задачу/смысл задачи.

IMHO
14 сен 20, 15:41    [22196673]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

Андрей Болконский бухал с Безуховым. Бухал с Безуховым долго.


И если разбить его на токены по пробелу то получается цепочка переходов. (Опустим точки и запятые для упрощения)

Андрей -> Болконский -> бухал -> с -> Безуховым. -> Бухал -> с -> Безуховым -> долго.


После схлопывания.

Наподобие Марковской цепи. Где есть вероятности переходов из 1 состояния в другое.
Но оно содержит (по своей природе) уникальные под-цепочки которые однозначно определены.

И в данном случае на выходе мы должны иметь некие состояния автомата типа

"Андрей Болконский" -> "Бухал с Безуховым"
"Бухал с Безуховым" -> "Бухал с Безуховым" // Здесь есть вероятность повтора состояния. Мультиграф. Ребро указывает циклично на свою-же вершину.
"Бухал с Безуховым" -> "долго"


Топологически получаем нормализованный автомат вида

1 -> 2
2 -> 2
2 -> 3


В нем еще не хватает вероятностей переходов. Но наш алгоритм схлопывания убирает единичные где (P=1.0)
и оставляет дробные где например есть ветка (0.4/0.6) Впрочем это отдельная тема.

Поэтому кольцо здесь пока алгоритмически - неясно. Как его потом интерпретировать.

Сообщение было отредактировано: 14 сен 20, 15:52
14 сен 20, 15:55    [22196681]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

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

1 -> 2
2 -> 2
2 -> 3



Петли просто надо исключать еще на шаге валидации вершины.

Собственно это без разницв есть ли кольца в графе или нет. Вершина с которой начал должна остаться от всего кольца. Не надо создавать новых вершин просто исходящая вершина всхлопывает входящую и все ее исходящие переписывет на себя равно как и входящие.
14 сен 20, 23:22    [22196968]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

1 -> 2
2 -> 2
2 -> 3



Петли просто надо исключать еще на шаге валидации вершины.

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

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.

Сейчас пока задача-прим - корректность. Я сегодня сделаю 3-5 модульных тестов и на них
мы будем гонять наши алгоритмы.

50 000 вершин будет потом. Позже. Отобразить их на экране - тоже проблема. То graphviz зависает
на рендеринге. То браузер не может открыть большую картинку или svg-файл.
15 сен 20, 10:09    [22197057]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

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

По поводу того где используются графы. Организация Thomson Reuters собирает сведения по физ-лицам
и организациям и складывает их в БД семантического веба. Некоторые сведения имеют статус Open Source
и вы можете тут почитать https://developers.thomsonreuters.com/ и там-же можно скачать образцы
графов в формате Turle (ttl) и кажется Trig.

Фрагмент.

+
@prefix tr-common: <http://permid.org/ontology/common/> .
@prefix fibo-be-le-cb: <http://www.omg.org/spec/EDMC-FIBO/BE/LegalEntities/CorporateBodies/> .
@prefix vcard: <http://www.w3.org/2006/vcard/ns#> .
@prefix tr-org: <http://permid.org/ontology/organization/> .
@prefix mdaas: <http://permid.org/ontology/mdaas/> .
@prefix tr-fin: <http://permid.org/ontology/financial/> .

<https://permid.org/1-5064696466>
        a                            tr-org:Organization ;
        tr-common:hasPermId          "5064696466"^^xsd:string ;
        mdaas:HeadquartersAddress    "India\n"^^xsd:string ;
        tr-org:hasActivityStatus     tr-org:statusActive ;
        tr-org:isIncorporatedIn      <http://sws.geonames.org/1269750/> ;
        fibo-be-le-cb:isDomiciledIn  <http://sws.geonames.org/1269750/> ;
        vcard:organization-name      "PI Prestige International India Pvt Ltd"^^xsd:string .

<https://permid.org/1-5064706661>
        a                            tr-org:Organization ;
        tr-common:hasPermId          "5064706661"^^xsd:string ;
        mdaas:HeadquartersAddress    "India\n"^^xsd:string ;
        tr-org:hasActivityStatus     tr-org:statusActive ;
        tr-org:isIncorporatedIn      <http://sws.geonames.org/1269750/> ;
        fibo-be-le-cb:isDomiciledIn  <http://sws.geonames.org/1269750/> ;
        vcard:organization-name      "Hexagon Composites India Pvt Ltd"^^xsd:string .


Мы немного работали с TR и насетапили им 1 пилотный проектик.

Для процессинга используются библиотеки такие java libs как Apache Jena, Eclipse RDF.

Для хранения используется Amazon Neptune.

Или из опенсорцного Neo4j, но последний я не юзал.

Из языков запросов используется SPARQL. На нем можно делать поисковые запросы типа найти все
вершины обладающие сетом атрибутов. Есть еще вариант java DSL для поисковых запросов.
Кажется называется Gremlin. По нему я хотел создать отдельный топик.

Семантический веб - это граф. Где вершины и рёбра несут мета-информацию о какой-то области.

Но в данной конкретной задаче у меня ребро не несет никакого смысла а в семантическом вебе - ребер
может быть много и на них может быть много смыслов. Например следующий скрипт на языке turtle
описывает различные узлы и связи между ними. Например в узел :member смотрят 3 ребра и исходящие
узлы - это мемберы.

@prefix : <https://sql.ru/forum#>
@prefix :rdfs <https://......#>

:mayton a :member;
           a :moderator.   
:leoniz a :member;
           sname "Кудрявцев".
:stas rdfs:type :member.

В данном примере rdf:type и артикль "a" - синонимы. Просто такой вот макрос. Вот так вот на черепашке
я описал например достаточно гибкую schema-less модель данных.

Описать подобную структуру реляционкой очень сложно. Зачастую - сложнее даже чем EAV. Почти невозможно.
Я пробовал.

Тоесть графовые задачи реально существуют и работают. И игры со схлопыванием - это просто какая
то частная задача. Которая возможно и имеет коробочное решение в Neptune/Neo4j но мне их
движки внутри не интересны.

А мне интересны нестандартные и сложные структкуры данных которые бросают челлендж.

Вот так вот.

Если ты хочешь качать скилы в мультипоточке - то gogo со мной. Если хочешь делать гороскопы в телеграме - то
... как хочешь короче.
15 сен 20, 19:23    [22197741]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80, сделал консольное приложение так.

+
package ru.sql

import scala.annotation.tailrec

object Dimonz {

  val data = {
    scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
      .map { l =>
        val arr = l.split(",").map(_.toInt)
        arr(0) -> arr(1)
      }.toArray
  }

  @tailrec
  def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {
    val inputs = data.groupBy(_._2).map { case (k, v) => k -> v.map(_._1) }
    val outputs = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

    val singleLinks = outputs.filter(_._2.length == 1)
      .filter { case (from, Array(to)) => Array(from).toList == inputs(to).toList }
      .map { case (from, Array(to)) => from -> to }

    if (singleLinks.isEmpty) {
      return data
    }

    val newData = collection.mutable.HashSet[(Int, Int)]()

    data.foreach { case (from, to) =>
      // нашли связь 1вых->1вх
      if (singleLinks.get(from) == Option(to)) {
        // перенести исходящие узлы удаляемго узла к преды дущему
        outputs.get(to).foreach { outs =>
          outs.foreach { out =>
            newData.add((from, out))
          }
        }
      } else {
        if (!singleLinks.exists { case (f, t) => (t == from) }) {
          newData.add((from, to))
        }
      }
    }

    processGraph(newData.toArray)

  }

  def main(args: Array[String]): Unit = {
    processGraph(data)
  }

}



Хм... 26 секунд. Неплохо. Еще остался пустяк - проверить корректность.

mayton@ryzen-ssd:/storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80$ sbt run
[info] welcome to sbt 1.3.13 (Ubuntu Java 11.0.8)
[info] loading project definition from /storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/project
[info] loading settings for project root from build.sbt ...
[info] set current project to dimonz80 (in build file:/storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/)
[info] Compiling 1 Scala source to /storage/sql.ru/java-pyatnichnoe-shlopyvanie-tolstyh-grafov/dimonz80/dimonz80/target/scala-2.13/classes ...
https://repo1.maven.org/maven2/org/scala-sbt/compiler-bridge_2.13/1.3.5/compiler-bridge_2.13-1.3.5.pom
  100.0% [##########] 2.8 KiB (4.8 KiB / s)
[info] Non-compiled module 'compiler-bridge_2.13' for Scala 2.13.3. Compiling...
[info]   Compilation completed in 7.12s.
[info] running ru.sql.Dimonz 
[success] Total time: 26 s, completed Sep 15, 2020, 9:08:08 PM
15 сен 20, 21:10    [22197827]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;
15 сен 20, 21:53    [22197854]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

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

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.


На самом деле мультипоточность тут возможно только при том если граф можно разбить на непересекающиеся графы. Если только нет активного желания связываться с вершинами которые связывают подмножества графов между собой. Но это будет очень гиморно, но скорость должна подрасти. Там только фокус в том, что вершины которые связаны с другими подграфами нельзя всхлапывать.
16 сен 20, 02:25    [22197991]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Sergunka
Member

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

Красивый код
16 сен 20, 02:26    [22197992]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;



Эээ... Я сейчас обидные, наверно, вещи говорить буду. Но есть мнение, что одна их главных проблем ООП это то, что программист начинает делать модель мира, в котором существует поставленная проблема, а не решать саму проблему. Т.е. если для решения задач типа предложенной в топике ты начинаешь писать такой код, то что-то не так в консерватории, интерпрайз головного мозга. По-моему, тут надо рисовать на простом листке в клетку и забыть про ООП, патерны и прочую шелупонь до того момента, пока это все не станет продакшн кодом, т.е. забыть навсегда))), а при реализации использовать максимально примитивные структуры. Я думаю, именно поэтому ты забыл, зачем Set поменял на Map)) Я бы точно забыл, когда перед глазами мельтешат всякие privatы, loggerы, public class implements Serializablы)))


Есть пример жизненный, когда на собесе (кажется в Ланит) предложили сделать тестовое задание, чисто алгоритмическое. Я вот тоже нагородил там, класс на классе сидит интерфейсом погоняет. Сделал , отправил на проверку, они говорят - неверно. Я тогда просто листик в клетку взял и карандаш, успокоился и нарисовал за пару часов решение, чисто схематично, потом за пару минут оттранслировал его в код, который можно было на любом языке практически сделать, и выслал снова, они говорят - вот теперь все верно, только с первого раза надо было сделать, отдыхай, родной.)) Но я не расстроился, т.к. это было самое лучшее тестовое задание с точки зрения подумать, а не кодить.


По теме топика:

От интерпрайза маятник качнулся в противоположную сторону - байтоjobство))

Попробовал сделать на матрицах. Чтобы сэкономить на памяти, решил использовать упакованную матрицу связности, т.е. кодировать связи битами, когда матрица хранит числа, каждое из которых является субматрицей, где каждый бит в числе кодитует связь (1 - связь есть, 0 - связи нет).

Расчет был на уменьшение матрицы как таковой в n^2 раз, где n - кол-во бит в числе. Это даст меньше итераций по массиву, а вычисление связи в субматрице - битовая операция и поэтому все должно быть быстро.


Для упрощения субматрицы должны были быть квадратные, т.е. 16, 64 и т.д битные, чтобы быть 4х4, 8х8 и т.д. Сначала принялся делать на Long (8x8), однако обжегся на порядке бит (little-endian), когда для половины числа надо было кодировать биты по другому, это в общем не сложно, но чтобы не усугублять, пока взял Short (4x4). Запилил функции для установки/снятия каждого отдельного бита, получения отдельных столбцов и строк.


Для нахождения пар узлов - кандидатов на удаление нужно найти элемент матрицы с установленной 1 на пересечении пустых в других ячейках строки с столбца. Если вычисление строки имеет сложность O(1) (просто взять нужный подмассив), то вычиление столбца - O(n), т.к. нужно пройтись в всем строкам и взять нужый элемент. И получается, что сканирование матрицы для нахождения нужных строк и столбцов имеет квадратичную сложность как минимум плюс еще пройтись по строке и столбцу и проверить что в там есть одна нужная 1 в нужном месте. Короче, все равно медленно.

Была идея отразить матрицу по диагонали и получить быстрый доступ к столбцам, т.к. теперь они стали строками. Но это двойной расход памяти и задача по сути сводится к предложенному мной выше решению, когда поиск ведется по 2м словарям: типа Узел->{Выходы} и Узел->{Входы}.


В итоге Fail! И по скорости и по памяти. Если на матрице работает медленно и с хипом -Xmx2g, то на словарях Узел->{Выходы} и Узел->{Входы} менее минуты и по памяти хватает дефолтных для scala REPL -Xmx256m
16 сен 20, 02:42    [22197993]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Sergunka
dimonz80,

Красивый код


это Proff-of-concept из говна и палок.
16 сен 20, 02:43    [22197994]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Sergunka
dimonz80,

Красивый код


И тут тебе не code review!!!
16 сен 20, 02:46    [22197995]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

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

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

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

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

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

посади пилота из прошлого в современный боинг- он с места его не сдвинет) так и олд скул прогеры - тупо пасуют - у меня живой пример - чувак реально в IT 20 лет - но дуб дубом и скорей всего будет уволен


Пилотов учат летать на планере без мотора, чтобы они жопой закон Бернулли почувствовали.
16 сен 20, 04:46    [22197997]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Вспомнил.
16 сен 20, 09:00    [22198087]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

Эээ... Я сейчас обидные, наверно, вещи говорить буду. Но есть мнение, что одна их главных проблем ООП это то, что программист начинает делать модель мира, в котором существует поставленная проблема, а не решать саму проблему. Т.е. если для решения задач типа предложенной в топике ты начинаешь писать такой код, то что-то не так в консерватории, интерпрайз головного мозга. По-моему, тут надо рисовать на простом листке в клетку и забыть про ООП, патерны и прочую шелупонь до того момента, пока это все не станет продакшн кодом, т.е. забыть навсегда))), а при реализации использовать максимально примитивные структуры. Я думаю, именно поэтому ты забыл, зачем Set поменял на Map)) Я бы точно забыл, когда перед глазами мельтешат всякие privatы, loggerы, public class implements Serializablы)))

Ахахах. Я-же писал в начале топика

mayton
То второе ограничение - медленная скорость поиска смежных вершин
по матрице - я не преодолел.


По поводу ООП головного мозга и все такое. В родительской задаче ребро - МАТЕРИАЛЬНО. Оно несет нагрузку.
И если в данном топике (в схлопывании) мы действительно можем его закодировать 1 битом то родительском - нет.

Вопрос - делать ли мне спициализированную библиотеку для данного топика или оставить обобщённую? Ну
для меня как-бы очевидно. Оставлю общую.
16 сен 20, 10:44    [22198153]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

По поводу не-создания новых вершин. Это была оптимизация под мультипоточность.
Впрочем мы еще обсудим.


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

Да. В этом челлендж этой задачи. Пока она принципиально не сегментируется.
Я не могу ее разделить на независимые подграфы. Хотя допускаю что такие
несвязные компоненты реально существуют. Но в родительском топике
мы просто находили такие себе сверх-вершины которые имели по сотне связей.
(это популярные артикли и предлоги в литературном произведении).

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

Интересно что все методики деления коллекции по хешу например - полезные для мультипоточного
процессинга - в нашем случае бесполезны. Уже на 2 уровне связей нелья ничего гарантировать
в отношении хеша и связности.
16 сен 20, 10:50    [22198162]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

Для нахождения пар узлов - кандидатов на удаление нужно найти элемент матрицы с установленной 1 на пересечении пустых в других ячейках строки с столбца. Если вычисление строки имеет сложность O(1) (просто взять нужный подмассив), то вычиление столбца - O(n), т.к. нужно пройтись в всем строкам и взять нужый элемент. И получается, что сканирование матрицы для нахождения нужных строк и столбцов имеет квадратичную сложность как минимум плюс еще пройтись по строке и столбцу и проверить что в там есть одна нужная 1 в нужном месте. Короче, все равно медленно.

Если вы посмотрите на граф глазами или на матрицу (не знаю как) то вы обратие внимание что она - очень разреженная.
Состоит из вакуума. Именно поэтому я решил трекать списк incomng/outgoing сввязей чтобы убрать из задачи линейный
поиск пл 50_000 соседенй и свести его тоже к линейному но более быстрому по ИЗВЕСТНЫМ соседям.

Кстати из курса численных методов. Физики и математики любят матрицы плотности как пенопласт.
У них даже есть для этого специальный инструмент Разреженных Матриц https://en.wikipedia.org/wiki/Sparse_matrix

И у меня была вначале идея касающаяся именно этого способа хранения. Но те матрицы ничего мне не гарантировали в плане
быстого lookup соседей. Они просто обеспечивали декартовый доступ по сжатым данным. А это вобщем мне было не надо.
16 сен 20, 10:56    [22198178]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

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


По поводу ООП головного мозга и все такое. В родительской задаче ребро - МАТЕРИАЛЬНО. Оно несет нагрузку.
И если в данном топике (в схлопывании) мы действительно можем его закодировать 1 битом то родительском - нет.

Вопрос - делать ли мне спициализированную библиотеку для данного топика или оставить обобщённую? Ну
для меня как-бы очевидно. Оставлю общую.



Ну тут тебе никто не указ. Твоя библиотека - твои правила. Поинт в том, что в ООП сначала мы накидаем модель как ее сходу увидели, а потом превозмогаем, пытаясь решить задачу, используя выдуманные нами же на ходу термины. Это нас ограничивает, нам жаль отказаться от уже с заботой написаных public class Graph implements Serialazable с логгером внутри))). Однако манипулировать примитивами может оказаться намного проще быстрее и экономичнее, чем сложными объектами. К тому же для примитивов с большей долей вероятности существует готовая мат. модель и алгоритмы.

А материальность ребра может быть вражена просто в еще дном числе, строке или наборе чисел и строк в добавок к существующей паре {вершина, вершина}.

IMHO, все эти классы Vertex, Edge, Graph годятся лишь как фасад к манипулированию числами, массивами и прочей низкоуровневой ерундой.

Когда я пытался возиться с матрицами, то пришлось делать некоторую нормализацию, т.е. приведение номеров вершин из исходных данных к индексам столбцов и строк. Т.е. это как всякие свертки и прочие преобразования Фурье и Лапласа в математиве. Мы свою модель приводим к какому-то удобоваримому для решения задачи виду, решаем задачу и разворачиваем обратно, чтобы придти к исходной системе координат. Вот.

Надеюсь на ваше понимание.
16 сен 20, 12:14    [22198296]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
mayton
Хм... пару недель назад я запилил Map<Edge, Edge> в качестве коллекции ребер.
И при этом я точно помню что Set<Edge> меня чем-то не устраивал.

Чьорт побьери... я забыл ЧЕМ!

import static java.lang.String.format;
import static java.lang.String.valueOf;
import static java.util.Collections.unmodifiableMap;

/**
 * Directed, Weight graph
 */
public class Graph implements Serializable {

    static Logger logger = LoggerFactory.getLogger(Graph.class);

    // TODO: Leonid proposes to get rid of Edges instead of primitives.
    private Map<Edge, Edge> edgeWeigthMap;
    private Map<String, Vertex> vertexMap;
    private transient LinkedHashMap<String, Object> statistics;

Основное

По поводу этой загадочной мапы где ключ и значение декларированы как один и тот-же объект.

Мне нужна была процедура поиска ребра в графе по идентификаторам двух вершин.
Например.

@NotNull
    public Edge extractEdgeByIds(@NotNull String id1,@NotNull String id2) {
        Edge keyEdge = new Edge(new Vertex(id1), new Vertex(id2));
        return edgeWeigthMap.get(keyEdge);
    }


Ребро содержит ключевые поля. Такие как v1,v2 - это ссылки на вершины к которому оно прикрепляется.
Это реальные объекты из текущего инстанса графа.

Тоесть по частичной (неполной) информации о ребре надо ивзлечь полную. Именно поэтому вместо

Set<Edge> 


что было достаточно просто и логично я ввел

Map<Edge, Edge> 

где семантика первого генерализованного параметра Edge - просто нужна чтоб заработали алгоритмы
хеш-поиска и уже восстановили ребро в полном наборе атрибутов. Hash-code и Equals соотвественно
работают только по ключевым атрибутам.

Альтернативное решение. Я мог завести синтетический составной ключ ребра типа String и складывать
туда сериализацию вершин в строку например "1->2" но с моей точки зрения это оверхед т.к. в первом
варианте я экономлю на ссылках на Edges без создания доп-объекотв String (напоминаю 260 тысяч ребер)
которые могут подгрузить память.
Map<String, Edge> 


Еще альтерантивное решение. Я мог завести ключ PairOfVertices или Pair<Vertex,Vertex>
но это тоже не давало явного преимущества перед простотой 1 варианта.

А из Set<Edge> нельзя было сделать поиск. Можно проверить contains() и извлечь итератор.
Но поиск по частичным ключам - нельзя.

Что еще

Также ребро содержит доп-атрибуты. В моём случае это weight (вес) но в будущем это будет генерик.
Чтоб добавлять произвольные атрибуты.
/**
 * Directed, Weight Edge
 */
public class Edge implements Serializable, Externalizable {

    static final long serialVersionUID = 2L;

    // Key fields
    private Vertex v1;
    private Vertex v2;

    // Non-key
    private int weight;

    // Displayeable


    public Edge(@NotNull Vertex v1, @NotNull Vertex v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

    public Edge(@NotNull Vertex v1, @NotNull Vertex v2, int weight) {
        this.v1 = v1;
        this.v2 = v2;
        this.weight = weight;
    }
16 сен 20, 12:23    [22198306]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

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

Когда я пытался возиться с матрицами, то пришлось делать некоторую нормализацию, т.е. приведение номеров вершин из исходных данных к индексам столбцов и строк. Т.е. это как всякие свертки и прочие преобразования Фурье и Лапласа в математиве. Мы свою модель приводим к какому-то удобоваримому для решения задачи виду, решаем задачу и разворачиваем обратно, чтобы придти к исходной системе координат. Вот.

Надеюсь на ваше понимание.

Я 100% буду подходить к примитивам когда исчерпаю возможности перформанса объектов. Но на данном этапе
такая разработка (на кривой Шипилёва) находится в точке экстремума где код еще на стал "свинским" по отношению
к читающему и можно еще рассуждать об алгоримах. Как вы понимаете когда программист-одиночка занят
глубоким перформансом - он ведет себя как свинья по отношению к тем что собирается глазами этот код
читать.

Да конешно в данном топике самый большой свинтус - это я. Так что не переживайте. А ваш сорс на Scala
я раскурю чуть позже и покрою тестами. Пока я как-бы ничего не могу сказать. Мой код покрыт лишь на
примитивных операциях а схлопывание еще не реализовано.
16 сен 20, 12:29    [22198315]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
Последние сообщения читал по диагонали, но или я не правильно понимаю задачу или Ваш код выглядит слишком просто (т.е. делает что-то не то).

Не очень понимаю, какие правила для того, что бы посчитать что ноды A и B можно схлопнуть и где данная проверка в Вашем коде (scale не знаю) ?
16 сен 20, 13:25    [22198386]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Leonid Kudryavtsev
Последние сообщения читал по диагонали, но или я не правильно понимаю задачу или Ваш код выглядит слишком просто (т.е. делает что-то не то).

Не очень понимаю, какие правила для того, что бы посчитать что ноды A и B можно схлопнуть и где данная проверка в Вашем коде (scale не знаю) ?




Слегка разбавил говнокод говнокоментами
import scala.annotation.tailrec

/*  
   Делаем замену типа вот так (ребра без стрелок считать направленными слева направо)

           1        6                       1   6                          
            \      /                         \ /                         
        2 -> 4 -> 5 -> 7       ====>     2 -> 4 -> 7                                               
            /      \                         / \                         
          3         8                      3    8      


  Суть реализации - сделать два словаря: для входящих и исходящих ребер каждого из узлов
  Т.е.  4->{1,2,3}, 5->{4}, 6->{5}, 7->{5}, 8->{5} - словать входов для каждого узла
        1->{4}, 2->{4}, 3->{4}, 4->{5}, 5->{6,7,8} - словарь выходов
  
  Потом найдем кандидата на удаление: в первом словаре есть 5->{4}, во втором 4->{5}
  Таким образом ребро 4->5 кандидат на схлопывание 



  Для незнающих синтаксис Scala
  val data : Type - объявление константы (Type data)
  (Int, Int) - кортеж их двух элементов типа  Int (Tuple<Int,Int>)
  _1 - первый элемент кортежа, _2 - второй и т.п. 
  Например: 
    val tuple = ("A","B") 
    tuple._1 ==  "A" // true
    tuple._2 == "B" // true

  Array[Type] - массив элементов типа Type (Type[])
  Map[Int, Array[Int]] - Map<Int,Int[]>
  

*/

// Ориентированный граф представлен в виде множества пар чисел,
// каждая пара - (вершина от которой направлено ребро, вершина к которой направлено ребро)

// вычитаем все ребра из файла в массив типа (Int, Int), преобразуя на ходу в Int
val data: Array[(Int, Int)] = {
  scala.io.Source.fromFile("war-and-society-1-2-3-4-simple-edges.sorted.csv").getLines()
    .map { l =>
      val arr = l.split(",").map(_.toInt)
      arr(0) -> arr(1)
    }.toArray
}

/**
 * Рекурсивная функция удаления пар вершин, связанных единственным ребром
 *
 * @param data - граф в виде массив связей между вершинами
 * @return - граф в виде массив связей между вершинами
 */
@tailrec
def processGraph(data: Array[(Int, Int)]): Array[(Int, Int)] = {

  // Хэш таблица с входящими связями для каждой вершины - вершина -> массив входящих ребер
  // т.е. 4 -> {1,2,3}, 5->{4}, 6->{5}, 7->{5}, 8->{5} 
  val inputs: Map[Int, Array[Int]] = data
    .groupBy(_._2) // группируем по врешине, в которую направлено ребро, на выходе Map[Int, Array[(Int,Int)]
    .map { case (k, v) => k -> v.map(_._1) } // оставляем в занчении  только входящие узлы, т.е. приводим к  Map[Int, Array[Int]]

  // Хэш таблица с исходящими связями для каждой вершины - вершина -> массив исходящих ребер
  // Аналогично inputs, только группировка относительно вершины, из которой выходит ребро
  // т.е. 1->{4}, 2->{4}, 3->{4}, 4->{5}, 5->{6,7,8}
  val outputs: Map[Int, Array[Int]] = data.groupBy(_._1).map { case (k, v) => k -> v.map(_._2) }

  // Пары с одним входом и одним выходом - кандидаты на схлопывание
  // в outputs ищем вершины с единственным выходным ребром, для которых есть пара в inputs тем же ребром, но уже входным
  // т.е. надо найти 5->{4} из inputs и 4->{5} из outputs
  val singleLinks: Map[Int, Int] =
    outputs
      .filter(_._2.length == 1) // ищем вершины с одним выходом (т.е. такую верщину, у ктр. длина массива ввыходов == 1)
      .filter { case (from, Array(to)) => // ищем к найденой вершиние с одним выходом пару из хэш таблицы входов, такую, чтобы выход одной вершины == вход другой 
        Array(from).toList == inputs(to).toList 
      } 
      .map { case (from, Array(to)) => from -> to } // преобразуем из Map[Int, Array[Int]] в Map[Int, Int], т.к. связаннре ребро одно и массив не нужен
  
  // singleLinks = 4->5

  // если пар для удаления нет, от делать больше нечего, возвращаем исходный граф
  if (singleLinks.isEmpty) {
    return data
  }

  // сюда будем собирать новый схлопнутый граф, Set - для перестраховки от дубляжей
  val newData = collection.mutable.HashSet[(Int, Int)]()
  
  /* 
     Теперь перебираем все ребра графа и проверяем, можно-ли их удалить,
     т.е. входит-ли данное ребро в singleLinks
     Если ребро является кандидатом на удаление, то сохраняем только вершину из которой направлено ребро
     и перевпривязываем к ней выходые ребра второй вершины
     Если ребра в singleLinks нет,  то просто переносим его в результирующий граф 
                        
  */  
  data.foreach { case (from, to) =>
    // нашли пару вершин - кандидатов на удаление (4->5)
    if (singleLinks.get(from) == Option(to)) {
      // перепривязываем выходые ребра второй вершины к первой
      // т.е. вновь образованные пары 4->6, 4->7, 4->8
      outputs.get(to).foreach { outs =>
        outs.foreach { out =>
          newData.add((from, out))
        }
      }
    } else { // иначе просто переносим ребро в результат
      // проверка, чтобы исх ребра из удаленной вершины 
      // (которые мы переприцепили к вервой) не попали в результат
      // т.е. пары 5->6, 5->7, 5->8 нам уже не нужны
      if (!singleLinks.exists { case (f, t) => (t == from) }) { 
        newData.add((from, to))
      }
    }
  }

  processGraph(newData.toArray)

}

processGraph(data)
 
16 сен 20, 16:16    [22198542]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
dimonz80

Таким образом ребро 4->5 кандидат на схлопывание

Где мы ишем факт того, что отстутвует другой путь из 4 в 5.

Т.е. не существует маршрута, например, 4 -> 3 -> 8 -> 5 ?
16 сен 20, 16:35    [22198562]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

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

Но тогда задача какая-то черезчур простая.

Что в ситуации, когда в нодах больше одной входящей связи но они относятся к непересекающимся-несвязанным подграфам (с терминологией у меня все плохо). Я так подумал, что их тоже нужно схлопывать.
16 сен 20, 16:42    [22198566]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Мой долг в части тест-кейсов растет. Я о нем помню. И я думаю сегодня их выложу.

Пока рисую в блокноте. Вот тривиальные случаи как раз закроем.
16 сен 20, 16:47    [22198573]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
ладно, пофиг, т.з. конечно замечательное " рёбра типа (4)->(5) как на картинке." )))

в любом случае, смысл сего действия мне не очень понятен
16 сен 20, 16:47    [22198574]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Leonid Kudryavtsev
dimonz80

Таким образом ребро 4->5 кандидат на схлопывание

Где мы ишем факт того, что отстутвует другой путь из 4 в 5.

Т.е. не существует маршрута, например, 4 -> 3 -> 8 -> 5 ?


В условии такого вроде нету.
16 сен 20, 16:47    [22198575]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно
16 сен 20, 16:50    [22198577]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Leonid Kudryavtsev
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно


Че ты начинаешь?! Нормально же общались! Зануда.

Иногда полезно делать такие экзерсисы. Просто чтобы размяться. Если ты вертишь графы, матрицы и т.п. каждый день на работе, то мы тут все тебе безмерно завидуем, честно.
16 сен 20, 16:55    [22198590]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
dimonz80
Leonid Kudryavtsev
тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно


Че ты начинаешь?! Нормально же общались! Зануда.

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


Это как отставной полковник иногда просыпается среди ночи и начинает разбирать и собирать наградной ПМ.
16 сен 20, 17:00    [22198595]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Беря во внимание что большинство "кодеров для бизнеса" про графы слыхали только в универах,
я-бы сказал что этот "полковник" собирает и разбирает РСЗО.

Я делаю своё суждение на основани своего уже более чем 15 летнего присуствия на этом форуме.
16 сен 20, 17:05    [22198600]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton
Беря во внимание что большинство "кодеров для бизнеса" про графы слыхали только в универах,
я-бы сказал что этот "полковник" собирает и разбирает РСЗО.

Я делаю своё суждение на основани своего уже более чем 15 летнего присуствия на этом форуме.


Для многих программирование - непыльное ремесло, чтобы кормить семью, во имя 1С, всемилостивого и милосердного, аминь.
16 сен 20, 17:25    [22198620]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80,

мне понравилось что у нас в топике появился скалист. Есть повод потом собрать ваш исходник на scala-native
https://scala-native.readthedocs.io/en/v0.3.9-docs/

и посмотреть как вырастет перформанс. Но это - потом. Сначала - самолёты.
16 сен 20, 17:33    [22198629]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Вот основные тестовые кейсы. 8 штук.

(1) и (3) это цепочка.
(2) это цикл. Не схлопывается.
(5) и (6) это ветка. Не схлопывается.
(7) это классический случай с которого мы начали
(8) это цикл. Тоже не схлопывается.

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

Откуда:
Сообщений: 227
mayton
Вот основные тестовые кейсы. 8 штук.

(1) и (3) это цепочка.
(2) это цикл. Не схлопывается.
(5) и (6) это ветка. Не схлопывается.
(7) это классический случай с которого мы начали
(8) это цикл. Тоже не схлопывается.


Случаи 5 и 6 противоречат остальным
вчера, 05:23    [22198885]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
Почему?
вчера, 09:41    [22198929]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
mayton
Почему?



Ну например, соединив 5 и 6 получим 7, но 5 и 6 не схлопываются, а 7 схлопывается. Как так?

И еще проблема тест кейсов в отсутствии намека на остальную часть графа.
вчера, 09:46    [22198932]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48895
dimonz80
mayton
Почему?



Ну например, соединив 5 и 6 получим 7, но 5 и 6 не схлопываются, а 7 схлопывается. Как так?

И еще проблема тест кейсов в отсутствии намека на остальную часть графа.

Я понял ваше сомнение. Действительно - надо хотя-бы обозначить прочие вершины.
вчера, 10:24    [22198958]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
dimonz80
Случаи 5 и 6 противоречат остальным

а так же 2 и 7

т.к. лично я бы подумал, что кольцо должно схлопнутся в 1-н элемент. Почему оно не должно схлопываться, мне не понятно

в 7-ом, я бы подумал, что элементы 7->4 7->6 так же должны схлопнутся (см. картинку N1)

В общем, правила схлопывания мне совершенно не понятны. А предметную область я не знаю.
вчера, 11:19    [22199030]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Leonid Kudryavtsev
dimonz80
Случаи 5 и 6 противоречат остальным

а так же 2 и 7

т.к. лично я бы подумал, что кольцо должно схлопнутся в 1-н элемент. Почему оно не должно схлопываться, мне не понятно

в 7-ом, я бы подумал, что элементы 7->4 7->6 так же должны схлопнутся (см. картинку N1)

В общем, правила схлопывания мне совершенно не понятны. А предметную область я не знаю.


Ну на картинке преобразования после одной итерации, по идее. При следующей должно схлопнуться.
вчера, 11:31    [22199052]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
dimonz80
Member

Откуда:
Сообщений: 227
Задача, похоже, мутирует в сторону поиска паттернов в графе.
вчера, 11:44    [22199065]     Ответить | Цитировать Сообщить модератору
 Re: Java :: Пятничное схлопывание толстых графов.  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8927
Задача еще никуда не сдвинулась.

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

Откуда: loopback
Сообщений: 48895
Схлопывание?
вчера, 13:45    [22199187]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Java Ответить