<< RoutingConnNeighbor Network Topology Generator RoutingDFSWeight >>

Network Topology Generator >> Network Topology Generator > RoutingDFS

RoutingDFS

Perform the Depth First Search algorithm from a source node on a topology in respect the node index metric.

Calling Sequence

[v,pred]=RoutingDFS(g,i,dw)

Parameters

g :

network graph.

i :

source node.

dw :

display parameter.

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

RoutingDFS aims to construct a tree inside the graph g in respect with a source node i defined as the root. 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. v is a vector that 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.

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]=NtgLocalityConnex(n,L,dmax);//generation of a topology in respect with the Locality method
i=Random(length(g.node_x));//selection of the source node
dw=2;//display parameter
[v,pred]=RoutingDFS(g,i,dw);//application of RoutingDFS
v
pred

Dependency

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact


<< RoutingConnNeighbor Network Topology Generator RoutingDFSWeight >>