问题标签 [graph]

我正在用 Python 开发一个程序生成的游戏世界。世界的结构将类似于 MUD/MUSH 范式，房间和出口排列为有向图（房间是节点，出口是边）。（请注意，这不一定是无环图，尽管我愿意考虑无环解决方案。）

对于世界生成算法，不同类型的房间将通过每个房间的“标签”属性（一组字符串）来区分。一旦它们被实例化，就可以通过标签（单标签、标签交集、标签联合、最佳候选）来查询和选择房间。

我将使用模板对象和工厂方法的美化系统创建特定类型的房间——我认为这里的细节并不重要，因为当前的实现可能会改变以匹配所选的策略。（例如，可以将标签和标签查询添加到房间模板系统。）

例如，我将拥有以下类型的房间：

最后，问题是：实例化和安排这些房间以创建可能对应于给定规则的图形的好策略是什么？

一些规则可能包括：每 10,000 人拥有一个广场；main_street连接到plaza; side_street连接到main_street或side_street；hotel青睐main_street或plaza联系，并相应地接收更多标签；等等

如果建议的策略能够实现数据驱动的实施，则可以加分。

该算法在遍历图中的节点方面做得很好。

我可以使用它在图中找到目标节点。工作清单在处理工作清单时使项目出队（或弹出）。找到目标后，如何返回节点的完整路径？

更新 我试图弄清楚如何将路径反转到根目录。该方法在根节点上调用，之后子节点可能有两个父节点，所以并不像在每个节点上调用父属性并向上遍历那么简单。

该方法的目标是找到路径，而不是迭代所有节点，或者检查节点是否存在。

我想为图创建一个邻接矩阵。因为我读到使用表单的数组是不安全的，matrix[x][y]因为它们不检查范围，所以我决定使用 stl 的向量模板类。我需要在矩阵中存储的只是布尔值。所以我的问题是，如果使用std::vector<std::vector<bool>* >*会产生过多的开销，或者是否有更简单的矩阵方法以及如何正确初始化它。

编辑：非常感谢您的快速回答。我刚刚意识到，我当然不需要任何指针。矩阵的大小将在开始时初始化，直到程序结束才会改变。这是一个学校项目，所以如果我写“好”的代码会很好，尽管技术上的性能并不是太重要。使用 STL 很好。使用诸如 boost 之类的东西可能不受欢迎。

我想创建一个表示网站更新频率的图表（例如，过去 5 年我在博客上发帖的频率）。一种明显的方法是绘制过去 60 个月的“每月发布的条目数”，但这并不令人满意。我应该考虑使用滚动平均值之类的东西吗？显示此类数据的良好可视化技术是什么？

我想知道是否有人可以提供一些关于如何在对图执行深度优先搜索时检查钻石依赖关系的指示......我有以下图表A -> B, A -> F, B -> C, B-> E, C -> D, E -> D。

我正在尝试构建代表指定图形的容器层次结构，但是当我达到菱形依赖项时，我不确定该怎么做。例如，在我的图中，CandE都是 的子容器B，当我解决 时D，我需要引用Cand E。我可以检测到钻石依赖关系并将其组合C到E一个容器中吗？

我有一张桌子：

我想用它制作一个条形图。

不是说网上没有lib，而是prototype或者flash xml文件。

--

我正在研究的解决方案是一个 jquery 插件，它将为谷歌图表生成一个 html 链接......不漂亮但 KISS（非常简单）和丑陋。

--

这是我的灵感之一： http ://www.dumpsterdoggy.com/articles/?jquery-horizo​​ntal-bar-graph

我试图弄清楚如何使用 boost::graph 来存储一些信息。但是，我希望将信息绑定到每个顶点。盯着库的文档会发现（a）写得不好的文档，或者（b），我显然不像我想象的那样擅长 C++。选择两个。

我正在寻找一个简单的示例使用。

我一直在玩一些东西，并想出了试图找出凯文培根数字的想法。我有一个网站的数据，为此我们可以考虑一个社交网络。让我们假设它是 Facebook（为了简化讨论）。我有人，我有他们朋友的名单，所以我有他们之间的联系。如何计算一个人到另一个人的距离（基本上是凯文培根数）？

我最好的想法是具有深度限制的双向搜索（以限制计算复杂性并避免在图中根本无法连接的人的问题），但我意识到这是相当蛮力的。

制作小的子图（比如 Facebook 上的群组），计算它们之间的最短距离（也许是提前），然后尝试使用 THOSE 来查找链接会更好吗？虽然这需要预先计算，但它可以搜索更少的节点（节点可以是组而不是个人，使图更小）。不过，这仍然是双向搜索。

我还可以预先计算个人连接的人数，首先在节点中搜索“受欢迎”的人，因为他们最有可能连接到给定的目标个人。我意识到这将是可能的最短路径的速度权衡。我想我还想使用深度优先搜索，而不是我计划在其他情况下使用的广度优先搜索。

有人能想出一种更简单/更快的方法吗？我希望能够找到两个人之间的最短距离，所以这并不像总是有相同的终点那么容易（例如在凯文培根问题中）。

我意识到有一些问题，比如我可以得到 200 人的连锁店之类的，但这可以解决我对我愿意搜索的深度的限制。

我对 munin 的工作原理不是很熟悉，所以如果这很明显，我深表歉意。

我现在已经在我的几个项目中使用了 munin，我已经两次遇到这种情况，我将丢失从过去事件生成的所有 munin 图。这只是今天下午发生在我身上。现在，我只有今天下午以来所有系统事件的跟踪记录。

这些图表可以恢复吗？是否有数据存储在用于生成这些图表的某处？

如果它无法恢复，我想知道是什么可能导致这种情况发生。当然，每次发生这种情况时，我都在搞乱我的 munin 配置设置。对于这种情况，我正在添加新的服务器以由 munin 记录...我不知道这样做会如何导致 munin 丢失我其他服务器上的所有数据。

谢谢。

我想将社交网络图中的一些节点指标组合成一个值，以便对节点进行排序：

in_degree + betweenness_centrality = informal_power_index

问题是in_degree和betweenness_centrality是在不同的尺度上测量的，比如 0-15 vs 0-35000 并遵循幂律分布（至少绝对不是正态分布）

有没有一种很好的方法来重新调整变量，以便在确定 时一个不会支配另一个informal_power_index？

三种明显的方法是：

• 标准化变量（减去mean和除以stddev）。这似乎会过度压缩分布，隐藏长尾值与峰值附近值之间的巨大差异。
• min(variable)通过减去和除以将变量重新缩放到范围 [0,1] max(variable)。这似乎更接近于解决问题，因为它不会改变分布的形状，但也许它不会真正解决问题？特别是手段会有所不同。
• 通过将每个值除以 来均衡均值mean(variable)。这不会解决尺度上的差异，但也许平均值对于比较更重要？

还有其他想法吗？