#java #graph #graph-theory #jgrapht #subgraph
#java #График #теория графов #jgrapht #подграф
Вопрос:
Как я могу получить все возможные подграфы графа в JGraphT в List<MyGraph> Set<MyGraph> коллекции or? Я прочитал документацию JGraphT, но не смог найти ничего, что могло бы помочь мне с этой конкретной проблемой.
Комментарии:
1. Что именно вы пробовали сами? Приведите минимальный пример, в котором вы застряли.
Ответ №1:
Ответ на этот вопрос зависит от того, хочет ли OP индуцированный вершиной подграф или индуцированный ребром подграф. Чтобы создать вершинный или реберный подграф в JGraphT, используйте класс AsSubgraph . Не существует метода, который просто сгенерирует все возможные подграфы, поскольку это очень необычная процедура, но ее легко реализовать самостоятельно. Обратите внимание 2^n , что возможны индуцированные вершинами подграфы, где n — количество вершин. Таким образом, количество подграфов огромно.
- Создайте список<Set>, содержащий все возможные подмножества вершин. Это называется набором полномочий (есть много сообщений SO о том, как сгенерировать набор полномочий)
- Для каждого набора в вашем powerset сгенерируйте индуцированный подграф с помощью
AsSubgraph.
Грубо говоря, код выглядит так:
//Initiate some graph. The vertex/edge type is irrelevant for this question
Graph<Integer,DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);
...
//Generate powerset
List<Set<Integer>> powerSet = powerSet(graph.vertexSet());
//Create subgraphs:
for(Set<Integer> subset : powerSet)
Graph<Integer,DefaultEdge> subGraph = new AsSubgraph(graph, subset);
Для реализации функции powerSet на SO можно найти много примеров. Чтобы вычислить подграфы, индуцированные ребрами, повторите описанное выше, но вместо graph.vertexSet() используйте graph.edgeSet();