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