Created
June 9, 2015 01:40
-
-
Save jfinkels/9ea6ef5cb50789328c42 to your computer and use it in GitHub Desktop.
Approximate dominating set with postprocessing heuristic
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
************************************** | |
Minimum Vertex and Edge Dominating Set | |
************************************** | |
A dominating set for a graph G = (V, E) is a subset D of V such that every | |
vertex not in D is joined to at least one member of D by some edge. The | |
domination number gamma(G) is the number of vertices in a smallest dominating | |
set for G. Given a graph G = (V, E) find a minimum weight dominating set V'. | |
http://en.wikipedia.org/wiki/Dominating_set | |
An edge dominating set for a graph G = (V, E) is a subset D of E such that | |
every edge not in D is adjacent to at least one edge in D. | |
http://en.wikipedia.org/wiki/Edge_dominating_set | |
""" | |
# Copyright (C) 2011-2012 by | |
# Nicholas Mancuso <nick.mancuso@gmail.com> | |
# All rights reserved. | |
# BSD license. | |
import networkx as nx | |
__all__ = ["min_weighted_dominating_set", | |
"min_edge_dominating_set"] | |
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)""" | |
def min_weighted_dominating_set(G, weight=None,post_process=True): | |
r"""Return minimum weight vertex dominating set. | |
Parameters | |
---------- | |
G : NetworkX graph | |
Undirected graph | |
weight : None or string, optional (default = None) | |
If None, every edge has weight/distance/weight 1. If a string, use this | |
edge attribute as the edge weight. Any edge attribute not present | |
defaults to 1. | |
Returns | |
------- | |
min_weight_dominating_set : set | |
Returns a set of vertices whose weight sum is no more than log w(V) * OPT | |
Notes | |
----- | |
This algorithm computes an approximate minimum weighted dominating set | |
for the graph G. The upper-bound on the size of the solution is | |
log w(V) * OPT. Runtime of the algorithm is `O(|E|)`. | |
References | |
---------- | |
.. [1] Vazirani, Vijay Approximation Algorithms (2001) | |
.. [2] Tal Grossman and Avishai Wool, EJOR 101:81-92, (1997) | |
""" | |
if not G: | |
raise ValueError("Expected non-empty NetworkX graph!") | |
# min cover = min dominating set | |
dom_set = set([]) | |
cost_func = dict((node, nd.get(weight, 1)) \ | |
for node, nd in G.nodes_iter(data=True)) | |
vertices = set(G) | |
vertex_depth=dict((node,0) for node in G) | |
sets = dict((node, set([node]) | set(G[node])) for node in G) | |
def _cost(node,subset): | |
""" Our cost effectiveness function for sets given its weight | |
""" | |
cost = cost_func[node] | |
return cost / float(len(subset - dom_set)) | |
while vertices: | |
# find the most cost effective set, and the vertex that for that set | |
dom_node, min_set = min(sets.items(), | |
key=lambda x: ( _cost(x[0],x[1]),x[0])) # second x[0] is tie breaker, not really needed | |
# add the node to the dominating set and reduce what we must cover | |
dom_set.add(dom_node) | |
del sets[dom_node] | |
vertices = vertices - min_set | |
for v in min_set: vertex_depth[v]=vertex_depth[v]+1 | |
if(post_process): | |
redundancy = dict() | |
for node in dom_set: | |
redundancy[node] = -1+ min(vertex_depth[vv] for vv in (set([node]) | set(G[node]))) | |
(max_redun, redun_node) = max(((redundancy[node],node) for node in redundancy), | |
key = lambda x: (x[0],cost_func[x[1]])) | |
while max_redun > 0: | |
dom_set= dom_set-set([redun_node]) | |
del redundancy[redun_node] | |
for v in set([redun_node]) | set(G[redun_node]): vertex_depth[v]=vertex_depth[v]-1 | |
for node in dom_set: | |
redundancy[node] = -1+ min(vertex_depth[vv] for vv in (set([node]) | set(G[node]))) | |
max_redun, redun_node = max(((redundancy[node],node) for node in redundancy), | |
key = lambda x: (x[0],cost_func[x[1]])) | |
#print vertex_depth | |
#print redundancy | |
return dom_set | |
def min_edge_dominating_set(G): | |
r"""Return minimum cardinality edge dominating set. | |
Parameters | |
---------- | |
G : NetworkX graph | |
Undirected graph | |
post-process=True : | |
Use Grossman & Wool's post-processing method to ensure result is at least | |
minimal. | |
Returns | |
------- | |
min_edge_dominating_set : set | |
Returns a set of dominating edges whose size is no more than 2 * OPT. | |
Notes | |
----- | |
The algorithm computes an approximate solution to the edge dominating set | |
problem. The result is no more than 2 * OPT in terms of size of the set. | |
Runtime of the algorithm is `O(|E|)`. | |
""" | |
if not G: | |
raise ValueError("Expected non-empty NetworkX graph!") | |
return nx.maximal_matching(G) | |
def test_this(): | |
H=nx.path_graph(1) | |
H.add_edge(0,3) | |
H.add_edge(1,3) | |
H.add_edge(2,3) | |
#print nx.nodes(H) | |
s = min_weighted_dominating_set(H) | |
print len(s), "=1?" | |
# should be 1 | |
# here's a good test graph to test post_processing | |
G= nx.path_graph(6) | |
G.add_nodes_from([6,7]) | |
G.add_edges_from([(6,1),(7,4),(6,3),(0,3)]) | |
''' | |
should look like | |
* * | |
/ \ | | |
*-*-*-* | |
\ / | | |
* * | |
''' | |
s = min_weighted_dominating_set(G) | |
print len(s), "=2?" | |
# should = 2 | |
s = min_weighted_dominating_set(G,post_process=False) | |
print len(s), "=3??" # probably 3 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment