问题标签 [adjacency-list]

我在 SqlAlchemy 0.6.6 中有一个非常简单的 N:M 关系。我有一个可以包含一堆媒体（图像或视频）的类“attractLoop”。我需要一个列表，其中可以将相同的媒体（比如说图像）附加两次。关系如下：

媒体是具有图像和视频将共享的大多数属性的基类。

然后是要使用这些“媒体”东西的班级：

以及链接两个表的中间类：

当我将相同的媒体对象（实例）两次附加到该 TestSqlAlchemyList 的一个实例时，它会正确附加两个，但是当我从数据库中检索 TestSqlAlchemyList 实例时，我只得到一个。它似乎表现得更像一个集合。

中间表正确包含所有信息，因此插入似乎工作正常。当我没有得到我插入的所有项目时，我尝试从数据库加载列表。

如您所见，id=1 的“测试”实例应该具有媒体 [1, 1, 2, 2, 1, 1]。好吧，它没有。当我从数据库加载它时，它只有媒体 [1, 2]

我试图在关系中设置任何可能闻到列表的参数... uselist，collection_class = list... 没有...

您将看到这些类继承自 BaseClass。这只是一个实际上没有映射到任何表的类，但包含一个数字字段（“id”），它将是每个类的主键和一堆对我系统中的其余类有用的其他方法（toJSON , toXML...)。以防万一，我附上一段摘录：

如果有人可以给我一个推动，我会很感激。谢谢你。很抱歉这个巨大的帖子......我真的不知道如何更好地解释。

我正在尝试对包含一个或多个形状的复合对象进行建模。为简单起见，我假设形状都是矩形。合成可能看起来像这样（原谅我糟糕的 ASCII 艺术）：

维基百科向我指出了图论，我在大学时几乎不记得了，而且邻接表似乎是对所有这些形状之间的关系进行建模的好方法。

我的问题是，我可以在邻接列表中指示左、右、上和下关系吗？说 1 与 2 相邻是不够的；我需要说 1 是 2 的左边（并且 3 在 4 之上，等等）。

在我的项目中，我正在尝试为图形构建邻接矩阵，并且出于空间和时间的考虑，我们应该使用稀疏矩阵，据我了解，使用哈希图最容易做到这一点。不幸的是，我们还必须实现一个邻接列表，我用所说的 hashmap 实现了它，并且由于我们的邻接矩阵在结构上必须不同，所以我不能对矩阵使用 hashmap。还有其他实现方式吗？

我有一个 MySQL 表pedigree，将我所有的互连亲子数据存储为 2 个邻接列表：

谱系表

• 任何org_id人都可能有孩子，也可能没有孩子。儿童人数不限。
• org_id表中的每个pedigree都需要至少有一个 dam_id 或一个sire_id
• 如果一个org_id没有父母，它不会在血统表中列出，除非是父亲或母亲
• 一个org_id可能有dam_id==sire_id

样本数据

我想使用 R 的igraph包（除非有更合适的东西）来显示我的谱系的有向 DAG，其中祖先节点出现在子节点之上。我不清楚 igraph 到底需要做什么。我想我需要从我的邻接列表中生成一个邻接矩阵，但我不知道如何有效地做到这一点。

想法？

这张图片展示了我想要实现的目标。左边是表格数据，右边是我要创建的表格。

该表使用 parentID 来引用同一个表中的另一个项目以创建层次结构。

我将如何以这种方式创建查询并组织它们？

如果我选择“海盗”并想要得到所有的父母怎么办？CFML 中有什么东西比循环查询更容易，直到我到达顶部？

问：使用 Datamapper ORM 时，如何为邻接列表设置模型。有人经历过吗？例如，表类别（id、name、has_parent_category_id）。感谢您的关注！

示例表，

这些文档在http://datamapper.wanwizard.eu/pages/advancedrelations.html中，我发现了以下“自我关系”。我不确定这是否是正确的方法！我正在测试它。

