标签: adjacency-list

我正在寻找 Django 树库，并尽力避免嵌套集（维护它们是一场噩梦）。

邻接列表模型的缺点始终是无法在不诉诸多个查询的情况下获取后代。Postgres 中的WITH 子句似乎是解决这个问题的可靠方法。

有没有人看过有关WITH与Nested Set的性能报告？我认为嵌套集仍然会更快，但只要它们处于相同的复杂性类别，我就可以承受 2 倍的性能差异。

姜戈-树须让我感兴趣。有谁知道他们在 Postgres 下运行时是否实现了 WITH 子句？

这里有人根据WITH 子句放弃了嵌套集吗？

我必须准备在 Adjency List中去除顶点 ( O(|V| + |E|)) 和边 ( O(|E|))的时间复杂度的解释。

当从图中删除带有 V 个顶点和 E 个边的顶点时，我们需要遍历所有边 ( O(|E|))，当然，要检查是否需要与顶点一起删除哪些顶点，但为什么我们需要检查所有顶点？

我不明白为什么为了去除边缘，我们需要遍历所有边缘。我想我可能从一开始就不太理解，所以你能帮助上面那两个吗？

我想使用boost的dijkstra算法(因为我在程序的其他部分使用了boost).我遇到的问题是添加自定义对象(我相信它们被称为property)adjacency_list.

基本上我有一个自定义边缘类,它维护有关边缘和通过它连接的顶点的各种信息.我想用我所需的边缘属性存储我的自定义数据对象adjaceny_list

我已经成功实现了提升提供的玩具示例.我试图使用自定义属性无济于事(提升示例,提升属性).我只是将我的VEdge数据结构封装在一个结构或其他东西中,我只需要能够检索它.但我无法弄清楚如何将自定义数据结构包含在boost adjaceny_list结构中.

在我的情况下,我有以下程序:

Main.cpp的:

#include <iostream>
#include <fstream>
#include "dijkstra.h"
#include <vector>

int
main(int, char *[])
{
  // Generate the vector of edges from elsewhere in the program
  std::vector<VEdge*> edges; //someclass.get_edges();

  td* test = new td(edges);
  test->run_d();

  test->print_path();

  return EXIT_SUCCESS;
}

Dijkstra.cpp:

#include <iostream>
#include <fstream>
#include "dijkstra.h"

using namespace boost;

td::td() {
    kNumArcs = sizeof(kEdgeArray) / sizeof(Edge);
    kNumNodes = 5;
}

td::td(std::vector<VEdge*> edges) {
    // …

我有一个 Flask RESTful API 应用程序，它具有以下 SQLAlchemy 类，其中包含一个邻接列表的自引用密钥代表：

class Medications(db.Model):
    __tablename__ = 'medications'
    id = Column(Integer, primary_key=True)
    type = Column(String(64))
    name = Column(String(64))
    parent_id = Column(Integer, ForeignKey('medications.id'))
    children = relationship("Medications")

我想要从 Medications 类返回的嵌套 JSON，如下所示

"objects": [
    {
      "children": [
        {
          "id": 4, 
          "name": "Child1", 
          "parent_id": 3, 
          "type": "Leaf"
        }, 
        {
          "id": 5, 
          "name": "Child2", 
          "parent_id": 3, 
          "type": "Leaf"
        }
      ], 
      "id": 3, 
      "name": "CardioTest", 
      "parent_id": null, 
      "type": "Parent"
    }
  ], 

根据how-to-create-a-json-object-from-tree-data-structure-in-database我创建了序列化程序类

class JsonSerializer(object):
    """A mixin that can be used …

我正在通过这个链接进行邻接列表表示.

http://www.geeksforgeeks.org/graph-and-its-representations/

我对代码的某些部分有一个简单的疑问,如下所示:

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

因为,这里执行每个Vwhile循环,比如说dd是每个顶点的度数.

所以,我认为时间的复杂性就像

d0 + d1 + d2 + d3 ....... +dV where di is the degree of each …

我正在寻找用于表示图形的不同数据结构，我遇到了 Nvidia CUDA Toolkit，并在 source_indices、destination_offsets 的帮助下找到了表示图形的新方法。

被这种创新的图形表示所吸引，我寻找了其他表示图形的方法。但没有发现任何新东西。

我想知道除了邻接矩阵或列表之外，是否还有其他方式来表示图...

我试图更好地理解在 AWS DynamoDB 中使用邻接列表模式进行多对多 (m:n) 关系设计。

查看此处的 AWS 文档： https: //docs.aws.amazon.com/amazondynamodb/latest/developerguide/bp-adjacency-graphs.html我们有一个示例，其中发票和账单实体具有 m:n 关系。

I understand that I can get details of all bills associated with a particular invoice by reading a single partition. For example I can query for Invoice-92551 and know some attributes of the 2 bills that are associated with it based on the additional items in the partition.

My question is what do I have to do to get the full bill attributes for these 2 …

我听说大多数图算法（但不是全部）都使用邻接表。我只是想知道什么算法更喜欢邻接矩阵，为什么？

到目前为止，我\xe2\x80\x99ve发现Floyd Warshall使用邻接矩阵。

在 C++ 中实现图的邻接表表示的有效方法是什么？

1. 向量*边；
2. 列出*边；
3. 地图<int, int> *边缘;
4. 地图<int, 地图<int, int>> 边；

在我看来，应该是选项3或4，但我找不到使用它的任何缺点......有什么缺点吗？

有人可以帮助我，这将是实现邻接表和竞争性编程的最有效方法吗？

假设我有两个选项来生成网络的邻接矩阵:nx.adjacency_matrix()以及我自己的代码.我想测试我的代码的正确性,并提出了一些奇怪的不等式.

示例:3x3网格网络.

import networkx as nx
N=3
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds))
plt.figure()
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200)

这是可视化:

邻接矩阵nx.adjacency_matrix():

B=nx.adjacency_matrix(G)
B1=B.todense()

[[0 0 0 0 0 1 0 0 1]
 [0 0 0 1 0 1 0 0 0]
 [0 0 0 …