<< NARVAL_R_DFSW NARVAL NARVAL_R_Dijkstra >>

NARVAL >> NARVAL > NARVAL_R_DFSWWD

NARVAL_R_DFSWWD

Perform the Depth First Search algorithm from a source node on a topology in respect the node degree metric (without display).

Calling Sequence

[v,pred] = NARVAL_R_DFSW(g,i)

Parameters

g :

network graph.

i :

source node.

v :

vector that gathers the chronological order how network nodes are visited.

pred :

vector composed by the predecessor of each node in order to reach the source node.

Description

NARVAL_R_DFSWWD constructs the DFS 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 smallest index, 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.

Pseudo-Code (Wikipedia)

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
}

Examples

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
[v,pred]=NARVAL_R_DFSWWD(g,i);//application of NARVAL_R_DFSWWD
i
v(1:10)//first ten values
pred(1:10)//first ten values

Dependency

NARVAL_G_GraphDegDistWD, NARVAL_R_SearchEndW

Authors

Foued Melakessou

Contact

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

Home Page


<< NARVAL_R_DFSW NARVAL NARVAL_R_Dijkstra >>