ReSQL.ru
     
powered by simpleCommunicator - 2.0.38     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Решил сравнить библиотеки для работы с графами.
25 сообщений из 30, страница 1 из 2
  1  все
Решил сравнить библиотеки для работы с графами.
    #39666590
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Составил список.

GraphT

JUNG

Guava

Apache Commons Graph

GRPH

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

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

Если кто-то хочет что-то узнать по имплементированным алгоримам - пишите.
Возможно я парарллельно посмотрю.
...
Рейтинг: 0 / 0
27.06.2018, 15:06
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666627
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Упрощение, кластеризация графа.

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

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

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

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

p.s.
Вики уверет, что в одних США - 13 513 аэропортов. Но это какое-то вранье. "действующих" аэропортов + железнодорожных пересадок (c IATA кодами) по миру в районе 5-6 тыс.
...
Рейтинг: 0 / 0
27.06.2018, 15:42
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666648
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev, я понял вашу задачу на человеческом уровне.

Но что-то мне подсказывает что для кластеризации нужен еще какой-то критерий. Типа этих 130 аэропортов.
Тоесть взять граф где вершины - аэропорты. И выкинуть все незначимые. А по поводу рейсов.... я не знаю
к чему их прикрутить. Но я посмотрю.
...
Рейтинг: 0 / 0
27.06.2018, 15:52
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666701
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonНо что-то мне подсказывает что для кластеризации нужен еще какой-то критерий. Типа этих 130 аэропортов.
Тоесть взять граф где вершины - аэропорты. И выкинуть все незначимые. А по поводу рейсов.... я не знаю
к чему их прикрутить. Но я посмотрю.
AFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей

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

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

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

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

На самом деле, кол-во до которого сокращать, было принято исходя из аппаратно-временно-денежных ограничений + примерно минимально достаточно для сохранения связности.
...
Рейтинг: 0 / 0
27.06.2018, 16:40
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666848
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Леонид.

Начал изучать 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 - похожий.
Код: java
1.
2.
3.
4.
5.
6.
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 для рисования диаграмм) но есть подозрение что она платная.
Еще не проверял.
...
Рейтинг: 0 / 0
27.06.2018, 23:23
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666864
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У JGraphT не нашел кластеризации. Ну... по крайней мере среди сущностей такого ключевого слова не было.
Зато были: клики, потоки, раскраска, циклы, изоморфизм, какой-то "скоринг", разделение, и пути.

Дополнительно рекламируется тесная интеграция с графической библиотекой JGraphX.
В учебном семпле приведена серализация двух графов в текстовое представление
подозрительно похожее на GraphViz (это отдельный тул для визуализации). Можно
это проверить. Будет удобно в качестве отладки.
...
Рейтинг: 0 / 0
28.06.2018, 01:41
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39666866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
GRPH - настоящее ископаемое. В исходниках встречаются каменты датирующиеся 1998 годом. Это спустя 2 года (!)
после создания первого релиза Java компиллятора. Пилят это французы из университета INRIA. Знатное местечко... хм.
Это толстая либа. В ней упаковано порядка 1.5 тысячи исходных файлов по количеству штук. Я был в большой обиде
что чортовы созатели упаковали сорцы не по феншую как положено в maven-src а свалили все в одну кучу. Из за
этого мышко-клик по бинарнику не подсвечивает исходный код но если распаковать jar то сорцы вроде в наличии
но надо перепаковать как-то получше.

Сущности для кластеризации там встречаются но.. выглядят как абстрактные классы... вобщем надо разбираться.
...
Рейтинг: 0 / 0
28.06.2018, 02:05
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39667346
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Guava common.graph (GCG) У нее - самая приятная и понятная структура. Мультиграф правда там выделен
в отдельный базовый класс и называется Network.

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

Я приведу фрагмент картинки с базовыми интерфейсами GCG которые мне показались наиболее значимыми.
...
Рейтинг: 0 / 0
28.06.2018, 19:40
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39667365
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Apache commons-graph. Я уделил ей 10 минут. И больше смотреть не буду.
Декларация интерфейсов соответствует примерно Java 1.4. Дженериков нет.
Вобщем производит впечатление заброшенного проекта.

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

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

Не используйте!
...
Рейтинг: 0 / 0
28.06.2018, 20:33
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39667429
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
maytonНе используйте!Если проект так и не выполз из песочницы за семь лет - ясен перец, что не надо его использовать.
...
Рейтинг: 0 / 0
29.06.2018, 00:03
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39667449
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм.. Гуава подбила меня на взлёте. Нужно проверять достижимость для вершин орграфа типа MutableNetwork<V,E>
А у нее в утилитах есть только проверка Graph<V>
Код: java
1.
assertTrue("t1 reachable from v2", Graphs.reachableNodes(model, v1));


Код: sql
1.
2.
3.
4.
5.
6.
[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>)
...
Рейтинг: 0 / 0
29.06.2018, 01:29
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768814
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Добавлю еще сюда:
Neo4j. Это блин целая DBMS. Но пускай будет

Apache Jena. Тоже очень мощная штука. Фактически фреймворк для работы с RDF. Почти графы. Но цели - несколько иные.

RDF4j. Те-же яйца. Похожа на Jena по своему назначению.
...
Рейтинг: 0 / 0
03.02.2019, 02:21
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768821
Sergunka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergunka
Участник
maytonСоставил список.

GraphT

JUNG

Guava

Apache Commons Graph

GRPH

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

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

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


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