如果有人对邻接列表、codeigniters Datamapper ORM 有经验，并且介意留下一个关于如何做到这一点的实际示例，我将不胜感激！

谢谢你的时间！

I'm preparing for a coding interview, and was refreshing my mind on graphs. I was wondering the following : in all places I've seen, it is assumed that adjacency lists are more memory efficient than adjacency matrices for large sparse graphs, and should thus be preferred in that case. In addition, computing the number of outgoing edges from a node requires O(N) in a matrix while it's O(1) in a list, as well as which are the adjacent nodes in O(num adjacent nodes) for the list instead of O(N) for the matrix.
Such places include Cormen et al.'s book, or StackOverFlow : Size of a graph using adjacency list versus adjacency matrix? or Wikipedia.

However, using a sparse matrix representation like with Compressed Row Storage representation, the memory requirement is just in O(number of non-zeros) = O(number of edges), which is the same as using lists. The number of outgoing edges from a node is O(1) (it is directly stored in CRS), and the adjacent nodes can be listed in O(num adjacent nodes).
Why isn't it discussed ? Should I assume that CSR is a kind of adjacency list representation of the graph represented by the matrix ? Or is the argument that matrices are memory intensive flawed because they don't consider sparse matrix representations ?

Thanks!

我有以下问题：对邻接列表进行成像，它已经通过从这样的 sql 中出来的递归进行了处理

到目前为止，一切都很好——有了另一个“扁平化器”，我正在到达我需要的地方。现在，这是诀窍，这适用于“分页”结果，可能发生的事情（确实如此）是父母可以在一个子集中，而孩子可以在不同的子集中。通过上面的递归很明显，孩子不会在缺少父母的情况下到达树。

关于如何解决这个问题的任何想法？非常感谢您的帮助。

我有一个大约 1000 条记录的数组，每条记录都是一个具有以下属性的对象：

我想计算并充分利用具有相邻日期的结果。
任何人都可以给出任何想法吗？

编辑： 例如：

开发语言和数据库：PHP/MySQL

我有一张geo_places包含 800 万个地理位置的表格。

这些地方都是分层的，我用

• parent_id （邻接），
• lft/rgt （嵌套集）
• 和祖先（枚举）。

现在，我有一个名为“兴趣点”的表entities，它被分配到一个地理位置，并且我针对每个实体记录：

• lft位置的价值geo_places
• 和实际ID的地理位置。

现在我需要一种方法来提供一个有效计数的目录列表（但无论如何我都会缓存这个），在一个位置下面的所有地方。

例如，如果我选择欧洲，那么我应该看到所有具有欧洲 parent_id 的地方，然后还有它下面的实体数量。请记住，一个地方不会直接分配给欧洲，但可能会分配给意大利的一个小村庄（这是欧洲的一个孩子）。

你知道它是欧洲的孩子，要么是因为：

• lft意大利小村庄的价值在地段的价值和价值lft之间rgt
• 或者因为祖先映射到这个地方。

例如，欧洲的祖先路径为/15，ID 为 5。（1 表示“世界”）。然后意大利的小村庄就会有/1/5/234/28924/124128

其中 1 = 世界 5 = 欧洲 234 = 意大利 28924 = 贝加莫等...

无论如何，这就是我构建数据集的方式，并且我已经使用了分层结构的混合，以使我的查询更有效率（对于那些想知道为什么我支持嵌套集、邻接和枚举的人） ..这是因为我以这种方式获得了所有结构中最好的）。

这是我正在尝试做的一个例子。

我很灵活，可以根据需要更改管理位置的方式。但是，这也是一个多租户应用程序，所以如果可以避免的话，我想尽量避免保存对 geo_places 的计数。

所以简单地说：选择一个位置...然后显示所有具有分配给该位置的兴趣点的位置，或者该位置的子位置。

有什么建议吗？