Более эффективный способ запуска случайного обхода ориентированного графа с помощью Networkx

Я пытаюсь смоделировать случайный обход через ориентированный сетевой граф. Псевдокод выглядит следующим образом

Create graph G with nodes holding the value true or false. 
// true -> visited, false -> not visited

pick random node N from G
save N.successors as templist
while true
    nooptions = false
    pick random node N from templist
    while N from templist has been visited
        remove N from templist
        pick random node N from templist
        if templist is empty
            nooptions = true
            break
    if nooptions = true 
        break
    save N.successors as templist

Есть ли более эффективный способ отметить путь как пройденный, кроме создания временного списка и удаления элементов, если они отмечены как посещенные?

ИЗМЕНИТЬ

Цель алгоритма — случайным образом выбрать узел в графе. Выберите случайного преемника/потомка этого узла. Если его никто не посещал, перейдите туда и отметьте его как посещенный. Повторяйте до тех пор, пока не останется преемников/потомков или пока не останется непосещенных преемников/потомков.


python graph-traversal networkx
person Linus Liang    schedule 03.03.2014    source источник
comment
Какова цель? Выбрать случайный узел, а затем выбрать случайный узел, к которому он может получить доступ, и извлечь этот путь? Мой ответ предполагает, что...   -  person Corley Brigman    schedule 03.03.2014
comment
Спасибо за ответ @CorleyBrigman. У меня уже есть код для запуска исходного кода, и сегодня вечером я опробую ваше последнее решение! Я оцениваю количество моих узлов примерно в сто тысяч. Цель состоит в том, чтобы начать со случайного узла и случайным образом выбрать узел для доступа, пока не останется узлов для доступа. К одному и тому же узлу нельзя обращаться более одного раза. Я надеюсь запускать симуляцию несколько раз (будет определено позже) и сохранять количество обращений к узлу, поэтому я думаю, что эффективность будет фактором.   -  person Linus Liang    schedule 03.03.2014
comment
Я просто проверяю свои предположения для начала со случайного узла и случайным образом выбираю узел... вы имеете в виду, начните с узла, выберите случайного преемника, затем выберите одного из преемников этого узла и т. д., пока вы не доберетесь до узла без наследников?   -  person Corley Brigman    schedule 03.03.2014
comment
Да, пока я не доберусь до узла без преемников или все преемники уже отмечены как посещенные.   -  person Linus Liang    schedule 03.03.2014

Ответы (1)


arrow_upward
4
arrow_downward

В зависимости от размера вашего графика вы можете использовать встроенную функцию all_pairs_shortest_path. Тогда ваша функция будет в основном:

G = nx.DiGraph()
<add some stuff to G>

# Get a random path from the graph
all_paths = nx.all_pairs_shortest_path(G)

# Choose a random source
source = random.choice(all_paths.keys())
# Choose a random target that source can access
target = random.choice(all_paths[source].keys())
# Random path is at
random_path = all_paths[source][target]

Кажется, нет способа просто сгенерировать случайные пути, начинающиеся с source, которые я видел, но код Python доступен, и я думаю, что добавление этой функции будет простым.

Две другие возможности, которые могут быть быстрее, но немного сложнее/вручную, заключаются в использовании bfs_successors, который выполняет поиск в ширину и должен включать любой целевой узел только один раз в список. Не на 100% уверен в формате, так что может быть не удобно.

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

# Get random source from G.node
source = random.choice(G.node)

min_tree = nx.bfs_tree(G, source)
# Accessible nodes are any node in this list, except I need to remove source.

all_accessible = min_tree.node.keys()
all_accessible.remove(source)
target = random.choice(all_accessible.node.keys())

random_path = nx.shortest_path(G, source, target)
person Corley Brigman    schedule 03.03.2014
comment
Почему вы удаляете источник? из bfs_tree - person Linus Liang; 04.03.2014
comment
Что касается вашего последнего решения, я не обязательно хочу использовать самый короткий путь от одного узла к другому. Позволит ли это действительно случайное блуждание? Кроме того, если моя цель является случайным выбором, скажем, что родитель является источником, а ребенок является целью. Смогу ли я пройти только одно ребро, даже если у цели может быть больше детей? Спасибо за вашу помощь! - person Linus Liang; 04.03.2014
comment
bfs_tree включает источник и все достижимые цели. А формат DiGraph таков, что G.node — это словарь. Итак, G.node.keys() — это список источника + всех целей. Чтобы выбрать случайную цель, вы можете использовать random.choice с этим списком, но вам не нужен источник, поэтому его можно удалить. - person Corley Brigman; 04.03.2014
comment
вы правы, с этим последним решением вы получите только кратчайший путь между этим случайным источником и целью. преимущество в том, что вы выбрали случайный источник и цель, между которыми вы знаете какой-то путь. но если вам нужен действительно случайный путь, тогда ваш оригинальный алгоритм работает, я бы просто использовал набор вместо списка - проверка на членство намного дешевле. вы также можете использовать мой метод с all_simple_paths, который даст все пути без циклов - создайте список и выберите случайную запись. это будет довольно равномерно случайным образом, но, вероятно, не очень эффективно... - person Corley Brigman; 04.03.2014
comment
Отлично, большое спасибо за вашу помощь! Я переключусь на использование набора для моего исходного алгоритма. В остальном ваш алгоритм отлично работает! Мне просто нужно было более равномерное случайное блуждание, которое дойдет до конца (больше никаких преемников или не посещенных преемников) - person Linus Liang; 04.03.2014