https://www.geeksforgeeks.org/greedy-algorithms/#greedyAlgorithmsInGraphs
...
Рейтинг: 0 / 0
03.02.2019, 06:39
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768827
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Топик тематически связан с https://www.sql.ru/forum/1306465/sparql-rdf-tehnologii-semanticheskogo-poiska-aws-neptune
...
Рейтинг: 0 / 0
03.02.2019, 09:31
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768837
Sergunka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergunka
Участник
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/
...
Рейтинг: 0 / 0
03.02.2019, 10:50
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768840
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Задача уже есть. И она в продуктиве. Но по я не могу называть здесь заказчика и прочие детали. Надеюсь понимаете.

Вообще в топиках я стараюсь охватить несколько целей. Иногда - получается. Иногда нет.
...
Рейтинг: 0 / 0
03.02.2019, 10:56
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768887
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Спасибо за статью.
...
Рейтинг: 0 / 0
03.02.2019, 13:40
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768907
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
Leonid KudryavtsevAFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей
Сортируете узлы по количеству связей и отрезаете всё, где связей меньше порога. Порог выбирается отдельным алгоритмом.
...
Рейтинг: 0 / 0
03.02.2019, 14:49
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39768920
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
alex55555Leonid KudryavtsevAFAIK в данном случае критерий: сократить граф до минимума, оставив максимум взаимосвязей
Сортируете узлы по количеству связей и отрезаете всё, где связей меньше порога. Порог выбирается отдельным алгоритмом.Нельзя так упрощать. Вы порежете мостовые рёбра и получите два несвязных графа.
...
Рейтинг: 0 / 0
03.02.2019, 15:53
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39769023
Sergunka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergunka
Участник
maytonСпасибо за статью.

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

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

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

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

...
Рейтинг: 0 / 0
03.02.2019, 23:55
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Решил сравнить библиотеки для работы с графами.
    #39992708
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ап. Привет друзья. Что изменилось? Какие новости по графам.
...
Рейтинг: 0 / 0
26.08.2020, 21:55
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39992801
mad_nazgul
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mad_nazgul
Участник
mayton
Ап. Привет друзья. Что изменилось? Какие новости по графам.


А какие новости должны быть?
Тема стухла в 980 г.г. прошлого тысячелетия. :-)
...
Рейтинг: 0 / 0
27.08.2020, 08:19
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39992810
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Моя предыдущая тема - стухла. Амазонский Нептун не взлетел. Но уже не по нашей вине а просто
кастомер отказался от проекта.

А тему я поднял в продолжение https://www.sql.ru/forum/1282300-14/chetvergovyy-arhivarius
когда понял что я стал реализовывать свою библиотечку для работы с графами.

К моему вящему ужасу когда я ищу ответы на важные вопросы ... нахожу - свои же
собственные топики с ответами на них. Вот такой вот парадокс.
...
Рейтинг: 0 / 0
27.08.2020, 09:05
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39993203
mad_nazgul
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mad_nazgul
Участник
mayton
Моя предыдущая тема - стухла. Амазонский Нептун не взлетел. Но уже не по нашей вине а просто
кастомер отказался от проекта.

А тему я поднял в продолжение https://www.sql.ru/forum/1282300-14/chetvergovyy-arhivarius
когда понял что я стал реализовывать свою библиотечку для работы с графами.

К моему вящему ужасу когда я ищу ответы на важные вопросы ... нахожу - свои же
собственные топики с ответами на них. Вот такой вот парадокс.


С графами проблема в том, что рано или поздно все сводиться к комбинаторным задачам на графах, типа поиска путей (например задача Коммивояжера).
Как выяснили в 980-х годах прошлого тысячелетия все они приводят к комбинаторному взрыву и эксподенциальному росту сложности задачи.
При этом "точные" оптимизации дают линейное уменьшение сложности задачи.
Я в 990-е г. прошлого тысячилетия работал по теме "Комбинаторные задачи на графах с нетривиальными группами автоморфизмов".
В общем после анализа источников, понял, что дело тухлое.
В 990-е года прошлого тысячилетия стали искать "не точные" решения, типа генетических алгоритмов, нечетких множеств. Щас вот взлетели нейронные сети.
Т.е. для лабораторных задач графовые БД ещё как-то работают. На реальных проектах все решения стремятся к бесконечности.
...
Рейтинг: 0 / 0
28.08.2020, 06:43
| Ответить | Цитировать | Написать  
Решил сравнить библиотеки для работы с графами.
    #39993374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да мне пока не вычислять. Пока хочеться взглянуть глазами на граф в 50 000 вершин.

Найти в нем глазами наиболее мощные вершины. Подвигать их мышкой. Может как-то вовращать весь граф.
Расплющить его на плоскости.

Еще хотелось-бы например красным цветом отметить наиболее весовые рёбра (weight > x) или как-то
толстой линией их изобразить.

А запросы пока у меня простые. Никаких тут коммивояжеров нету пока. Просто поиск топ 10 мощных вершин.
Топ 10 весомых рёбер. Соединить их в подграф. Отфильтровать только это (как-бы такая клика).
Увеличить на экране.

Нет. Я не хочу сказать что мне нужна только визуализация. Я посмотрел видосы по gremlin/tinkerpop.
Неплохо выглядит. Тоже пригодится. Но просто как способ выборки.

Вобщем вот такое вот хочу.
...
Рейтинг: 0 / 0
28.08.2020, 12:14
| Ответить | Цитировать | Написать  
25 сообщений из 30, страница 1 из 2
  1  все
Форумы / Java [игнор отключен] [закрыт для гостей] / Решил сравнить библиотеки для работы с графами.
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&fpage=12&tid=2120691]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 70ms
get topic data:
 14ms
get forum data:
 3ms
get page messages:
 79ms
get tp. blocked users:
 2ms
others: 297ms
total:  493ms
созд. / загр.: 493ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]