Minimal vertex separator between two nodes in an undirected graph

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Minimal vertex separator between two nodes in an undirected graph

Federico Schluter
Hi all, is there some implemented function in jgrapht to get a minimal vertex separator set between two non adjacent nodes in an undirected graph? I was searching at the javadoc but I can't find if there exist something like that.


I would like to use jgrapht to implement the getMinimalVertexSeparator function in the following example code: 

public static void main(String[] args) {
UndirectedGraph g = new UndirectedGraph(6);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 0);
List<Integer> x = getMinimalVertexSeparator(0, 2, g);

}

​Thanks in advance,​

--
​Federico

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimal vertex separator between two nodes in an undirected graph

Rushang Karia
Have you tried looking at min-cut. There is an implementation of min cut in jgrapht.

NOTE: Min cut is not the same as vertex seperator. There are a few differences!


From: [hidden email]
Date: Tue, 15 Sep 2015 14:39:37 -0300
To: [hidden email]
Subject: [jgrapht-users] Minimal vertex separator between two nodes in an undirected graph

Hi all, is there some implemented function in jgrapht to get a minimal vertex separator set between two non adjacent nodes in an undirected graph? I was searching at the javadoc but I can't find if there exist something like that.


I would like to use jgrapht to implement the getMinimalVertexSeparator function in the following example code: 

public static void main(String[] args) {
UndirectedGraph g = new UndirectedGraph(6);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 0);
List<Integer> x = getMinimalVertexSeparator(0, 2, g);

}

​Thanks in advance,​

--
​Federico

------------------------------------------------------------------------------
_______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...