查找具有属性的边，如果您遵循这些属性，则必须回到刚刚离开才能到达图的其余部分的节点

我正在处理与多个销售员有关的旅行推销员问题，而我希望找到并标记“口袋”的入口（我不知道一个更好的词，这是问题），如果一个推销员进入那个口袋里，没有其他人进入那里，除非它的工作量太大第一个。查找具有属性的边，如果您遵循这些属性，则必须回到刚刚离开才能到达图的其余部分的节点

这些都在真正的街道网络中的地方。如果你以这样的方式进入，那么迟早你必须以相同的方式出现，因为没有其他出路。可能有一些内部结构，循环和分支，但没有办法回到城市本身，除非你进来。

我不在乎子口袋，我只想得到一个列表的节点，其中一个是城市的大部分，其他的都是这些口袋，如上所述连接到主要道路网络。

我正在使用osmnx提供的MultiDiGraph。

来源

2017-09-01 Lauritz V. Thaulow

重新找回所有边缘的问题是否公平？如果一个被删除，它会分割图表？ –

@KevinBeck这就是所谓的桥梁，对吧？不，这不是我所追求的，因为那将包括所有树型结构的所有小型子插座和树干和分支，这些我并不感兴趣，我只想将“最终桥”连接到主要街道网络。 –

什么定义了“主要街道网络”，与您的可分离子图不同？ – Prune

您的出发点是术语cut，这是一组去除该分区图的边。你正在寻找任何规模为1的“最小剪辑”。

对于像街道地图连接的东西，我想你会想要Karger's算法。这通过将任何高度连接的节点集合折叠成单个节点来间接搜索最小切割点，直到最后还有相对较少的单边连接剩余。从这里开始，更容易找到切割。

来源

2017-09-01 21:28:28 Prune

中所描述的那样将图切成双连通组件。非常感谢。我似乎无法在networkx中找到Karger的算法，即使在2.0b2中也是如此，但是我发现了一个实现[here]（https://github.com/jinhw1989/MinCutAlgo/blob/master/algo/MinCut.py）。 –

并非每种算法都已经在每种语言中实现。我很高兴你能在你阅读的语言中找到一个。 – Prune

@ LauritzV.Thaulow - 当然，如果您使用networkx将其编码为高质量，我相信他们会有兴趣添加它。 – Joel

查找具有属性的边，如果您遵循这些属性，则必须回到刚刚离开才能到达图的其余部分的节点

回答

相关问题