Решение проблемы с графами с Python

Question

У меня есть одна ситуация, и я хотел бы подойти к этой проблеме с Python, но, к сожалению, мне не хватает знаний о графиках. Я нашел одну библиотеку, которая кажется очень подходящей для этой относительно простой задачи: networkx, но у меня возникают проблемы с выполнением точных вещей, которые я хочу, что должно быть довольно простым.

У меня есть список узлов, которые могут иметь разные типы и два «класса» соседей, вверх и вниз. Задача состоит в том, чтобы найти пути между двумя целевыми узлами, с некоторыми ограничениями в виде:

• только узлы определенного типа может быть пройдены, то есть, если исходные узлы имеют тип х, любой узел на пути должен быть от другой набор путей, у или г
• если узел имеет тип у, он может быть передан только через один раз
• если узел имеет тип г, он может быть пропущен через два раза
• в случае, когда узел тип z посещается, выход должен быть из другого класса соседа, то есть, если его посещать сверху, выход должен быть от

Итак, я попробовал несколько экспериментов, но я, как сказал, боролся. Во-первых, я не уверен, какой тип графика действительно представляет? Он не направлен, так как не имеет значения, переходите ли вы от узла 1 к узлу 2 или от узла 2 к узлу 1 (, за исключением в этом последнем сценарии, так что это немного усложняет ситуацию ...). Это означает, что я не могу просто создать граф, который просто многонаправлен, поскольку я должен иметь это ограничение. Во-вторых, мне нужно пройти через эти узлы, но указать, что для пути должны быть доступны только узлы определенного типа. Кроме того, в случае возникновения последнего сценария, я должен иметь в виду класс и направление ввода и выхода, что ставит его в несколько направленное состояние.

Ниже приведен пример макета код:

import networkx as nx 

G=nx.DiGraph() 
G.add_node(1, type=1) 
G.add_node(2, type=2) 
G.add_node(3, type=3) 
G.add_edge(1,2, side="up") 
G.add_edge(1,3, side="up") 
G.add_edge(2,1, side="down") 
G.add_edge(2,3, side="down") 
for path in nx.all_simple_paths(G,1,3): 
    print path 

Выход довольно хорошо, но мне нужны эти ограничения. Итак, есть ли у вас предложения о том, как я могу их реализовать, или дать мне несколько рекомендаций относительно понимания этого типа проблем или предложить другой подход или библиотеку для этой проблемы? Может быть, простой алгоритм на основе словаря соответствовал бы этой потребности?

Спасибо!

Answer 1

Возможно, вы сможете использовать функцию all_simple_paths() для своей проблемы, если вы построите свой график по-разному. Простыми путями являются те, у которых нет повторяющихся узлов. Поэтому для ваших ограничений здесь есть несколько предложений по построению графика, чтобы вы могли выполнить этот алгоритм без изменений.

• только узлы определенного типа может быть пройдены, то есть, если исходные узлы имеют тип х, любой узел на пути должен быть из другого набора путей, у или г

Учитывая начальный node n, удалите все остальные узлы с этим типом, прежде чем находите пути.

• если узел имеет тип у, он может быть передан только через один раз

Это определение простых путей, так что выполняется автоматически.

• если узел имеет тип г, он может быть пропущен через два раза

Для каждого узла п типа г добавить новый n2 узел с теми же самыми ребрами, как те, указывая на и от п.

• в случае посещается узел типа г, выход должен быть из другого класса соседа, то есть, если его посещенных вверх, выход должен быть от вниз

, если ребра направлены так, как вы предлагаете, тогда это может быть выполнено, если вы убедитесь, что ребра на z имеют одинаковое направление - например в для вверх и вниз для вниз ...

Answer 2

Лучший способ сделать это, я думаю, вычисляя все допустимые пути длины не более K между источником S и любым другим узлом, а затем, используя эту информацию, чтобы вычислить все действительные пути длины не более k + 1. Затем вы просто повторяете это, пока не получите фиксированную точку, где никакие пути не будут изменены.

На практике это означает, что вы должны настроить список путей на каждом узле. На каждом шаге вы берете каждый узел U по очереди и смотрите пути, которые на предыдущем шаге заканчивались у какого-то соседа V от U. Если какой-либо из этих путей может быть расширен, чтобы быть новым, отличным путем до U, добавьте его и добавьте его в U.

Если при выполнении шага вы не найдете новых путей, это ваше состояние завершения. Затем вы можете проверить список путей на целевом узле T.

псевдокод (в очень рыхлой C# формализма):

var paths = graph.nodes.ToDictionary(node => node, node => new List<List<node>>()) 
paths[S].Add(new List<node> {S}) // The trivial path that'll start us off. 


bool notAFixedPoint = true; 

while (notAFixedPoint) 
{ 
    notAFixedPoint = false // Assume we're not gonna find any new paths. 

    foreach (var node in graph) 
    { 
     var pathsToNode = paths[node] 

     foreach (var neighbour in node.Neighbours) 
     { 
      var pathsToNeighbour = paths[neighbour] 

      // ExtendPaths is where all the logic about how to recognise a valid path goes. 
      var newPathsToNode = ExtendPaths(pathsToNeighbour, node) 

      // The use of "Except" here is for expository purposes. It wouldn't actually work, 
      // because collections in most languages are compared by reference rather than by value. 
      if (newPathsToNode.Except(pathsToNode).IsNotEmpty()) 
      { 
       // We've found some new paths, so we can't terminate yet. 
       notAFixedPoint = true 

       pathsToNode.AddMany(newPathsToNode) 
      } 
     } 
    } 
} 

return paths[T] 

Answer 3

Это выглядит как проблема оптимизации для меня - смотреть вверх «коммивояжер» для классического примера, который несколько близко к тому, что вы хотите делать.

Мне удалась использовать «имитированный отжиг» для задач оптимизации, но вы также можете взглянуть на «генетические алгоритмы».