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

Откуда: loopback
Сообщений: 39873
Составил список.

  • GraphT
  • JUNG
  • Guava
  • Apache Commons Graph
  • GRPH

    По результатам - отпишусь. Для себя я просто поищу тривиальные штуки типа
    объекты в базе (tables, fields, indexes, triggers, contraints, views) и представлю
    их как вершины. А связи между ними - как ориентированные рёбра. И простейшие
    запросики типа кто зависит от таблички и тому подобное.

    Составлю табличку фичей. Типа там.... Реализован или нет
    коммивояжер или метод кратчайших путей.

    Если кто-то хочет что-то узнать по имплементированным алгоримам - пишите.
    Возможно я парарллельно посмотрю.
  • 27 июн 18, 15:06    [21525406]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Leonid Kudryavtsev
    Member

    Откуда:
    Сообщений: 7516
    Упрощение, кластеризация графа.

    Пример из жизни. Есть 5-6 тысяч аэропортов (вершины графа), есть около 50-60 тыс. регулярных авиаперелетов (в один день) между этими аэропортами (ребра графа)

    Искать маршрут Нижне Вартовск - остров Лимпопо (с населением 100 чел и взлетной площадкой для самолетов наркоторговцев), больно накладно. Значительно проще провести кластеризацию графа, т.к. 99 % международных рейсов выполняет 100-130 наиболее крупных аэропортов (скажем первая сотня + еще пара десятков хабов типа Пулкова /который вообще где-то 200 по рейтингу/ или Новосибирск)

    Т.ч. проще найти Нижне-Вартовск - Ханты-Мансийск - [Москва] - Хельсинки - [Сингапур] - и дальше на кокурузниках до вожделенной травки )))

    В общем, хотелось бы граф "кластеризировать" (в случае с аэропортами это банально проделали руками "на глазок" из 5 тыс. аэропортов оставив около 130-140 "хабов").

    p.s.
    Вики уверет, что в одних США - 13 513 аэропортов. Но это какое-то вранье. "действующих" аэропортов + железнодорожных пересадок (c IATA кодами) по миру в районе 5-6 тыс.
    27 июн 18, 15:42    [21525518]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Leonid Kudryavtsev, я понял вашу задачу на человеческом уровне.

    Но что-то мне подсказывает что для кластеризации нужен еще какой-то критерий. Типа этих 130 аэропортов.
    Тоесть взять граф где вершины - аэропорты. И выкинуть все незначимые. А по поводу рейсов.... я не знаю
    к чему их прикрутить. Но я посмотрю.
    27 июн 18, 15:52    [21525556]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Leonid Kudryavtsev
    Member

    Откуда:
    Сообщений: 7516
    mayton
    Но что-то мне подсказывает что для кластеризации нужен еще какой-то критерий. Типа этих 130 аэропортов.
    Тоесть взять граф где вершины - аэропорты. И выкинуть все незначимые. А по поводу рейсов.... я не знаю
    к чему их прикрутить. Но я посмотрю.

    AFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей

    Пусть при 6 тыс вершин у нас 60 тыс ребер

    Если сокрашаем граф до 400 аэропортов, то остается 38 тыс ребер
    Если до 200 аэропортов, то 35 тыс
    Если до 130 аэропортов, то 30 тыс.
    Если до 100 аэропортов, то 20 тыс.

    Исходя из этой статистики, "на глазок", считаем что 130 аэропортов выгодно по сравнению со 100 (+30% аэропортов +50% связей)
    А 400 совершенно излишне (+400% аэропортов +<100% связей по сравнению со 100; и +100% аэропортов +8% связей по сравнению с 200)

    Наиболее критичное требование - общая связность не должна понизится. Т.е. после упрощения, не должно быть аэропортов до которых вообще не долететь.

    На самом деле, кол-во до которого сокращать, было принято исходя из аппаратно-временно-денежных ограничений + примерно минимально достаточно для сохранения связности.
    27 июн 18, 16:40    [21525727]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Леонид.

    Начал изучать JUNG. Уже устал. В принципе мои задачи джунг уже покрывает. Единственное. Я не нашел
    красивого DSL-подобного языка запросов наподобие того как я видел в Neo4j.

    По поводу алгоритмов кластеризации. Джунг поддерживает их 4 штуки.

    http://jung.sourceforge.net/doc/api/index.html

    BicomponentClusterer<V,E> - Finds all biconnected components (bicomponents) of an undirected graph.
    EdgeBetweennessClusterer<V,E> An algorithm for computing clusters (community structure) in graphs based on edge betweenness.
    VoltageClusterer<V,E> Clusters vertices of a Graph based on their ranks as calculated by VoltageScorer.
    WeakComponentClusterer<V,E> Finds all weak components in a graph as sets of vertex sets.

    К сожалению моего уровня владения теорией графов и техническими терминами не хватает чтобы решить - это оно или не оно.
    Я должен что-то почитать и подготовиться. +Есть некая терминологическая путаница. Где-то вершина это Node, где-то Vertex.
    +Гуглу при поиске надо дополнительно указывать что Graph - это не графика а математика. Вобщем фильтровать поиск т.к.
    находит много нерелевантного материала.

    По поводу других библиотек. Они достаточно однородны в работе с графами. Почти везде API - похожий.
    XGraph g= new XImplGraph();
    XVertex v1= new Vertex(1);
    XVertex v2= new Vertex(2);
    g.add(v1);
    g.add(v2);
    g.add(new XEdge(v1,v2));
    

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

    Apache Commons Graph - предположительно не поддерживает дженерики. Надо проверять.

    C GRPH - были проблемы с удалённым репозитарием. Он не был индексирован в центральном.
    Актуальная версия номер 2 отсутствовала и мне пришлось ходить в веб-порт его собственного
    централа чтоб подсмотреть какая щас актуальная последняя релизная.

    +Перспективной выглядит библиотека yWorks, у нее богатые возможности по визуализации
    (я пользуюсь ихним редактором yEd для рисования диаграмм) но есть подозрение что она платная.
    Еще не проверял.
    27 июн 18, 23:23    [21526818]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    У JGraphT не нашел кластеризации. Ну... по крайней мере среди сущностей такого ключевого слова не было.
    Зато были: клики, потоки, раскраска, циклы, изоморфизм, какой-то "скоринг", разделение, и пути.

    Дополнительно рекламируется тесная интеграция с графической библиотекой JGraphX.
    В учебном семпле приведена серализация двух графов в текстовое представление
    подозрительно похожее на GraphViz (это отдельный тул для визуализации). Можно
    это проверить. Будет удобно в качестве отладки.
    28 июн 18, 01:41    [21526905]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    GRPH - настоящее ископаемое. В исходниках встречаются каменты датирующиеся 1998 годом. Это спустя 2 года (!)
    после создания первого релиза Java компиллятора. Пилят это французы из университета INRIA. Знатное местечко... хм.
    Это толстая либа. В ней упаковано порядка 1.5 тысячи исходных файлов по количеству штук. Я был в большой обиде
    что чортовы созатели упаковали сорцы не по феншую как положено в maven-src а свалили все в одну кучу. Из за
    этого мышко-клик по бинарнику не подсвечивает исходный код но если распаковать jar то сорцы вроде в наличии
    но надо перепаковать как-то получше.

    Сущности для кластеризации там встречаются но.. выглядят как абстрактные классы... вобщем надо разбираться.
    28 июн 18, 02:05    [21526909]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Guava common.graph (GCG) У нее - самая приятная и понятная структура. Мультиграф правда там выделен
    в отдельный базовый класс и называется Network.

    Бегло просмотрел бинарники. Алгоритмов не видно вообще. В недрах документации есть отсылки на Джунг и Граф-Т
    и есть хорошие новости на тему переноса части функционала JUNG под интерфесы Guava (common.graph).

    Я приведу фрагмент картинки с базовыми интерфейсами GCG которые мне показались наиболее значимыми.

    К сообщению приложен файл. Размер - 31Kb
    28 июн 18, 19:40    [21529551]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Apache commons-graph. Я уделил ей 10 минут. И больше смотреть не буду.
    Декларация интерфейсов соответствует примерно Java 1.4. Дженериков нет.
    Вобщем производит впечатление заброшенного проекта.

    Некоторые алгоритмы есть. По крайней мере DFS (поиск в глубину), Minimum Spanning Forest.

    Вобщем по ней уже готов вердикт.

    Не используйте!
    28 июн 18, 20:33    [21529639]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Basil A. Sidorov
    Member

    Откуда:
    Сообщений: 9073
    mayton
    Не используйте!
    Если проект так и не выполз из песочницы за семь лет - ясен перец, что не надо его использовать.
    29 июн 18, 00:03    [21530063]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Хм.. Гуава подбила меня на взлёте. Нужно проверять достижимость для вершин орграфа типа MutableNetwork<V,E>
    А у нее в утилитах есть только проверка Graph<V>
    assertTrue("t1 reachable from v2", Graphs.reachableNodes(model, v1));
    

    [ERROR] Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.7.0:testCompile (default-testCompile) on project ProbeGraph: Compilation failure
    [ERROR] /git/probe/ProbeGraph/src/test/java/mayton/probes/GuavaCommonGraphTest.java:[43,50] method reachableNodes in class com.google.common.graph.Graphs cannot be applied to given types;
    [ERROR]   required: com.google.common.graph.Graph<N>,N
    [ERROR]   found: com.google.common.graph.MutableNetwork<mayton.probes.oracle.OracleObject,mayton.probes.oracle.OracleObject>,mayton.probes.oracle.OracleObject
    [ERROR]   reason: cannot infer type-variable(s) N
    [ERROR]     (argument mismatch; com.google.common.graph.MutableNetwork<mayton.probes.oracle.OracleObject,mayton.probes.oracle.OracleObject> cannot be converted to com.google.common.graph.Graph<N>)
    
    29 июн 18, 01:29    [21530177]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Добавлю еще сюда:
  • Neo4j. Это блин целая DBMS. Но пускай будет
  • Apache Jena. Тоже очень мощная штука. Фактически фреймворк для работы с RDF. Почти графы. Но цели - несколько иные.
  • RDF4j. Те-же яйца. Похожа на Jena по своему назначению.
  • 3 фев 19, 02:21    [21800655]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Sergunka
    Member

    Откуда:
    Сообщений: 1736
    mayton
    Составил список.

  • GraphT
  • JUNG
  • Guava
  • Apache Commons Graph
  • GRPH

    По результатам - отпишусь. Для себя я просто поищу тривиальные штуки типа
    объекты в базе (tables, fields, indexes, triggers, contraints, views) и представлю
    их как вершины. А связи между ними - как ориентированные рёбра. И простейшие
    запросики типа кто зависит от таблички и тому подобное.

    Составлю табличку фичей. Типа там.... Реализован или нет
    коммивояжер или метод кратчайших путей.

    Если кто-то хочет что-то узнать по имплементированным алгоримам - пишите.
    Возможно я парарллельно посмотрю.


  • Вы бы не могли отписаться под какие задачи Вы собираетесь использовать решения на графах. Часто обычный жадный алгоритм Дейкстры или А* вполне так срабатывает.

    https://www.geeksforgeeks.org/greedy-algorithms/#greedyAlgorithmsInGraphs
    3 фев 19, 06:39    [21800672]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Топик тематически связан с https://www.sql.ru/forum/1306465/sparql-rdf-tehnologii-semanticheskogo-poiska-aws-neptune
    3 фев 19, 09:31    [21800682]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Sergunka
    Member

    Откуда:
    Сообщений: 1736
    mayton
    Топик тематически связан с https://www.sql.ru/forum/1306465/sparql-rdf-tehnologii-semanticheskogo-poiska-aws-neptune


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

    У меня есть занятная статья в блоге на несколько близкую тему - я ее написал исключительно из любви к искусству гляньте может понравится

    https://vyatkins.wordpress.com/2018/07/03/predix-asset-store-model-viewer/
    3 фев 19, 10:50    [21800696]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Задача уже есть. И она в продуктиве. Но по я не могу называть здесь заказчика и прочие детали. Надеюсь понимаете.

    Вообще в топиках я стараюсь охватить несколько целей. Иногда - получается. Иногда нет.
    3 фев 19, 10:56    [21800699]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    Спасибо за статью.
    3 фев 19, 13:40    [21800756]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    alex55555
    Member

    Откуда:
    Сообщений: 1966
    Leonid Kudryavtsev
    AFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей

    Сортируете узлы по количеству связей и отрезаете всё, где связей меньше порога. Порог выбирается отдельным алгоритмом.
    3 фев 19, 14:49    [21800784]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 39873
    alex55555
    Leonid Kudryavtsev
    AFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей

    Сортируете узлы по количеству связей и отрезаете всё, где связей меньше порога. Порог выбирается отдельным алгоритмом.
    Нельзя так упрощать. Вы порежете мостовые рёбра и получите два несвязных графа.
    3 фев 19, 15:53    [21800797]     Ответить | Цитировать Сообщить модератору
     Re: Решил сравнить библиотеки для работы с графами.  [new]
    Sergunka
    Member

    Откуда:
    Сообщений: 1736
    mayton
    Спасибо за статью.


    Я провел свое исследование и написал код в пику нашим архитекторам которые изучали на тот момент gremlin

    https://tinkerpop.apache.org/gremlin.html

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

    На самом деле смотря какой стек Вы хотите избрать гремлин в общем-то неплох в базовой идеи

    Картинка с другого сайта.
    3 фев 19, 23:55    [21800964]     Ответить | Цитировать Сообщить модератору
    Все форумы / Java Ответить