CODEWITHSUNDEEP
javajgrapht
sergey_208
sergey_208

Reputation: 654

how to create an induced sub graph in JgraphT

Let G=(V,E) be an undirected graph. I'd like to create an induced sub graph for a given subset of nodes U with JgraphT in Java.

Here is an adjacency list.

0 1
0 3
1 0
1 2
1 3
2 1
2 3
3 0
3 1
3 2

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.HashSet;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.Graphs;
public class RatioBased {

    public static void main(String[] args) {

        String DATADIR = ...; // specify the DIR

        Graph<Integer, DefaultEdge> G =  new SimpleGraph<>(DefaultEdge.class); // create gragh G object

        HashMap<Integer, HashSet<Integer>> adjacencyList = new HashMap<Integer, HashSet<Integer>>();


        Path filePath = Paths.get(DATADIR).resolve(Paths.get("adjacencyList.txt"));         
        try {
            Files.lines(filePath).forEach(line -> {
                String[] columnValues = line.split("\\s+");
                adjacencyList.computeIfAbsent(Integer.valueOf(columnValues[0]),
                        k -> new HashSet<>()).add(Integer.valueOf(columnValues[1]));
            });
        } catch (IOException e) {
            e.printStackTrace();
        }

        int numNodes =4;

        for(int i = 0 ; i <numNodes; i++) //add nodes
             G.addVertex(i);        

        for(int i = 0 ; i< numNodes; i++) { //add edges
            if(adjacencyList.get(i) != null) {
                for(Integer j : adjacencyList.get(i)) {
                     G.addEdge(i, j);
                }
            }
        }


    }

}

Suppose I am given with three nodes 0,1,3 and would like to create an induced sub graph meaning that I would have a sub graph with nodes 0,1,3 and edges 0-1,0-3,1-3. The only source I could find is here, however, I could not figure out how to get away with this.

Upvotes: 0

Views: 1167

Answers (1)

Joris Kinable
Joris Kinable

Reputation: 2411

To create induced subgraphs in JGraphT, use the MaskSubgraph or AsSubgraph classes. In your particular usecase, use the AsSubgraph:

Graph<Integer,DefaultEdge> g=new SimpleGraph<>(DefaultEdge.class)
...
Set<Integer> vertexSubset=new HashSet<>(Arrays.asList(1,2,3));
Graph<Integer,DefaultEdge> inducedSubgraph=new AsSubgraph(g, vertexSubset);

Upvotes: 1

Related Questions