Блог

Я пытаюсь перенести код с python NetworkX на R igraph. В NetworkX есть функция с именем has_path , которая определяет, имеют ли две вершины путь. Я хочу эффективно найти все вершины графа, между которыми нет ребра, но есть путь.

Я думаю, что вы можете использовать приведенный ниже код, чтобы проверить, есть ли путь от вершины V1 до V2 (график может быть направленным или неориентированным)

 c(!is.infinite(distances(g, V1, V2, mode = "out")))
 

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

Смотрите components функцию. Это дает вам вектор членства. Вам нужно проверить, имеет ли позиция, соответствующая двум вершинам, одинаковое значение (один и тот же индекс компонента).

Если график направлен, то самым простым решением будет то, которое опубликовано @ThomasIsCoding. Это вполне подходит для одноразовой проверки. Ускорение повторных проверок вызывает больше проблем и требует своего собственного вопроса.