[Lemon-user] k-node-connectivity

[Balázs Dezső]

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
>>>>
>>