专门存储有向图的数据库？
我想知道是否有人对此有任何建议。
这不是研究图理论；我正在使用图表代表
问题域。这些图可能很大，并且可以
很容易拥有数百万个节点，并且大多数节点具有很大的节点
与它们相关的数据量。显然我不想整个
这样的记忆中的此类图，因此库库仅处理 -
内存图已经熄灭。
我知道我可以用关系DB实施此功能，我会没事的
带有一个在一个顶部建造的图书馆。但我希望
特殊行为对图表有用。
例如，假设我有一组名为A的节点A
有助于知道这些节点是否通过路径连接
当然，我可以通过阅读来做到这一点。我当然可以做到这一点
数据库和遵循路径，但我显然不想做
那。我希望以某种方式缓存外部连接
A的不同节点之间的关系
某些地方在其他地方发生了变化。通知的缓存如何？
它可以使用图定理有效地更新
再生？
这很棘手；这就是为什么我希望别人做到这一点。
我猜不。
卡尔银行
# 回答1
2008年10月27日星期一下午5:32，卡尔银行
要找到一个我很久以前发生的项目，但不记得
它的名称模糊地喜欢您想要的，因为它是一个"图形"
数据库"：neo4j -http：//neo4j.org/(是的，它在Java;叹气)
不确定这正是您要寻找的，但是无论如何...。
干杯，
克里斯
- -
遵循鬣蜥的路径... http：//rebertia.com
2008年10月27日星期一下午5:32，卡尔银行
要找到一个我很久以前发生的项目，但不记得
它的名称模糊地喜欢您想要的，因为它是一个"图形"
数据库"：neo4j -http：//neo4j.org/(是的，它在Java;叹气)
不确定这正是您要寻找的，但是无论如何...。
干杯，
克里斯
- -
遵循鬣蜥的路径... http：//rebertia.com
# 回答2
卡尔·班克斯(Carl Banks)在2008-10-28 01:32写道：
亚伦·沃特斯(Aaron Watters)是这一点的专家，并实施了kjbuckets
为了在内存中执行此操作：http：//gadfly.sourceforge.net/kjbuckets.html
Gadfly使用库来实现关系查询(并起作用
在磁盘上)：http：//gadfly.sourceforge.net/
该包现在由理查德·琼斯(Richard Jones)维护。
您也许可以为您的某些部分重复使用Gadfly的部分
目的。
还要查看pygr：http：//bioinfo.mbi.ucla.edu/pygr
这是一个python库，可以在
关系数据库。
- -
马克·安德烈·伦堡
egenix.com
直接来自来源的专业Python服务(2008年10月28日，#1)
______________________________________________________________________________________________________
::::尝试MXODBC.ZOPE.DA Windows，Linux，Solaris，MacOSX免费！ ::::
egenix.com软件，技能和服务GmbH Pastor-Loeh-Str.48
D-40764德国Langenfeld。首席执行官大队。马克·安德烈·伦堡
在Amtsgericht Duesseldorf注册：HRB 46611
卡尔·班克斯(Carl Banks)在2008-10-28 01:32写道：
亚伦·沃特斯(Aaron Watters)是这一点的专家，并实施了kjbuckets
为了在内存中执行此操作：http：//gadfly.sourceforge.net/kjbuckets.html
Gadfly使用库来实现关系查询(并起作用
在磁盘上)：http：//gadfly.sourceforge.net/
该包现在由理查德·琼斯(Richard Jones)维护。
您也许可以为您的某些部分重复使用Gadfly的部分
目的。
还要查看pygr：http：//bioinfo.mbi.ucla.edu/pygr
这是一个python库，可以在
关系数据库。
- -
马克·安德烈·伦堡
egenix.com
直接来自来源的专业Python服务(2008年10月28日，#1)
______________________________________________________________________________________________________
::::尝试MXODBC.ZOPE.DA Windows，Linux，Solaris，MacOSX免费！ ::::
egenix.com软件，技能和服务GmbH Pastor-Loeh-Str.48
D-40764德国Langenfeld。首席执行官大队。马克·安德烈·伦堡
在Amtsgericht Duesseldorf注册：HRB 46611
# 回答3
10月27日，8：32*PM，Carl Banks
平行扩展[2]可能是您最好的选择；它也随附
Python结合 但是它们不再维护。用于商业
解决方案，star-p [3]似乎是一个有趣的平台，与
Matlab和Python。 Freebase [4]显然是在特殊图上构建的
数据库，但不幸的是，只有存储的数据可用，而不是
DB源代码。
乔治
[1] http://www.boost.org/doc/libs/1_36_0...doc/index.html
[2] http://www.osl.iu.edu/research/pbgl/
[3] http：//www.interactivesupercomputing...sematrices.php
[4] http://www.freebase.com/help/faq#q7
10月27日，8：32*PM，Carl Banks
平行扩展[2]可能是您最好的选择；它也随附
Python结合 但是它们不再维护。用于商业
解决方案，star-p [3]似乎是一个有趣的平台，与
Matlab和Python。 Freebase [4]显然是在特殊图上构建的
数据库，但不幸的是，只有存储的数据可用，而不是
DB源代码。
乔治
[1] http://www.boost.org/doc/libs/1_36_0...doc/index.html
[2] http://www.osl.iu.edu/research/pbgl/
[3] http：//www.interactivesupercomputing...sematrices.php
[4] http://www.freebase.com/help/faq#q7
# 回答4
对不起，卡尔·班克斯(Carl Banks)的回答延迟，Google存在问题
小组。
对于现代PC来说，这听起来不是问题。
我认为您可以将整个图形拓扑保持在RAM和节点中
磁盘上的数据(例如，在文件或数据库中)。拓扑是
由ARC代表(您什么也没说有关电弧数据，所以
我认为它不存在)和节点(在RAM中您只需要32位
未符号整数表示存储在上的节点的索引
磁盘。如果内存变得紧绷，您只能使用3个字节(2 ^ 24 = 16
节点的数百万个不同节点)，但通常是内存
与必要的记忆相比，节点所需的所需
存储弧)。
您没有说有多少弧，节点的总或平均水平，
如果这种弧线是指向或无方向性的。
无论如何，使用我的图形类(每弧两次存储)，这需要
大约1分钟和1.3 GB的RAM(100万节点，节点10个弧)：
从图表导入图
从随机导入randrange
g = graph()
n = 1000000
g.addnodes(xrange(n))
对于我在Xrange(n * 10)中：
G.Addarc(randrange(n)，randrange(n))
您已经说过"很容易拥有数百万个节点"，每个弧线可能
具有数十个或更多的弧线。
("任意大"是一个无法解决的问题，因为总会有
程序中的限制，没有能够在
"任意大"数据集)，因此Python数据结构也变得
公羊队的成本很高。使用较低的语言，例如D/C/C ++
可以管理更大的图形。您可以使用Boost图，但是自制
图形结构也足以满足您的目的。
对于这个问题，您已经解释了我认为一个非常简单的图
表示形式可能就足够：整数对数组(statter_index，
len)(statter_index也可以是指针)，其中len是
节点n的出站弧，以及一系列索引/指针
列出出站弧。如果记忆变得紧张，您可以分开第二个
数组成两半，并使用一组字节来进行长度(如果您有
超过256个出站弧线，您可能需要简短)。请注意，如果您
使用索引，然后使用Python Array.Array(或Numpy)就足够了。
在这种情况下，如果nnodes = 10_000_000和narcs/node = 40(总计
节点= 40 * 10_000_000)：
nnodes * narcs * 4 + nnodes *(4 + 4)= 1_680_000_000字节，也就是说
通常在现代PC上可用。
在64位机器上，索引采用相同的内存，但指针
两次。
在"存储器保存"模式中：
nnodes * narcs * 3 + nnodes *(3 + 1)= 1_240_000_00 0字节。
一个更方便的妥协是：
nnodes * narcs * 3 + nnodes *(4 + 4)= 1_280_000_000字节。
关于数据结构，如果您像我所解释的那样使用数组，
如果您的更新不经常，那么您可以分配额外的小额
存储更多弧的数组出现一个节点(但是要这样做
可能喜欢使用指针而不是索引)。当你有一个
大量更新了您可以将全部保存到磁盘，然后再生整个
数据结构。
再见，
熊
对不起，卡尔·班克斯(Carl Banks)的回答延迟，Google存在问题
小组。
对于现代PC来说，这听起来不是问题。
我认为您可以将整个图形拓扑保持在RAM和节点中
磁盘上的数据(例如，在文件或数据库中)。拓扑是
由ARC代表(您什么也没说有关电弧数据，所以
我认为它不存在)和节点(在RAM中您只需要32位
未符号整数表示存储在上的节点的索引
磁盘。如果内存变得紧绷，您只能使用3个字节(2 ^ 24 = 16
节点的数百万个不同节点)，但通常是内存
与必要的记忆相比，节点所需的所需
存储弧)。
您没有说有多少弧，节点的总或平均水平，
如果这种弧线是指向或无方向性的。
无论如何，使用我的图形类(每弧两次存储)，这需要
大约1分钟和1.3 GB的RAM(100万节点，节点10个弧)：
从图表导入图
从随机导入randrange
g = graph()
n = 1000000
g.addnodes(xrange(n))
对于我在Xrange(n * 10)中：
G.Addarc(randrange(n)，randrange(n))
您已经说过"很容易拥有数百万个节点"，每个弧线可能
具有数十个或更多的弧线。
("任意大"是一个无法解决的问题，因为总会有
程序中的限制，没有能够在
"任意大"数据集)，因此Python数据结构也变得
公羊队的成本很高。使用较低的语言，例如D/C/C ++
可以管理更大的图形。您可以使用Boost图，但是自制
图形结构也足以满足您的目的。
对于这个问题，您已经解释了我认为一个非常简单的图
表示形式可能就足够：整数对数组(statter_index，
len)(statter_index也可以是指针)，其中len是
节点n的出站弧，以及一系列索引/指针
列出出站弧。如果记忆变得紧张，您可以分开第二个
数组成两半，并使用一组字节来进行长度(如果您有
超过256个出站弧线，您可能需要简短)。请注意，如果您
使用索引，然后使用Python Array.Array(或Numpy)就足够了。
在这种情况下，如果nnodes = 10_000_000和narcs/node = 40(总计
节点= 40 * 10_000_000)：
nnodes * narcs * 4 + nnodes *(4 + 4)= 1_680_000_000字节，也就是说
通常在现代PC上可用。
在64位机器上，索引采用相同的内存，但指针
两次。
在"存储器保存"模式中：
nnodes * narcs * 3 + nnodes *(3 + 1)= 1_240_000_00 0字节。
一个更方便的妥协是：
nnodes * narcs * 3 + nnodes *(4 + 4)= 1_280_000_000字节。
关于数据结构，如果您像我所解释的那样使用数组，
如果您的更新不经常，那么您可以分配额外的小额
存储更多弧的数组出现一个节点(但是要这样做
可能喜欢使用指针而不是索引)。当你有一个
大量更新了您可以将全部保存到磁盘，然后再生整个
数据结构。
再见，
熊
# 回答5
真的不知道这是否有用，但我会尝试使用Pytables：http：//www.pytables.org/moin
它处理的各种层次数据集都很好，没有
大小。
它将仅加载重要的数据，您将能够
查询您的数据。
它建在HDF5库的顶部，但公开了一个非常友好的
Pythonic界面。
当然，您仍然必须自己实现所有图形逻辑
但这可能是一个很好的起点。
希望能帮助到你
Marco
真的不知道这是否有用，但我会尝试使用Pytables：http：//www.pytables.org/moin
它处理的各种层次数据集都很好，没有
大小。
它将仅加载重要的数据，您将能够
查询您的数据。
它建在HDF5库的顶部，但公开了一个非常友好的
Pythonic界面。
当然，您仍然必须自己实现所有图形逻辑
但这可能是一个很好的起点。
希望能帮助到你
Marco
# 回答6
10月27日，7：32*PM，Carl Banks
"搁置"，" sqllite"，" mmap"和" ctypes.structure"。还是你需要
"外部连接"属性的特殊结构？
存储是通常的时间空间折衷。 (实际上，我认为
该术语是指略有不同的东西。这会更多
大约是正确称为阅读时间/写入时间的权衡。)
假设您选择了RDB，则有一个顶点和一个表
边缘。您是否要"设置A"为桌子并在运行之间持续存在
程序？如果没有
满足该物业。我认为您所追求的套件是：所有X，Y
x是a中的顶点，y是a中的顶点，存在p
p是一条路径，p在x，p末端开始，p处，p在p中为v
暗示v为x，v是y或v不在A中。我不知道您是否是否
可以缓存有关一个为您提供任何快捷方式的任何信息
计算s或运行时间或运行空间
最快/最小的算法是。在最坏的情况下，每个是o(| v | * | e |)
更改为V或E.未经验证。
您可能可以将最短路径存储在2-的映射中
到路径的元组。或更好的是，将每个节点映射到所有节点
节点可以从中获得一次。然后，您可以保存
在A或G中添加节点/顶点的时间，或从A中删除一个节点
或G，或两者兼而有之。也许将G中的每个节点映射到该相对集。
您没有说该图是否是指向和/或循环。
一个好的起点是，如果您向G中添加一个节点，可以S
减少？不，因为原始路径P仍然存在。如果你
从A中删除一个，仍然在G中，S可以保持相同的大小，可能
减少。如果您从g中删除一个节点，则不在A中，等等。
10月27日，7：32*PM，Carl Banks
"搁置"，" sqllite"，" mmap"和" ctypes.structure"。还是你需要
"外部连接"属性的特殊结构？
存储是通常的时间空间折衷。 (实际上，我认为
该术语是指略有不同的东西。这会更多
大约是正确称为阅读时间/写入时间的权衡。)
假设您选择了RDB，则有一个顶点和一个表
边缘。您是否要"设置A"为桌子并在运行之间持续存在
程序？如果没有
满足该物业。我认为您所追求的套件是：所有X，Y
x是a中的顶点，y是a中的顶点，存在p
p是一条路径，p在x，p末端开始，p处，p在p中为v
暗示v为x，v是y或v不在A中。我不知道您是否是否
可以缓存有关一个为您提供任何快捷方式的任何信息
计算s或运行时间或运行空间
最快/最小的算法是。在最坏的情况下，每个是o(| v | * | e |)
更改为V或E.未经验证。
您可能可以将最短路径存储在2-的映射中
到路径的元组。或更好的是，将每个节点映射到所有节点
节点可以从中获得一次。然后，您可以保存
在A或G中添加节点/顶点的时间，或从A中删除一个节点
或G，或两者兼而有之。也许将G中的每个节点映射到该相对集。
您没有说该图是否是指向和/或循环。
一个好的起点是，如果您向G中添加一个节点，可以S
减少？不，因为原始路径P仍然存在。如果你
从A中删除一个，仍然在G中，S可以保持相同的大小，可能
减少。如果您从g中删除一个节点，则不在A中，等等。