简单无向图的表示
Representation of a simple undirected graph
我需要你的专业知识：
我即将在 C++ 中实现一个图形 class 并考虑正确的表示形式。这些图简单且无向。顶点数量目前最多可达 1000，但将来可能会更高。边数高达 200k 甚至更高。每个顶点都有一个颜色 (int) 和一个 id (int)。边传输的信息不超过连接到顶点的信息。
我存储了图表，只需要访问 x 和 y 是否连接 - 我经常需要这个。
初始化后，我从不删除或添加新的顶点或边（N = 顶点数和 M = 从一开始就给定的边数）！
我已经可以使用的一个表示：
一个邻接列表展开成一个长列表。与此表示一起出现的是一个数组，其中包含每个顶点的起始索引。存储 O(2M) 并检查 x 和 y 之间的边缘是否平均为 O(n/m)
我想到的表示法：
我们的想法是，不是将邻接列表展开到一个数组中，而是使用邻接矩阵来完成。所以存储 O(N^2)？是的，但我想在一个字节以外的一位中存储一个边缘。（实际上是对称的 2 位）
示例：假设 N=8，然后创建一个长度为 8（64 位）的向量。在 0 上初始化每个条目。如果顶点 3 和顶点 5 之间有一条边，则将 pow(2,5) 添加到属于顶点 3 且对称的我的向量的条目。因此，当 3 和 5 之间有一条边时，顶点 5 的位置处的顶点 3 的条目中就有一个 1。将我的图形插入到这个数据结构中后，我认为应该能够在恒定时间内通过一个访问邻域二元运算：3和5相连吗？是的，如果 v[3] ^ pow(2,5) == 0。当顶点数超过 8 个时，每个顶点都需要在向量中获得多个条目，我需要执行一次模和一次除法运算访问正确的位置。
您如何看待第二种解决方案 - 它是否已经为人所知并正在使用？
考虑 O(1) 的访问我错了吗？
是否付出了很多努力却没有真正的性能提升？
我被告知在一个大列表中加载两种表示的原因是缓存改进。
我很高兴收到有关此想法的一些反馈。我可能离题太远了 - 在那种情况下请善待 :D
如果你选择一个位矩阵，那么内存使用量是 O(V^2)，所以大约 1Mb 位或 128KB，其中略低于一半确实是重复的。
如果你制作一个边数组 O(E) 和另一个索引数组到从顶点到它的第一个边的边，你使用 200K*sizeof(int) 或 800KB，这是更多，一半它也是重复的（A-B 和 B-A 相同），这里实际上可以保存。同样，如果您知道（或者可以从中模板化）顶点数可以存储在 uint16_t 一半中可以再次保存。
要节省一半，您只需检查哪个顶点的编号较小并检查其边。
要找出何时停止查找，您可以使用下一个顶点上的索引。
因此对于您的数字，使用位矩阵很好甚至很好。
第一个问题出现在 (V^2)/8 > (E*4) 时，尽管 Edge 算法中的二进制搜索仍然比检查位慢得多。如果我们设置 E = V * 200（1000 个顶点 vs 200K 边）
，就会发生这种情况
V*V/8 > V*200*4
V/8 > 200*4
V > 200*4*8 = 6400
这将是 5120000 ~ 5MB 很容易放入如今的 L3 缓存中。如果连通性（此处为每个顶点的平均连接数）高于 200 则更好。
检查边缘也会花费 lg2(connectivity)*K(mispredicts)，这会变得相当陡峭。检查位矩阵将是 O(1).
除其他外，您需要测量位矩阵何时显着破坏 L3 而边缘列表仍适合 L3 以及何时溢出到虚拟内存中。
换句话说，具有高连通性的位矩阵应该击败具有低得多的连通性或更多数量的顶点的边列表，边列表可能更快。
具有 200,000 条边的 1000x1000 矩阵将非常稀疏。由于图是无向的，所以矩阵中的边会被写两次：
VerticeA -> VerticeB and VerticeB -> VerticeA
你最终会填满矩阵的 40%，其余的将是空的。
边
这里我能想到的最好方法是使用 2D 布尔值向量:
std::vector<std::vector<bool>> matrix(1000, std::vector<bool>(1000, false));
查找将花费 O(1) 时间，std::vector<bool> 通过为每个布尔值使用一个位来节省 space。您最终将使用 1Mbit 或 ~128kB (125 kB) 的内存。
The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit.
这将允许您像这样检查边缘：
if( matrix[3][5] )
{
// vertice 3 and 5 are connected
}
else
{
// vertice 3 and 5 are not connected
}
顶点
如果顶点的 id 值形成连续的整数范围（例如 0,1,2,3,...,999），那么您可以将颜色信息存储在 std::vector<int> 中，其中具有O(1) 访问时间：
std::vector<int> colors(1000);
这将耗尽内存等于：
1000 * sizeof(int) = 4000 B ~ 4 kB (3.9 kB)
另一方面，如果 id 值不形成连续的整数范围，则使用 std::unordered_map<int, int> 可能是更好的主意，这平均会给您 O(1) 查找时间。
std::unordered_map<int, int> map;
例如存储和查找顶点 4 的颜色：
map[4] = 5; // assign color 5 to vertice 4
std::cout << map[4]; // prints 5
std::unordered_map<int, int> 使用的内存量将为：
1000 * 2 * sizeof(int) = 8000 B ~ 8 kB (7.81 kB)
一起，边：
Type
Memory
Access time
std::vector<std::vector<bool>>125 kB
O(1)
并且对于顶点：
Type
Memory
Access time
std::vector<int>3.9 kB
O(1)
std::unordered_map<int, int>7.8 kB
O(1) on avg.
我需要你的专业知识：
我即将在 C++ 中实现一个图形 class 并考虑正确的表示形式。这些图简单且无向。顶点数量目前最多可达 1000，但将来可能会更高。边数高达 200k 甚至更高。每个顶点都有一个颜色 (int) 和一个 id (int)。边传输的信息不超过连接到顶点的信息。
我存储了图表，只需要访问 x 和 y 是否连接 - 我经常需要这个。 初始化后，我从不删除或添加新的顶点或边（N = 顶点数和 M = 从一开始就给定的边数）！
我已经可以使用的一个表示：
一个邻接列表展开成一个长列表。与此表示一起出现的是一个数组，其中包含每个顶点的起始索引。存储 O(2M) 并检查 x 和 y 之间的边缘是否平均为 O(n/m)
我想到的表示法：
我们的想法是，不是将邻接列表展开到一个数组中，而是使用邻接矩阵来完成。所以存储 O(N^2)？是的，但我想在一个字节以外的一位中存储一个边缘。（实际上是对称的 2 位）
示例：假设 N=8，然后创建一个长度为 8（64 位）的向量
您如何看待第二种解决方案 - 它是否已经为人所知并正在使用？ 考虑 O(1) 的访问我错了吗？ 是否付出了很多努力却没有真正的性能提升？
我被告知在一个大列表中加载两种表示的原因是缓存改进。
我很高兴收到有关此想法的一些反馈。我可能离题太远了 - 在那种情况下请善待 :D
如果你选择一个位矩阵，那么内存使用量是 O(V^2)，所以大约 1Mb 位或 128KB，其中略低于一半确实是重复的。
如果你制作一个边数组 O(E) 和另一个索引数组到从顶点到它的第一个边的边，你使用 200K*sizeof(int) 或 800KB，这是更多，一半它也是重复的（A-B 和 B-A 相同），这里实际上可以保存。同样，如果您知道（或者可以从中模板化）顶点数可以存储在 uint16_t 一半中可以再次保存。
要节省一半，您只需检查哪个顶点的编号较小并检查其边。
要找出何时停止查找，您可以使用下一个顶点上的索引。
因此对于您的数字，使用位矩阵很好甚至很好。
第一个问题出现在 (V^2)/8 > (E*4) 时，尽管 Edge 算法中的二进制搜索仍然比检查位慢得多。如果我们设置 E = V * 200（1000 个顶点 vs 200K 边）
，就会发生这种情况V*V/8 > V*200*4
V/8 > 200*4
V > 200*4*8 = 6400
这将是 5120000 ~ 5MB 很容易放入如今的 L3 缓存中。如果连通性（此处为每个顶点的平均连接数）高于 200 则更好。
检查边缘也会花费 lg2(connectivity)*K(mispredicts)，这会变得相当陡峭。检查位矩阵将是 O(1).
除其他外，您需要测量位矩阵何时显着破坏 L3 而边缘列表仍适合 L3 以及何时溢出到虚拟内存中。
换句话说，具有高连通性的位矩阵应该击败具有低得多的连通性或更多数量的顶点的边列表，边列表可能更快。
具有 200,000 条边的 1000x1000 矩阵将非常稀疏。由于图是无向的，所以矩阵中的边会被写两次：
VerticeA -> VerticeB and VerticeB -> VerticeA
你最终会填满矩阵的 40%，其余的将是空的。
边
这里我能想到的最好方法是使用 2D 布尔值向量:
std::vector<std::vector<bool>> matrix(1000, std::vector<bool>(1000, false));
查找将花费 O(1) 时间，std::vector<bool> 通过为每个布尔值使用一个位来节省 space。您最终将使用 1Mbit 或 ~128kB (125 kB) 的内存。
The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit.
这将允许您像这样检查边缘：
if( matrix[3][5] )
{
// vertice 3 and 5 are connected
}
else
{
// vertice 3 and 5 are not connected
}
顶点
如果顶点的 id 值形成连续的整数范围（例如 0,1,2,3,...,999），那么您可以将颜色信息存储在 std::vector<int> 中，其中具有O(1) 访问时间：
std::vector<int> colors(1000);
这将耗尽内存等于：
1000 * sizeof(int) = 4000 B ~ 4 kB (3.9 kB)
另一方面，如果 id 值不形成连续的整数范围，则使用 std::unordered_map<int, int> 可能是更好的主意，这平均会给您 O(1) 查找时间。
std::unordered_map<int, int> map;
例如存储和查找顶点 4 的颜色：
map[4] = 5; // assign color 5 to vertice 4
std::cout << map[4]; // prints 5
std::unordered_map<int, int> 使用的内存量将为：
1000 * 2 * sizeof(int) = 8000 B ~ 8 kB (7.81 kB)
一起，边：
| Type | Memory | Access time |
|---|---|---|
std::vector<std::vector<bool>> |
125 kB | O(1) |
并且对于顶点：
| Type | Memory | Access time |
|---|---|---|
std::vector<int> |
3.9 kB | O(1) |
std::unordered_map<int, int> |
7.8 kB | O(1) on avg. |