Perform the Depth First Search algorithm from a source node on a topology in respect the node degree metric.
[go,v,pred] = NARVAL_R_DFSW(g,i,dw,ind)
network graph.
source node.
display parameter.
window index.
output graph.
vector that gathers the chronological order how network nodes are visited.
vector composed by the predecessor of each node in order to reach the source node.
NARVAL_R_DFSW is an enhanced version of NARVAL_R_DFS that considers the node degree metric for the research propagation along the graph rather than the node index metric. It constructs a tree inside the graph g in respect with the source node i defined as the root (WIKIPEDIA). This graph search algorithm begins at the root node and explores all the neighboring nodes. Then for each of those nodes with the highest degree, unexplored neighbor nodes are explored, and so on. The search is done in depth. The vector v gathers the chronological order how network nodes are visited. pred provides the predecessor of each node in order to reach the source node. dw is used to display the research propagation on the graph. Thus the tree starts with an initial edge width rating one unit. The last edges connected to the tree leafs are displayed with a width equal to dw. The graph is plotted in the window ind.
void DFS(Graph G, int v) { // DFS PreVisit(G, v); // action on the vertex v G.setMark(v, VISITED); // v is set as visited for (Edge w = G.first(v); G.isEdge(w); w = G.next(w)) if (G.getMark(G.v2(w)) == UNVISITED) DFS(G, G.v2(w)); PostVisit(G, v); // action on the vertex v } | ![]() | ![]() |
n=150;//network size L=1000;//network square area side dmax=100;//Locality radius [g]=NARVAL_T_LocalityConnex(n,L,dmax);//generation of a topology in respect with the Locality method i=NARVAL_F_Random(length(g.node_x));//selection of the source node dw=2;//display parameter ind=1;//window index [go,v,pred]=NARVAL_R_DFSW(g,i,dw,ind);//application of NARVAL_R_DFSW i v(1:10)//first ten values pred(1:10)//first ten values | ![]() | ![]() |
Dr. Foued Melakessou
Research Associate
Interdisciplinary Centre for Security, Reliability and Trust
Room F106
University of Luxembourg
6, rue Coudenhove Kalergi
L-1359 Luxembourg-Kirchberg
E-mail: foued.melakessou@uni.lu
Tel: (+352) 46 66 44 5346