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