标签: graph-theory

我正在寻找一种方法来自动将城市中的社区定义为图形上的多边形。

我对邻里的定义有两个部分：

1. 街区：在多条街道之间封闭的区域，其中街道（边）和交叉点（节点）的数量最少为三个（三角形）。
2. 邻域：对于任何给定的街区，与该街区直接相邻的所有街区以及街区本身。

有关示例，请参见此插图：

例如，B4是由 7 个节点和连接它们的 6 个边定义的块。正如此处的大多数示例一样，其他块由 4 个节点和连接它们的 4 条边定义。此外，附近的B1包括B2（反之亦然），而B2还包括B3。

我正在使用osmnx从 OSM 获取街道数据。

1. 使用 osmnx 和 networkx，我如何遍历图来找到定义每个块的节点和边？
2. 对于每个块，我如何找到相邻的块？

我正在努力编写一段代码，该代码以图形和一对坐标（纬度、经度）作为输入，识别相关块并返回该块的多边形以及上述定义的邻域。

这是用于制作地图的代码：

import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt

G = ox.graph_from_address('Nørrebrogade 20, Copenhagen Municipality',
                          network_type='all', 
                          distance=500)

以及我试图找到具有不同节点数和度数的派系。

def plot_cliques(graph, number_of_nodes, degree):
    ug = ox.save_load.get_undirected(graph)
    cliques = nx.find_cliques(ug)
    cliques_nodes = [clq for clq in cliques if len(clq) …

有一组用户。一个人可以拥有多个用户，但ref1和ref2可能相似，因此可以将用户链接在一起。ref1且ref2不重叠，则 中ref1不存在 中的一个值ref2。

一个用户可以拥有多种资产。我想“合并”具有一个或多个相似参考的用户，然后计算他们总共拥有多少资产。用户表中可能缺少条目，在这种情况下，我只想将所有者传播到 ref2 并设置 asset_count 和 asset_ids。

下面是一个示例架构来说明：

示例资产

SELECT * FROM assets;

用户示例

SELECT * FROM users;

我有一个(理论上)网络,有N个节点,每个节点都有自己的固定位置.每个节点每个周期发送一条消息,需要直接或通过其他节点到达根节点.

从节点A向节点B发送消息的能量成本是它们之间的距离,平方.

挑战在于如何以树形格式链接这些节点以产生最节能的网络.

例如,有两种可能的方式来链接这些节点,左边的节点更节能.

我正在研究遗传算法来解决这个问题,但我想知道是否有人有任何其他想法,或者知道任何相关的开源代码.

编辑:网络的另一个方面,我忘了提到,每个节点都是电池供电的.因此,如果我们通过同一节点路由太多消息,那么该节点的电池将耗尽,导致网络出现故障.网络的能效是通过在任何节点电池耗尽之前可以从每个节点成功传输到根节点的消息来衡量的.

编辑#2:对于问题原始文本中的遗漏,我很抱歉.不管怎么说,你之前的一些答案并不是我想要的,但我不熟悉MST算法,所以感谢你告诉我它们.

为了让事情更清楚,让我补充一点:

所有节点每个周期发送一个自己的消息,包括内部节点.内部节点还负责中继它们收到的任何消息.这增加了电池的压力,如果他们发送了他们自己的附加信息.目标是在任何节点电池耗尽之前最大化循环次数.

我不想在大学里接受比我更多的数学,图论理论课程不是必修课,而是由CS部门"推荐".对于程序员来说,学习图论是否值得？

我想在开始实施之前检查一下我的理论.

常量:

• m =顶点质量(全部相同 - 可能将其设置为节点半径)
• k =恒定边力.
• l ="能量最小状态"处的边缘长度.

变量:

• d =两个顶点之间的距离.
• cl =边缘的当前长度.

理论: 每个顶点在每个其他顶点都有一个排斥力,即:m / (d^2).对于每个边缘,它表现出一个力,两个顶点将它们"拖动"在方向上以使边缘达到"能量最小状态"; 所以每个顶点:-k * ((l - cl) / 2).

伪代码:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each …

通过观看Christopher Bishops视频(http://videolectures.net/mlss04_bishop_gmvm/),我一直在学习很多关于使用图形进行机器学习的知识.我发现它非常有趣并且在同一类别(机器学习/图表)中观看了其他几个但是想知道是否有人有任何关于学习更多方法的建议？

我的问题是,虽然视频给出了很高的理解,但我还没有太多的实用技巧.我读过关于机器学习/模式的Bishops书以及Norvig的AI书,但两者似乎都没有涉及特定的使用图表.随着搜索引擎和社交网络的出现,我认为图形上的机器学习会很受欢迎.

如果可能,任何人都可以建议学习资源吗？(我是这个领域的新手,开发对我来说是一个爱好,所以如果有一个非常明显的资源需要学习,我很抱歉.我试过谷歌和大学网站).

提前致谢!

我是SO和postgres的新手所以请原谅我的无知.尝试使用类似于本文中的解决方案在postgres中获取图表的集群在PostgreSQL中查找集群给定节点

唯一的区别是我的id是一个UUID,我使用varchar(255)来存储这个id

当我尝试运行查询时,我收到以下错误(但不知道如何投射):

ERROR: recursive query "search_graph" column 1 has type character varying(255)[] in non-recursive term but type character varying[] overall

SQL状态:42804提示:将非递归项的输出强制转换为正确的类型.性格:81

我的代码(与上一篇文章基本相同):

WITH RECURSIVE search_graph(path, last_profile1, last_profile2) AS (
SELECT ARRAY[id], id, id
FROM node WHERE id = '408d6b12-d03e-42c2-a2a7-066b3c060a0b'
UNION ALL
SELECT sg.path || m.toid || m.fromid, m.fromid, m.toid
FROM search_graph sg
JOIN rel m
ON (m.fromid = sg.last_profile2 AND NOT sg.path @> ARRAY[m.toid]) 
   OR (m.toid = sg.last_profile1 AND NOT sg.path @> ARRAY[m.fromid])
)

 SELECT DISTINCT unnest(path) FROM …

我有一组节点和它们之间的有向边集.边缘没有重量.

如何找到必须添加的最小边数以使图形强连接(即应该有从每个节点到所有其他节点的路径)？这个问题有名字吗？

我想移动边缘标签的位置,使其不在它的顶部.这是一个小例子:

 g <- graph.empty(n=3) 
 g <- graph(c(1,2,3,2,1,3), directed=T)
 E(g)$weight <- c(3,2,5) 
 plot(g, edge.label = E(g)$weight)

在我的例子中,标签位于边缘,我希望它们垂直于边缘移动一点点.

我正在寻找一种方法,从节点和度数的所有强连接有向图(没有自循环)的空间均匀地采样.nk=(k_1,...,k_n), 1 <= k_i <= n-1

输入

• n,节点数量
• k = (k_1,...,k_n),其中k_i =进入节点的有向边数i(度数)

产量

• 具有n给定度数的节点(没有自循环)的强连接有向图,k_1,...,k_n其中每个可能的这样的图以相同的概率返回.

我特别感兴趣的n是大而k_i小的情况,因此简单地创建图形并检查强连通性是不可行的,因为概率基本上为零.

我浏览了各种各样的论文和方法,但找不到任何可以解决这个问题的方法.