0

我在看 jgraphT 但我不是很有经验，而且它缺乏一些文档。

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

我从 n1,n2,n3,n4 开始

我希望能够与每个节点通信，但仍然有不止一个可能的路径，这样如果一个节点下降，其他节点仍然可以通信。

jgraphT 可以为我创建一个好的拓扑吗？也许给一些权重，以便它比其他节点更重视某些节点？

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

4

1 回答 1

2

评论有点长：

我认为您正在寻找的形式特征没有足够清楚地指定。您显然正在寻找具有一定连通性的图表（http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29），但根据当前问题，可以建议使用CompleteGraphGenerator.

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

大概，你想要一个最小的冗余。也就是说，您可能希望插入最少数量的附加边，以便在删除k任意顶点后图形仍然是连接的。

我不知道可以开箱即用的库。

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

编辑：

基于上面提到的第一个想法添加了一个实现。该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;
    }
}
于 2014-03-26T22:35:04.860 回答