Модуль Julia для подграфирования графа (узлы/вершины и ребра) без изменения или перемаркировки индексов узлов?

Примечание по терминологии: "vertices"="nodes", "метки вершин/узлов" = "indices"

LightGraphs в Julia изменяет индексы узлов при создании индуцированных подграфов.

Например, если граф имеет узлы [1, 2, 3, 4], его LightGraphs.induced_subgraph, индуцированный узлами [3,4], будет новым графом с узлами [3,4], переименованными в [1,2].

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

Подграфы в networkx в Python, например, сохраняют метки узлов.

Можно использовать MetaGraphs, добавив атрибут узла :id, который сохраняется путем подграфирования, но тогда вам придется написать много дополнительного кода для преобразования между индексами узлов и узлами :id.

Разве не существует пакета Julia, который «просто работает», когда дело доходит до подграфов и сохранения идентификаторов узлов?


julia undirected-graph networkx subgraph lightgraphs
person OrangeSherbet    schedule 08.12.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Сначала я хотел бы воспользоваться возможностью, чтобы прояснить некоторую терминологию: LightGraphs сам по себе не диктует тип графика. Это набор алгоритмов и спецификация интерфейса. Ограничения, которые вы видите, относятся к SimpleGraphs, типу графика, который поставляется с пакетом LightGraphs и является типом по умолчанию для Graph и DiGraph.

Причина, по которой это важно, заключается в том, что очень легко (или, по крайней мере, должно быть) создать тип графика, который делает именно то, что вам нужно, и который может использовать преимущества существующей инфраструктуры LightGraphs. Все, что вам (теоретически) нужно сделать, это реализовать интерфейсные функции, описанные в src/interface.jl. Если вы реализуете их правильно, все алгоритмы LightGraphs должны просто работать (tm) (хотя они могут быть неэффективными; это зависит от выбранных вами структур данных и принятых вами решений по интерфейсу).

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

person sbromberger    schedule 08.12.2019
comment
На самом деле SimpleGraphs имеет поведение, которое я ищу. Он сохраняет индексы узлов для подграфов (SimpleGraphs.induce()). Похоже, что LightGraphs сам объединяет индексы в {1, 2,... |V|} во время подграфа. Поправьте меня если я ошибаюсь. Тогда я просто буду использовать SimpleGraphs. - person OrangeSherbet; 09.12.2019
comment
SimpleGraphs возвращает карту для induced_subgraph(), которая сообщает вам, где были ваши исходные вершины. Если этого достаточно, то да - вы хороши. Обратите внимание, что доступ к графу с использованием индексов (g[[1,3,5,7]]) аналогичен induced_subgraph(), но без этого сопоставления вершин. - person sbromberger; 09.12.2019
comment
Меня немного смущает, что SimpleGraphs возвращает карту для induced_subgraph. LightGraphs.induced_subgraph возвращает кортеж (graph, vmap) с новым графом, имеющим объединенные индексы узлов, что требует много дополнительного кода для вычисления vmap1[vmap2[vmap3[....vertex_idx]]] вниз в слоях рекурсии для обработки подграфов подграфы. SimpleGraphs.induce возвращает только новый график с неизмененными идентификаторами узлов, не о чем беспокоиться vmap, что является требуемым поведением. - person OrangeSherbet; 09.12.2019
comment
О, вы говорите о SimpleGraphs.jl, несвязанном пакете? Я не очень знаком с ним, но если он делает то, что вам нужно, то это здорово. Здесь происходит некоторая перегрузка имен (за этим стоит история, но лучше оставить ее в прошлом). В любом случае, рад слышать, что вы нашли пакет, отвечающий вашим потребностям. - person sbromberger; 09.12.2019
comment
О, какой несчастный случай. Ха-ха. Спасибо за помощь. - person OrangeSherbet; 09.12.2019