Как разбить граф с помощью дерева квадрантов?

У меня есть программа, которая позволяет пользователю рисовать вершины и ребра в JFrame размером 1000 на 750. Теперь мне нужно использовать дерево квадрантов для разделения входного графа в зависимости от того, сколько вершин находится в одном квадранте. Я был бы очень признателен, если бы кто-нибудь мог указать мне правильное направление, как этого добиться?

Дополнительная информация: у меня есть класс Edge, в котором хранятся: источник (вершина), цель (вершина) и вес. У меня есть класс Vertex, в котором хранятся: имя, координаты x, координаты y и Edge[] смежный список. У меня также есть класс Graph, в котором хранятся два списка ArrayList: ребра и вершины.


java graph partitioning graph-algorithm quadtree
person RikudouSennin    schedule 26.07.2012    source источник
comment
Как вы хотите разделить его? Вы отсекаете вершины, которые находятся в квадранте с наибольшим количеством вершин? В любом случае, я не думаю, что ваша проблема так уж сильно связана с графиками. Вы можете сделать разбиение, основываясь только на координатах x-y вершин.   -  person jclancy    schedule 31.07.2012
comment
Я надеялся определить верхний предел максимального количества вершин в квадранте, чтобы он продолжал разбиваться до тех пор, пока не превысит этот порог. Также каждая вершина может принадлежать только одной области. На самом деле ничего не отрезается. Для каждой области мне нужно запустить алгоритм кратчайшего пути для каждой вершины в этой области и вычислить флаги ребер.   -  person RikudouSennin    schedule 03.08.2012
comment
@ jclancy, в конце концов, я воспользовался вашим методом для разделения графика.   -  person RikudouSennin    schedule 26.08.2012

Ответы (2)


arrow_upward
5
arrow_downward

Недавно я реализовал код, который должен решить вашу проблему. Это бесплатно для загрузки в моем недавнем сообщении в блоге. Quadtrees для пространственной декомпозиции, реализация Java http://kirstywilliams.co.uk/blog/2012/08/quadtrees-java-implementation/

person Kirsty Williams    schedule 16.08.2012

arrow_upward
1
arrow_downward

Еще несколько реализаций quadtree, которые имеют лицензию Apache:

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

Еще один интересный репозиторий ( но AGPL я думаю как сам neo4j) с некоторыми пространственными коллекциями.

person Karussell    schedule 30.08.2012