如何在 JgraphT 中创建诱导子图

Question

设G=(V,E)为无向图。我想为给定的节点子集 U 和 Java 中的 JgraphT 创建一个导出子图。

这是一个邻接表。

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


    }

}

假设我有三个节点 0,1,3，并且想创建一个导出子图，这意味着我将有一个包含节点 0,1,3 和边 0-1,0-3,1-3 的子图。我能找到的唯一来源是 here，但是，我不知道如何解决这个问题。

Answer 1

要在 JGraphT 中创建导出子图，请使用 MaskSubgraph or AsSubgraph 类。在您的特定用例中，使用 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);

如何在 JgraphT 中创建诱导子图

how to create an induced sub graph in JgraphT

java

jgrapht