<< NL_G_Star NL_G: Graph NL_G_WCDSChannel >>

NARVAL >> NL_G: Graph > NL_G_WCDS

NL_G_WCDS

Generate a Weakly Connected Dominating Set (WCDS) of a graph.

Calling Sequence

[Go,N,E] = NL_G_WCDS(G)

Arguments

G :

Graph.

N :

List of master nodes (nucleus).

E :

List of slave nodes (electron).

:

Output graph.

Description

NL_G_WCDS performs the Weakly Connected Dominated Set (WCDS) of the graph G (WIKIPEDIA). Each node of the graph receives a role (master/slave, nucleus/electron). The list of master (respectivelly slave) nodes is N (respectivelly E). The most connected node of the graph is selected as the root. It is also a master node. Each node can be white, gray or black. All nodes are initialized to white, except the root node that is black. The list T is defined and updated with black and gray nodes. When a white or gray vertex is colored in black, all of its white neighbors become gray. When a vertex is colored in black, it is placed in T along with all of its newly grey neighbors. The construction runs while there is white nodes in the graph. At each loop, the candidates consist of the gray nodes of T and their adjacent white nodes. For each candidate, the number of white vertices that are in the direct neighborhood is performed. The candidate that has the maximum value is chosen to be dyed black.

Examples

n=200;//network size
l=1000;//network squared area side
d=100;//Locality radius
[g]=NL_T_LocalityConnex(n,l,d);//generation of a topology
[go,n,e]=NL_G_WCDS(g);//application of NL_G_WCDS
w=1;//window index
f=NL_G_ShowGraphN(go,w);//graph visualization
n(1:10)//first ten nucleus
e(1:10)//first ten electrons

Dependency

NL_G_GraphDegreeDist, NL_G_NodeNeighbors

Report an issue
<< NL_G_Star NL_G: Graph NL_G_WCDSChannel >>