Finding minimal separators between pairs of non adjacent vertices

Usage
1

Hello,
I am trying to find all the minimal separators between pairs of non adjacent vertices.

For now I created a basic graph following the tutorial but I am stuck.

There is a function as explained in https://igraph.org/c/doc/igraph-Iterators.html#igraph_vs_nonadj to find the non adjacent vertices of a given vertex but it seems that this option is only available in C and I would like to use Python.
What I would like to have is a list of pairs of non adjacent vertices.

Same for the minimal separators function as in https://igraph.org/c/doc/igraph-Separators.html#igraph_is_minimal_separator.

This is the code I wrote until now.

from igraph import *
g = Graph([(0,1), (0,2), (2,3), (3,4), (4,2), (2,5), (5,0), (6,3), (5,6)])
layout = g.layout("kk")
g.vs["label"] = g.vs.indices
plot(g, layout = layout, bbox = (300, 300), margin = 40)

Could you please provide guidance on how to use these functions in Python?

Thank you very much.

Michelangelo

2

If your graph is relatively small, then you can achieve this with some basic Python coding. Assuming that your graph is undirected:

from itertools import combinations

nonadjacent_pairs = sorted(set(combinations(range(graph.vcount()), 2)) - set(graph.get_edgelist()))

The minimal separators function is a method on the Graph object.

1 Like