查找具有屬性的邊，如果您遵循這些屬性，則必須回到剛剛離開才能到達圖的其餘部分的節點

我正在處理與多個銷售員有關的旅行推銷員問題，而我希望找到並標記「口袋」的入口（我不知道一個更好的詞，這是問題），如果一個推銷員進入那個口袋裏，沒有其他人進入那裏，除非它的工作量太大第一個。查找具有屬性的邊，如果您遵循這些屬性，則必須回到剛剛離開才能到達圖的其餘部分的節點

這些都在真正的街道網絡中的地方。如果你以這樣的方式進入，那麼遲早你必須以相同的方式出現，因爲沒有其他出路。可能有一些內部結構，循環和分支，但沒有辦法回到城市本身，除非你進來。

我不在乎子口袋，我只想得到一個列表的節點，其中一個是城市的大部分，其他的都是這些口袋，如上所述連接到主要道路網絡。

我正在使用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

查找具有屬性的邊，如果您遵循這些屬性，則必須回到剛剛離開才能到達圖的其餘部分的節點

回答

相關問題