Given a graph text file representing a graph, my program give you all the minimal separator of this graph.

Windows Binary

What is it?

A graph is denoted G=(V,E)
For C a subset of V, G(C) denotes the subgraph induced by C.
For C a subset of V, C(C) denotes the set of connected components of G(V\X).
S is called an ab-separator if a and b are in different connected components of C(S).
S is called a minimal ab-separator if S is an ab-separator and no proper subset of S is in an ab-separator.
S is called a minimal separator if there is some paire {a,b} such that S is a minimal ab-separator

Graph format

In the text file, the graph can have two format.
The file must start with the kind of format it is : matrix or edge
Then you have to indicate the number of Nodes.
Then if you use the first format you indicate the adjacency matrix.
If you use the second format you indicate all the edge like that : NodeNumber1 NodeNumber2

Example

The two following file define the same graph:

graph1.txt

matrix
5
1 0 0 1 0
0 1 1 1 0
0 1 1 0 0
1 1 0 1 1
0 0 0 1 1

graph2.txt

edge
5
0 3
1 2
1 3
3 4

I didn’t test my program on big graph yet.