Calculate connected dominating sets (CDS)

It is believed that the minimum connected dominating set problem cannot be solved in polynomial time. To the best of my knowledge, there is no source code available for approximation algorithms. Therefore, I decide to implement one proposed by M. Rai in 2009.

1. MCDS-NON-DISTRIBUTED

1.1 Descriptions

The algorithm I implemented is proposed by M. Rai in 2009.

RAI, M., GARG, N., VERMA, S., et al. A new heuristic approach for minimum connected dominating set in adhoc wireless networks. In : Advance Computing Conference, 2009. IACC 2009. IEEE International. IEEE, 2009. p. 284-289.

The main idea of MCDS-NON-DISTRIBUTED is to form a connected dominating set by transversing all nodes (either breadth first search or depth first search) and continuously removing the node v if G(V-v) is still connected.

  • Transverse nodes, beginning with the node u with the maximum degree. Therefore, we have CDS = {u}, Q = {N(u)} (enqueue u‘s neighbors in descending order by their degree)
  • Pop a node from the queue Q, add v to CDS if G(V-v) is not yet connected otherwise remove it
  • Loop until the queue Q is empty, then we get a connected dominating set for G

1.2 Implementation

The key source code is as follows. Click GitHub, complex networks, dominating sets to access the full source code.

# Step 1: initialization
# take the node with maximum degree as the starting node
starting_node = max(G2.degree().items(), key=operator.itemgetter(1))[0] 
fixed_nodes = {starting_node}

# Enqueue the neighbor nodes of starting node to Q in descending order by their degree
neighbor_nodes = G2.neighbors(starting_node)
neighbor_nodes_sorted = OrderedDict(sorted(G2.degree(neighbor_nodes).items(), key=operator.itemgetter(1), reverse=True)).keys()

priority_queue = deque(neighbor_nodes_sorted) # a priority queue is maintained centrally to decide whether an element would be a part of CDS.

inserted_set = set(neighbor_nodes_sorted + [starting_node])

# Step 2: calculate the cds
while priority_queue:
    u = priority_queue.pop()

    # check if the graph after removing u is still connected
    rest_graph = copy.deepcopy(G2)
    rest_graph.remove_node(u)

    if nx.is_connected(rest_graph):
        G2.remove_node(u)
    else: # is not connected 
        fixed_nodes.add(u)

        # add neighbors of u to the priority queue, which never are inserted into Q
        inserted_neighbors = set(G2.neighbors(u)) - inserted_set
        inserted_neighbors_sorted = OrderedDict(sorted(G2.degree(inserted_neighbors).items(),
                                                        key=operator.itemgetter(1), reverse=True)).keys()

        priority_queue.extend(inserted_neighbors_sorted)
        inserted_set.update(inserted_neighbors_sorted)

return fixed_nodes

1.3 An example

Take Florentine families graph as an example, as shown below, the nodes in red is a connected dominating set.

florentine_families_graph_cds_non_distributed

References:
[1]Wikipedia: Connected dominating set
[2]RAI, M., GARG, N., VERMA, S., et al. A new heuristic approach for minimum connected dominating set in adhoc wireless networks. In : Advance Computing Conference, 2009. IACC 2009. IEEE International. IEEE, 2009. p. 284-289.

发表评论

电子邮件地址不会被公开。 必填项已用*标注