<p style="margin-bottom:0cm" lang="en-US">Hey,</p>
<p style="margin-bottom:0cm"><span lang="en-US">thanks for your
answers. The examples work very well for directed graphs . I did a
few optimization. It is not necessary do create the SplitNodes objet
at every call of stConnectivity, because it is every time the same
flow-network that.</span></p>
<p style="margin-bottom:0cm">My stConnectivity looks linke this now:</p>
<p style="margin-bottom:0cm">int
Availability::stConnectivity(mySplitNodes splitNodes, CapacityMap
capacity, ListDigraph::Node s, ListDigraph::Node t) {</p>
<p style="margin-bottom:0cm">//performing the max flow algorithm</p>
<p style="margin-bottom:0cm"> Preflow<mySplitNodes,
CapacityMap></p>
<p style="margin-bottom:0cm"> preflow(splitNodes, capacity,
splitNodes.outNode(s), splitNodes.inNode(t));</p>
<p style="margin-bottom:0cm"> preflow.init();</p>
<p style="margin-bottom:0cm"> preflow.startFirstPhase();</p>
<p style="margin-bottom:0cm"> return(preflow.flowValue());
//return the max flow value</p>
<p style="margin-bottom:0cm">}</p>
<p style="margin-bottom:0cm"><br>
</p>
<p style="margin-bottom:0cm" lang="en-US">Note for every one else
likes to use it: the output in the second loop has to be toggled</p>
<p style="margin-bottom:0cm" lang="en-US">minCutSource = u; ->
v<br>minCutTarget = v; -> u</p>
<p style="margin-bottom:0cm" lang="en-US"><br>
</p>
<p style="margin-bottom:0cm" lang="en-US">thanks, although my
question was long time ago ;-)</p>
<br><br><div class="gmail_quote">2012/4/9 <span dir="ltr"><<a href="mailto:lemon-user-request@lemon.cs.elte.hu" target="_blank">lemon-user-request@lemon.cs.elte.hu</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Send Lemon-user mailing list submissions to<br>
<a href="mailto:lemon-user@lemon.cs.elte.hu">lemon-user@lemon.cs.elte.hu</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
or, via email, send a message with subject or body 'help' to<br>
<a href="mailto:lemon-user-request@lemon.cs.elte.hu">lemon-user-request@lemon.cs.elte.hu</a><br>
<br>
You can reach the person managing the list at<br>
<a href="mailto:lemon-user-owner@lemon.cs.elte.hu">lemon-user-owner@lemon.cs.elte.hu</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of Lemon-user digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
1. Re: k-node-connectivity (Bal?zs Dezs?)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Sun, 8 Apr 2012 18:04:16 +0200<br>
From: Bal?zs Dezs? <<a href="mailto:deba.mf@gmail.com">deba.mf@gmail.com</a>><br>
Subject: Re: [Lemon-user] k-node-connectivity<br>
To: Attila Bern?th <<a href="mailto:athos@cs.elte.hu">athos@cs.elte.hu</a>><br>
Cc: Martin <<a href="mailto:bauerhorst0815@googlemail.com">bauerhorst0815@googlemail.com</a>>,<br>
<a href="mailto:lemon-user@lemon.cs.elte.hu">lemon-user@lemon.cs.elte.hu</a><br>
Message-ID:<br>
<CAMNd4+Ujf0oL2aaDOPC572=<a href="mailto:7X-mdBGV_EB3hC3xAiJWWMm_8-A@mail.gmail.com">7X-mdBGV_EB3hC3xAiJWWMm_8-A@mail.gmail.com</a>><br>
Content-Type: text/plain; charset=UTF-8<br>
<br>
Hi,<br>
<br>
I have implemented algorithm 10. It's not well tested well for<br>
directed graphs, but I hope that it is working.<br>
<br>
========================================<br>
#include <lemon/list_graph.h><br>
#include <lemon/adaptors.h><br>
#include <lemon/preflow.h><br>
#include <lemon/lgf_reader.h><br>
#include <limits><br>
<br>
using namespace std;<br>
using namespace lemon;<br>
<br>
int stConnectivity(ListDigraph& graph,<br>
ListDigraph::Node s,<br>
ListDigraph::Node t) {<br>
typedef SplitNodes<ListDigraph> SplitNodes;<br>
SplitNodes splitNodes(graph);<br>
<br>
typedef ConstMap<SplitNodes::Arc, Const<int, 1> > CapacityMap;<br>
CapacityMap capacity;<br>
<br>
Preflow<SplitNodes, CapacityMap><br>
preflow(splitNodes, capacity, splitNodes.outNode(s), splitNodes.inNode(t));<br>
preflow.init();<br>
preflow.startFirstPhase();<br>
<br>
return preflow.flowValue();<br>
}<br>
<br>
int main(int argc, const char *argv[]) {<br>
ListDigraph graph;<br>
<br>
digraphReader(graph, argv[1]).run();<br>
<br>
int minCut = numeric_limits<int>::max();<br>
ListDigraph::Node minCutSource = INVALID;<br>
ListDigraph::Node minCutTarget = INVALID;<br>
<br>
int sourceSize = 0;<br>
for (ListDigraph::NodeIt u(graph); u != INVALID; ++u) {<br>
++sourceSize;<br>
{<br>
ListDigraph::NodeMap<bool> adjacentNodes(graph, false);<br>
adjacentNodes[u] = true;<br>
for (ListDigraph::OutArcIt a(graph, u); a != INVALID; ++a) {<br>
adjacentNodes[graph.target(a)] = true;<br>
}<br>
for (ListDigraph::NodeIt v(graph); v != INVALID; ++v) {<br>
if (adjacentNodes[v]) continue;<br>
int currentCut = stConnectivity(graph, u, v);<br>
if (minCut > currentCut) {<br>
minCut = currentCut;<br>
minCutSource = u;<br>
minCutTarget = v;<br>
}<br>
}<br>
}<br>
{<br>
ListDigraph::NodeMap<bool> adjacentNodes(graph, false);<br>
adjacentNodes[u] = true;<br>
for (ListDigraph::InArcIt a(graph, u); a != INVALID; ++a) {<br>
adjacentNodes[graph.source(a)] = true;<br>
}<br>
for (ListDigraph::NodeIt v(graph); v != INVALID; ++v) {<br>
if (adjacentNodes[v]) continue;<br>
int currentCut = stConnectivity(graph, v, u);<br>
if (minCut > currentCut) {<br>
minCut = currentCut;<br>
minCutSource = u;<br>
minCutTarget = v;<br>
}<br>
}<br>
}<br>
if (sourceSize > minCut) break;<br>
}<br>
std::cout << minCut << std::endl;<br>
return 0;<br>
}<br>
========================================<br>
<br>
If you need to run it on undirected graph, change the graph type to<br>
ListGraph and the second block in the loop can be removed (which<br>
checks the incoming cuts to u). The undirected case was better tested,<br>
I checked that I get the same numbers of graphs with given<br>
connectivity as given in<br>
<a href="http://mathworld.wolfram.com/k-ConnectedGraph.html" target="_blank">http://mathworld.wolfram.com/k-ConnectedGraph.html</a>.<br>
<br>
If you need the the node sets of the cut, you can run one more<br>
preflow. The simpest way to get the cut is to set the capacity to 2<br>
for the original arcs and to 1 for the binding arcs in the adaptor.<br>
Then all cut arcs of the preflow are binding arcs in the adaptor.<br>
<br>
Balazs<br>
<br>
<br>
<br>
On Wed, Apr 4, 2012 at 3:01 PM, Bal?zs Dezs? <<a href="mailto:deba.mf@gmail.com">deba.mf@gmail.com</a>> wrote:<br>
>>> fix a node $s$<br>
>>> for every other node $t$, determine the node connectivity from $s$ to<br>
>>> $t$ using the SplitNodes adaptor, and a maxflow algorithm (and also<br>
>>> from $t$ to $s$): the minimum of these will be the node connectivity<br>
>>> of the (di)graph.<br>
> I think, this algorithm is not complete. This can be done for edge<br>
> connectivity, but it's not suitable for node connectivity. This<br>
> algorithm does not cover the case when s is part of the cut nodes. The<br>
> algorithm 11 does almost the same, but it also takes all adjacent<br>
> nodes of s, and calculates the cut between each node pairs. If the<br>
> node s is not part of every minimum cut of the graph, then the<br>
> suggested algorithm finds the minimum cut. Otherwise, node s has two<br>
> neighbors which are on the two sides of the cut, so the second<br>
> iteration finds the cut. If you implement this algorithm, s should be<br>
> chosen with the smallest degree.<br>
><br>
> Other solution to use at least K+1 source nodes to compute the minimum<br>
> cut from and to, where K is the global minimum cut. Then you can be<br>
> sure, that at least of the source nodes was not part of all minimum<br>
> cuts. Because K is not known at the beginning of the algorithm,<br>
> therefore you can start with a large estimation, and adjust the value<br>
> when a new cut is found. It is in Algorithm 10.<br>
><br>
> Balazs<br>
><br>
><br>
> On Wed, Apr 4, 2012 at 12:43 PM, Martin <<a href="mailto:bauerhorst0815@googlemail.com">bauerhorst0815@googlemail.com</a>> wrote:<br>
>> Hi,<br>
>><br>
>> thanks for your reply Balazs and Attila.<br>
>><br>
>> @Attila: If you like and have the time it would be quite helpful for me<br>
>> to get some example code for the node connectivity (third issue of your<br>
>> answer).<br>
>><br>
>> Thanks a lot in advance,<br>
>> Martin<br>
>><br>
>>> Hi Martin,<br>
>>><br>
>>> As far as I know, this is not implemented explicitly, but it is easy to get:<br>
>>> to determine graph edge-connectivity, use Nagamochi-Ibaraki,<br>
>>> to determine digraph arc-connectivity, use Hao-Orlin,<br>
>>><br>
>>> to determine the node-connectivities, you can only use the SplitNodes<br>
>>> adaptor (as Bal?zs also writes), but you need to calculate the<br>
>>> node-connectivity using a maxflow method for some pairs of nodes:<br>
>>><br>
>>> fix a node $s$<br>
>>> for every other node $t$, determine the node connectivity from $s$ to<br>
>>> $t$ using the SplitNodes adaptor, and a maxflow algorithm (and also<br>
>>> from $t$ to $s$): the minimum of these will be the node connectivity<br>
>>> of the (di)graph.<br>
>>><br>
>>> Attila<br>
>>><br>
>>> Ps: I can put together some example code, if you wish, for one of these.<br>
>>><br>
>>> Martin <<a href="mailto:bauerhorst0815@googlemail.com">bauerhorst0815@googlemail.com</a>> ?rta (2012. ?prilis 3. 22:02):<br>
>>>> Hi,<br>
>>>><br>
>>>> does anybody know a function to get the k-node-connectivity<br>
>>>> (k-vertex-connectivity) of a digraph (or graph)?<br>
>>>> (<a href="http://en.wikipedia.org/wiki/K-vertex-connected_graph" target="_blank">http://en.wikipedia.org/wiki/K-vertex-connected_graph</a>)<br>
>>>> I could only find the function biNodeConnected to check whether a graph<br>
>>>> is 2-node-connected so far.<br>
>>>><br>
>>>> Thanks,<br>
>>>> Martin<br>
>>>> _______________________________________________<br>
>>>> Lemon-user mailing list<br>
>>>> <a href="mailto:Lemon-user@lemon.cs.elte.hu">Lemon-user@lemon.cs.elte.hu</a><br>
>>>> <a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
>>>><br>
>><br>
<br>
<br>
------------------------------<br>
<br>
_______________________________________________<br>
Lemon-user mailing list<br>
<a href="mailto:Lemon-user@lemon.cs.elte.hu">Lemon-user@lemon.cs.elte.hu</a><br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
<br>
<br>
End of Lemon-user Digest, Vol 52, Issue 4<br>
*****************************************<br>
</blockquote></div><br>