java是否可以创建具有特定冗余级别的连通图？

Question

我在看jgraphT，但我不是很有经验，它缺乏一点文档

我有一些节点，我想创建一个连接的拓扑，提供一些冗余。 例如：

我从n1，n2，n3，n4开始

我希望能够与每个节点通信，但仍然有多个可能的路径，以便在一个节点掉下时，其他节点仍然可以通信

jgraphT能为我创建一个好的拓扑吗？也许给一些权重，使其对某些节点的估值高于其他节点

或者你知道其他图书馆也有同样的成就？ 此外，如果我能生成某种网页来记录我创建的拓扑结构，那就太好了

Answer 1

有点太长，无法发表评论：

我认为你要找的东西的形式特征还不够明确。显然，您正在寻找具有特定连接性（http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29）的图，但是基于当前的问题，可以建议使用CompleteGraphGenerator

关键点可能是你提到的“一些冗余”和“一些权重”（以及记录拓扑结构的“一些网页”）

想必，你想要最少的冗余。也就是说，您可能希望插入额外边的最小数量，以便在移除k任意顶点后，图形仍保持连接

我不知道有哪个图书馆能做到这一点

基于JGraphT提供的两个粗略想法：

• 可以计算最小切割，并在切割两侧的顶点之间插入额外的边。这里的http://jgrapht.org/javadoc/org/jgrapht/alg/StoerWagnerMinimumCut.html可能是一个起点

• 可以计算强连接的组件，并在这些组件之间插入额外的边。强连通分量可以用http://jgrapht.org/javadoc/org/jgrapht/alg/StrongConnectivityInspector.html

---

编辑：

---

添加了基于上述第一个想法的实现。ensureConnectivity方法将确保给定的图具有如下特定的连接性：它使用StoerWagnerMinimumCut类计算最小割。此类的输出是顶点列表，这些顶点是将由切割创建的组件之一。computeCutVertices方法将计算实际必须移除的顶点，以便将图形划分为多个组件。对于这些顶点中的每一个，将计算邻域集。这些邻居中的任意两个（尚未连接的）将使用新的边连接。整个过程将重复，直到“切割顶点”的数量大于所需的连通性

请注意，这还没有得到广泛的测试，可能会有更优雅或有效的解决方案，但。。。总的来说，它应该是有效的

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.StoerWagnerMinimumCut;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class GraphConnectivityTest
{
    public static void main(String[] args)
    {
        UndirectedGraph<String, DefaultEdge> graph =
            new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        String v0 = "0";
        String v1 = "1";
        String v2 = "2";
        String v3 = "3";
        String v4 = "4";
        String v5 = "5";
        String v6 = "6";
        String v7 = "7";
        graph.addVertex(v0);
        graph.addVertex(v1);
        graph.addVertex(v2);
        graph.addVertex(v3);
        graph.addVertex(v4);
        graph.addVertex(v5);
        graph.addVertex(v6);
        graph.addVertex(v7);

        graph.addEdge(v0, v1);
        graph.addEdge(v0, v2);
        graph.addEdge(v0, v3);
        graph.addEdge(v1, v2);
        graph.addEdge(v1, v3);
        graph.addEdge(v2, v3);

        graph.addEdge(v4, v5);
        graph.addEdge(v4, v6);
        graph.addEdge(v4, v7);
        graph.addEdge(v5, v6);
        graph.addEdge(v5, v7);
        graph.addEdge(v6, v7);

        graph.addEdge(v1, v4);
        //graph.addEdge(v3, v6);

        ensureConnectivity(graph, 2);
    }

    /**
     * Make sure that the given graph has the specified connectivity.
     * That is: Make sure that more than the given number of vertices
     * have to be removed in order to split the graph into two
     * components.
     * 
     * @param graph The graph
     * @param connectivity The desired connectivity
     */
    private static <V, E> void ensureConnectivity(
        UndirectedGraph<V, E> graph, int connectivity)
    {
        System.out.println("Desired connectivity is "+connectivity);
        while (true)
        {
            StoerWagnerMinimumCut<V, E> m = 
                new StoerWagnerMinimumCut<V, E>(graph);
            Set<V> minCut = m.minCut();

            Set<V> cutVertices = 
                computeCutVertices(graph, minCut);
            System.out.println("Removing "+cutVertices+" will create two components");
            if (cutVertices.size() > connectivity)
            {
                System.out.println("Reached desired connectivity");
                return;
            }
            for (V cutVertex : cutVertices)
            {
                E edge = addBridgeEdge(graph, cutVertex);
                System.out.println("Added edge "+edge);
            }
        }
    }


    /**
     * Creates an edge between two arbitrary neighbors of the
     * given vertex in the given graph that have not yet
     * been connected.
     * 
     * @param graph The graph
     * @param v The vertex
     */
    private static <V, E> E addBridgeEdge(Graph<V, E> graph, V v)
    {
        Set<E> edges = graph.edgesOf(v);
        Set<V> neighbors = new LinkedHashSet<V>();
        for (E edge : edges)
        {
            V v0 = graph.getEdgeSource(edge);
            V v1 = graph.getEdgeTarget(edge);
            neighbors.add(v0);
            neighbors.add(v1);
        }
        neighbors.remove(v);

        List<V> neighborsList = new ArrayList<V>(neighbors);
        for (int i=0; i<neighborsList.size(); i++)
        {
            for (int j=i+1; j<neighborsList.size(); j++)
            {
                V n0 = neighborsList.get(i);
                V n1 = neighborsList.get(j);
                E present = graph.getEdge(n0, n1);
                if (present == null)
                {
                    return graph.addEdge(n0, n1);
                }
            }
        }
        return null;
    }


    /**
     * Compute the vertices in the given graph that have to be 
     * removed from the graph in order to split it into two 
     * components (of which one only contains the given 
     * "minCut" vertices)
     * 
     * @param graph The graph
     * @param minCut The set of vertices on one side of the cut
     * @return The vertices that have to be removed 
     */
    private static <V, E> Set<V> computeCutVertices(
        Graph<V, E> graph, Set<V> minCut)
    {
        Set<V> cutVertices = new LinkedHashSet<V>();
        for (V v : minCut)
        {
            Set<E> edges = graph.edgesOf(v);
            for (E edge : edges)
            {
                V v0 = graph.getEdgeSource(edge);
                V v1 = graph.getEdgeTarget(edge);
                if (minCut.contains(v0) && !minCut.contains(v1))
                {
                    cutVertices.add(v1);
                }
                if (!minCut.contains(v0) && minCut.contains(v1))
                {
                    cutVertices.add(v0);
                }
            }
        }
        return cutVertices;
    }
}