Какой алгоритм можно использовать для разбиения графа, чтобы сделать значение каждой разбитой группы (или компонента) равным или сбалансированным?

Question

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

<Data information>
[node_id]: n_1, n_2, n_3 ,, etc
[node_value]: 10, 5, 20,, etc
[node_adjacency_data] : Please refer to the attached picture.
[node_latitude]: 37.25201, 37.25211, 37.25219,, etc
[node_longitude]: 127.10195, 127.11321, 127.11377,, etc 

Answer 1

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

Самым известным алгоритмом разбиения графов таким способом является METIS , и есть хорошоОболочка Python для оптимизированной реализации C (которую вы должны собрать / установить отдельно).В качестве входных данных он принимает графы networkx или простые списки смежности.

METIS берет граф с взвешенными вершинами и ребрами и возвращает до заданного числа разбиений, минимизируя вес разрезаемых ребер.Вам все равно придется выбрать, на сколько частей вы хотите разбить ваш график.

Вот пример кода, использующего библиотеку Python METIS для решения поставленной вами задачи:

import networkx as nx
import metis

# Set up graph structure
G = nx.Graph()
G.add_edges_from([ (0,1), (0,2), (0,3), (1, 2), (3, 4) ])

# Add node weights to graph
for i, value in enumerate([1,3,2,4,3]):
    G.node[i]['node_value'] = value

# tell METIS which node attribute to use for 
G.graph['node_weight_attr'] = 'node_value' 

# Get at MOST two partitions from METIS
(cut, parts) = metis.part_graph(G, 2) 
# parts == [0, 0, 0, 1, 1]

# Assuming you have PyDot installed, produce a DOT description of the graph:
colors = ['red', 'blue']
for i, part in enumerate(parts):
    G.node[i]['color'] = colors[part]
nx.nx_pydot.write_dot(G, 'example.dot')

МыЗатем вы можете использовать GraphViz для визуализации раздела:

Какой раздел вы задали в своем вопросе.