c# - 大型无向图的高效存储、查找和操作

Question

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

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

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

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

两种可能性:

• bool[numNodes, numNodes] 和 Dictionary<string, int> 将每个节点名称与索引匹配。优点:简单、快速的查找。缺点:无法轻松删除或添加节点(必须添加/删除行/列)、冗余(必须小心 g[n1, n2] 与 g[n2, n1] )、笨拙的语法，因为我每次都必须通过 HashMap。

• HashSet<HashSet<string>> 。优点:直观，节点直接由字符串标识，易于“添加/删除节点”，因为只存储边，节点本身是隐式的。缺点:可能输入垃圾输入(“连接”三个节点的边，因为集合有三个成员)。

关于第二个选项，我也不清楚一些事情:

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

Answer 1

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

1. 规范化键，无论在边的描述中首先指定哪个节点，键都是相同的。在我的测试中，我只是选择将序号比较值最低的节点作为键中的第一个组件。

2. 在哈希表中创建两个条目，每个条目对应边的每个方向。

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

带有键规范化的字符串连接和元组版本的工作原理大致相同:在 Release模式下的 VirtualBox VM 中，在大约 3 秒内完成了大约 200 万次随机查找。

为了查看 key 规范化是否淹没了查找操作的效果，第三种实现不进行 key 规范化，但在边的两个可能方向上保持对称条目。这似乎在查找时慢了大约 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();
    }
}