通过删除某些边和顶点来压缩我的图（JGraphT）的算法

Question

我有一个图表，我想通过创建一个新图表来压缩它。所以顶点是“拓扑节点”，边是不同的对象，但它们有相同的父对象 class。现在在示例中我想删除类型为 b.

的所有边

顶点“拓扑节点”的编号为 (1,2,3)。没有比这更简单的了。边有对这些节点的引用。

示例：

  Graph {
    //uncompressed Graph
    1 -- 2 [label="a1"];
    2 -- 3 [label="b1"];
    3 -- 4 [label="b2"];
    4 -- 5 [label="b3"];
    5 -- 1 [label="a2"];
  }

Graph {
    //compressed Graph
    5 -- 1 [label="a2"];
    5 -- 1 [label="a1"];
}

我目前的情况是：

public void compression(Graph<TopologicalNode, IdentifiedObject> unCompressedGraph){


    Set<SubGeographicalRegion> networks = datamodel.equipmentProfile.keySet();
    for (SubGeographicalRegion subGeographicalRegion : networks) {
        Graph<TopologicalNode, IdentifiedObject> compressedGraph = GraphTypeBuilder
                .<TopologicalNode, IdentifiedObject>undirected().allowingSelfLoops(true)
                .edgeClass(IdentifiedObject.class).buildGraph();

        ArrayList<PowerTransformer> powerTransformers = getPTsFromSubnet(subGeographicalRegion);

        for(PowerTransformer powerTransformer :powerTransformers) {
            for (PowerTransformerEnd powerTransformerEnd : powerTransformer.getEnds()) {
                if (unCompressedGraph.vertexSet().stream().filter(r -> r.equals(powerTransformerEnd.getTerminal().getTopologicalNode())).findAny().isPresent()) {
                    TopologicalNode start = unCompressedGraph.vertexSet().stream().filter(r -> r.equals(powerTransformerEnd.getTerminal().getTopologicalNode())).findAny().get();
                    compressedGraph.addVertex(start);
                    ArrayList<TopologicalNode> nodesToBeCompressed = new ArrayList<>();
                    Iterator<TopologicalNode> iterator = new DepthFirstIterator<>(unCompressedGraph, start);
                    while (iterator.hasNext()) {
                        TopologicalNode nextNode = iterator.next();
                     
                        Set<IdentifiedObject> eqs = unCompressedGraph.edgesOf(nextNode);
                        //TODO: How to go on?
                    }
                }
            }
        }
    }
}

所以我真的不知道如何继续，我是 JGraphT 的新手。

Answer 1

您似乎打算通过移除边并合并边接触的节点来删除边。您可以通过以下方式做到这一点：

在图中找到边 e1 及其两个端点，比如 u 和 v。

2a。如果u和v之间有多条边，那么去掉边就可以了，没有别的办法。

2b。如果 u 和 v 之间只有一条边，我们进行如下处理。创建一个新的顶点 w。顶点 w 将是新的 'merged' 节点。删除边 e1。连接从 u 到它的邻居到 w 的所有边。对 v 做同样的事情。删除节点 u 和 v.

在代码中，这转换为：

public static void main(String[] args){
    //Create a graph
    Graph<Integer, String> g =
            new Pseudograph<>(SupplierUtil.createIntegerSupplier(1), null, false);
    for(int i=0; i<5; i++)
        g.addVertex();
    g.addEdge(1,2,"a1");
    g.addEdge(2,3,"b1");
    g.addEdge(3,4,"b2");
    g.addEdge(4,5,"b3");
    g.addEdge(5,1,"a2");

    removeEdge(g,"b1");
    removeEdge(g,"b2");
    removeEdge(g,"b3");
    System.out.println(g);
}
private static void removeEdge(Graph<Integer, String> g, String edge){
    if(!g.containsEdge(edge))
        throw new RuntimeException(String.format("Cannot delete edge %s because this edge does not exist in the graph!", edge));

    Integer u=g.getEdgeSource(edge);
    Integer v=g.getEdgeTarget(edge);

    //Case 2a: there are multiple edges between vertex u and v
    if(g.getAllEdges(u,v).size()>1){
        g.removeEdge(edge);
        return;
    }
    //Case 2b: there is only 1 edge between u and v. Delete the edge, and merge nodes u and v into new node w.
    g.removeEdge(edge);
    Integer w=g.addVertex();
    Set<String> edgesOfU = new HashSet<>(g.edgesOf(u));
    Set<String> edgesOfV = new HashSet<>(g.edgesOf(v));
    //Remove all edges between u and its neighbors and re-add those edges for node w
    for(String e : edgesOfU){
        Integer neighbor = Graphs.getOppositeVertex(g,e,u);
        g.removeEdge(e);
        g.addEdge(w,neighbor,e);
    }
    //Remove all edges between v and its neighbors and re-add those edges for node w
    for(String e : edgesOfV){
        Integer neighbor = Graphs.getOppositeVertex(g,e,v);
        g.removeEdge(e);
        g.addEdge(w,neighbor,e);
    }
    //Nodes u and v have been replaced by w, so we can safely remove u and v
    g.removeVertex(u);
    g.removeVertex(v);
}

执行此代码时，我们得到了所需的图形：

([1, 8], [a1={8,1}, a2={8,1}])

请注意，delete-and-merge 操作可能会在同一节点或 self-loops 之间生成具有多条边的图，因此我们需要使用伪图作为基础图类型。

通过删除某些边和顶点来压缩我的图（JGraphT）的算法

Algorithm to compress my Graph (JGraphT) by delete certain edges and vertexes

java

jgrapht