A. DOMINATING SETS & COMMUNITIES

In [1]:
from IPython.display import Image
%matplotlib inline

/usr/lib/sagemath/local/lib/python2.7/site-packages/setuptools-12.4-py2.7.egg/pkg_resources/__init__.py:1224: UserWarning: /home/mab/.sage//.python-eggs is writable by group/others and vulnerable to attack when used with get_resource_filename. Consider a more secure location (set with .set_extraction_path or the PYTHON_EGG_CACHE environment variable).
In [2]:
%load_ext sage
In [8]:
# Experiment A1: COMPUTING DOMINATING SETS
# Graph type: Erdos-Renyi random graph
nodes = 40 # Number of nodes
p = 0.2 # Probability of link formation

from dom_set import domination,draw_doms,draw_domcomms
G=domination(nodes,p)
g=Graph(G)
dom=g.dominating_set()
idom=g.dominating_set(independent=True)
print 'Edge list:',G.edges()
print 

print 'Minimum Dominating Set (red) = ',dom
print 'Independent Dominating Set (green) = ',idom
print

gamma=len(idom)
# print 'S(G) = ',dom
print 'Domination number = ',len(dom)
print 'Independent domination number = ',gamma
print

nodes=list(G.nodes())
dom_list=[]
node_set=set(nodes)
no_dom_list=[]
for i in G.nodes():
    node_set=set(nodes)
    nei=G.neighbors(i)
    nei.append(i)
    node_set=node_set-set(nei)
    G_Ni=G.subgraph(list(node_set))
    g_ni=Graph(G_Ni)
    dom_ni=g_ni.dominating_set(independent=False)
    if len(dom_ni)>=gamma:
        no_dom_list.append(i)
    else:
        dom_list.append(i)
print 'Possible Minimum Dominating Vertices (magenta) = ',dom_list
print 'Always Minimum Dominated Vertices (cyan) = ',no_dom_list

d=1
dd=3.5
draw_doms(G,dom,idom,dom_list,no_dom_list,d,dd)

Edge list: [(0, 35), (0, 5), (0, 7), (0, 8), (0, 21), (0, 23), (0, 28), (0, 29), (1, 32), (1, 34), (1, 4), (1, 5), (1, 6), (1, 15), (1, 16), (1, 17), (1, 20), (1, 24), (2, 8), (2, 27), (2, 21), (2, 23), (3, 33), (3, 34), (3, 35), (3, 5), (3, 38), (3, 9), (3, 17), (3, 21), (3, 23), (3, 28), (4, 37), (4, 13), (4, 25), (4, 28), (4, 29), (5, 32), (5, 8), (5, 11), (5, 13), (5, 25), (5, 30), (6, 10), (6, 13), (6, 16), (6, 19), (6, 20), (6, 31), (7, 16), (7, 12), (7, 22), (7, 33), (8, 33), (8, 10), (8, 11), (8, 14), (8, 17), (8, 20), (8, 24), (8, 25), (8, 29), (9, 37), (9, 16), (9, 22), (9, 23), (9, 28), (9, 31), (10, 34), (10, 13), (10, 15), (10, 17), (10, 22), (10, 27), (10, 28), (10, 31), (11, 39), (11, 13), (11, 19), (11, 24), (11, 25), (12, 33), (12, 39), (12, 14), (12, 15), (12, 18), (12, 19), (12, 23), (12, 24), (12, 28), (13, 21), (13, 26), (13, 28), (14, 37), (14, 17), (14, 18), (14, 22), (14, 28), (14, 30), (14, 31), (15, 35), (15, 28), (15, 29), (16, 21), (16, 24), (16, 25), (17, 34), (17, 26), (17, 31), (18, 32), (18, 36), (18, 34), (19, 32), (19, 35), (19, 37), (19, 23), (19, 24), (20, 34), (20, 35), (21, 34), (22, 35), (22, 36), (22, 25), (23, 32), (23, 36), (23, 33), (23, 28), (23, 29), (24, 32), (24, 35), (24, 30), (25, 32), (26, 34), (26, 39), (26, 33), (27, 37), (27, 31), (28, 34), (28, 37), (28, 35), (28, 31), (29, 32), (29, 34), (29, 35), (29, 31), (30, 32), (30, 34), (31, 34), (31, 35), (31, 38), (32, 35), (32, 36), (32, 38), (33, 35), (34, 36), (34, 37), (34, 35), (36, 37), (36, 38), (36, 39), (37, 38), (38, 39)]

Minimum Dominating Set (red) =  [12, 21, 25, 31, 34]
Independent Dominating Set (green) =  [2, 13, 14, 16, 35, 36]

Domination number =  5
Independent domination number =  6

Possible Minimum Dominating Vertices (magenta) =  [2, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 22, 23, 25, 26, 27, 28, 32, 35, 36, 37, 38, 39]
Always Minimum Dominated Vertices (cyan) =  [0, 1, 3, 4, 10, 15, 17, 18, 19, 20, 21, 24, 29, 30, 31, 33, 34]
In [9]:
#Experiment A2: COMPUTING DOMINATING SETS AND COMMUNITIES
d=.8
dd=.8
c=1.2
cc=1.4
alpha=0.6
draw_domcomms(G,dom,idom,dom_list,no_dom_list,d,dd,c,cc,alpha)
In [ ]: