高效存储、查找和操作大型无向图

我有一个无向图G，大约有5000个节点。任何一对节点都可以通过边连接。边的长度、方向或其他要素无关紧要，两点之间最多只能有一个边，因此节点之间的关系是二进制的。因此，总潜在边缘12497500。

每个节点都由字符串名称标识，而不是数字。

我想存储这样的图形（作为输入数据加载到我的程序中），但我不确定哪种数据结构最好。

我需要多次查找给定的一对节点是否连接，因此查找性能可能是主要关注点。
添加和删除元素的性能成本不是问题。
如果可能的话，我还想保持语法简单优雅，以减少引入错误的可能性并使调试更容易。

两种可能性：

bool[numNodes, numNodes]和Dictionary<string, int>，用于将每个节点名称与索引匹配。优点：简单，快速的查找。缺点：不能轻易删除或添加节点（必须添加/删除行/列），冗余（必须小心g[n1, n2]与g[n2, n1]），笨拙的语法，因为我每次都必须通过HashMap。
HashSet<HashSet<string>> .优点：直观，节点直接由字符串标识，易于"添加/删除节点"，因为只存储边缘并且节点本身是隐式的。缺点：可以输入垃圾输入（"连接"三个节点的边，因为集合有三个成员）。

关于第二种选择，我也不清楚一些事情：

它会比bool数组占用更多的内存吗？
两个 .NET 集是否等同于数学集，即当且仅当它们具有完全相同的成员（而不是通过元素的容量或顺序等进行区分）以HashSet成员身份而言，它们是相等的？（即查询outerSets.Contains(new HashSet<string>{"node1", "node2"})实际上会起作用吗？
查找会比bool数组花费更长的时间吗？

我很好奇在生成表示哈希表中边缘的键时使用字符串连接与元组，以便接近 O（1）查找性能。这里有两种处理无向边缘要求的可能性：

规范化密钥，以便无论在边缘描述中首先指定哪个节点，它都是相同的。在我的测试中，我只是选择将序数比较值最低的节点作为键中的第一个组件。
在哈希表中创建两个条目，边的每个方向一个。

这里的一个关键假设是字符串节点标识符不是很长，因此键规范化相对于查找来说是廉价的。

具有键规范化的字符串串联和元组版本似乎工作原理大致相同：在发布模式下的 VirtualBox VM 中，在大约 3 秒内完成了大约 200 万次随机查找。

为了查看键规范化是否淹没了查找操作的效果，第三个实现不执行键归一化，而是保持相对于边缘的两个可能方向的对称条目。这似乎在查找中慢了大约 30-40%，这有点出乎意料（对我来说）。也许底层哈希表桶的平均占用率更高，因为元素数量是其两倍，每个哈希桶中需要更长的线性搜索（平均）？

interface IEdgeCollection
{
    bool AddEdge(string node1, string node2);
    bool ContainsEdge(string node1, string node2);
    bool RemoveEdge(string node1, string node2);
}
class EdgeSet1 : IEdgeCollection
{
    private HashSet<string> _edges = new HashSet<string>();
    private static string MakeEdgeKey(string node1, string node2)
    {
        return StringComparer.Ordinal.Compare(node1, node2) < 0 ? node1 + node2 : node2 + node1;
    }
    public bool AddEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Add(key);
    }
    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }
    public bool RemoveEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Remove(key);
    }
}
class EdgeSet2 : IEdgeCollection
{
    private HashSet<Tuple<string, string>> _edges = new HashSet<Tuple<string, string>>();
    private static Tuple<string, string> MakeEdgeKey(string node1, string node2)
    {
        return StringComparer.Ordinal.Compare(node1, node2) < 0 
            ? new Tuple<string, string>(node1, node2) 
            : new Tuple<string, string>(node2, node1);
    }
    public bool AddEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Add(key);
    }
    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }
    public bool RemoveEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Remove(key);
    }
}
class EdgeSet3 : IEdgeCollection
{
    private HashSet<Tuple<string, string>> _edges = new HashSet<Tuple<string, string>>();
    private static Tuple<string, string> MakeEdgeKey(string node1, string node2)
    {
        return new Tuple<string, string>(node1, node2);
    }
    public bool AddEdge(string node1, string node2)
    {
        var key1 = MakeEdgeKey(node1, node2);
        var key2 = MakeEdgeKey(node2, node1);
        return _edges.Add(key1) && _edges.Add(key2);
    }
    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }
    public bool RemoveEdge(string node1, string node2)
    {
        var key1 = MakeEdgeKey(node1, node2);
        var key2 = MakeEdgeKey(node2, node1);
        return _edges.Remove(key1) && _edges.Remove(key2);
    }
}
class Program
{
    static void Test(string[] nodes, IEdgeCollection edges, int edgeCount)
    {
        // use edgeCount as seed to rng to ensure test reproducibility
        var rng = new Random(edgeCount);
        // store known edges in a separate data structure for validation
        var edgeList = new List<Tuple<string, string>>();
        Stopwatch stopwatch = new Stopwatch();
        // randomly generated edges
        stopwatch.Start();
        for (int i = 0; i < edgeCount; i++)
        {
            string node1 = nodes[rng.Next(nodes.Length)];
            string node2 = nodes[rng.Next(nodes.Length)];
            edges.AddEdge(node1, node2);
            edgeList.Add(new Tuple<string, string>(node1, node2));
        }
        var addElapsed = stopwatch.Elapsed;
        // non random lookups
        int nonRandomFound = 0;
        stopwatch.Start();
        foreach (var edge in edgeList)
        {
            if (edges.ContainsEdge(edge.Item1, edge.Item2))
                nonRandomFound++;
        }
        var nonRandomLookupElapsed = stopwatch.Elapsed;
        if (nonRandomFound != edgeList.Count)
        {
            Console.WriteLine("The edge collection {0} is not working right!", edges.GetType().FullName);
            return;
        }
        // random lookups
        int randomFound = 0;
        stopwatch.Start();
        for (int i = 0; i < edgeCount; i++)
        {
            string node1 = nodes[rng.Next(nodes.Length)];
            string node2 = nodes[rng.Next(nodes.Length)];
            if (edges.ContainsEdge(node1, node2))
                randomFound++;
        }
        var randomLookupElapsed = stopwatch.Elapsed;
        // remove all
        stopwatch.Start();
        foreach (var edge in edgeList)
        {
            edges.RemoveEdge(edge.Item1, edge.Item2);
        }
        var removeElapsed = stopwatch.Elapsed;
        Console.WriteLine("Test: {0} with {1} edges: {2}s addition, {3}s non-random lookup, {4}s random lookup, {5}s removal",
            edges.GetType().FullName,
            edgeCount,
            addElapsed.TotalSeconds,
            nonRandomLookupElapsed.TotalSeconds,
            randomLookupElapsed.TotalSeconds,
            removeElapsed.TotalSeconds);
    }

    static void Main(string[] args)
    {
        var rng = new Random();
        var nodes = new string[5000];
        for (int i = 0; i < nodes.Length; i++)
        {
            StringBuilder name = new StringBuilder();
            int length = rng.Next(7, 15);
            for (int j = 0; j < length; j++)
            {
                name.Append((char) rng.Next(32, 127));
            }
            nodes[i] = name.ToString();
        }
        IEdgeCollection edges1 = new EdgeSet1();
        IEdgeCollection edges2 = new EdgeSet2();
        IEdgeCollection edges3 = new EdgeSet3();
        Test(nodes, edges1, 2000000);
        Test(nodes, edges2, 2000000);
        Test(nodes, edges3, 2000000);
        Console.ReadLine();
    }
}

C5 集合库有一些关于图形的有用内容

http://www.itu.dk/research/c5/

这个问题，完整无向图的最有效实现，看起来也很有用。

SortedDictionary 在引擎盖下，一棵高度平衡的红黑树，所以查找是 O（log n）。

相关内容

最新更新

热门标签：