CODEWITHSUNDEEP
javagraphgraph-theoryjgraphtsubgraph
asajadi84
asajadi84

Reputation: 559

Get all subgraphs in JGraphT

How can I get all possible subgraphs of a graph in JGraphT in a List<MyGraph> or Set<MyGraph> collection? I've read the documentation of JGraphT, but I couldn't find anything to help me with that particular issue.

Upvotes: 0

Views: 812

Answers (1)

Joris Kinable
Joris Kinable

Reputation: 2411

The answer to this question depends on whether the OP wants a vertex-induced subgraph or an edge-induced subgraph. To create a vertex or edge induced subgraph in JGraphT, use the AsSubgraph class. There is no method that will simply generate all possible subgraphs as this is a very uncommon procedure, but it is easy to implement yourself. Do notice that there are 2^n possible vertex induced subgraphs, where n is the number of vertices. So the number of subgraphs is huge.

  1. Create a List<Set> containing all possible subsets of vertices. This is called a powerset (there are many SO posts on how to generate a powerset)
  2. For each set in your powerset, generate an induced subgraph using AsSubgraph.

Coarsely, the code looks like this:

//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);

To implement the powerSet function, many examples can be found on SO. To compute edge induced subgraphs, repeat the above but instead of graph.vertexSet() use graph.edgeSet();

Upvotes: 1

Related Questions