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.
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.
微信赞赏
支付宝赞赏