<< NL_R_BFS NL_R: Routing NL_R_BFSSearchStart >>

NARVAL >> NL_R: Routing > NL_R_BFSPlot

NL_R_BFSPlot

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

Calling Sequence

[V,P] = NL_R_BFSPlot(G,S,W,I)

Argument

G :

Graph.

S :

Source node.

W :

Display parameter.

I :

Window index.

V :

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

P :

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

Description

NL_R_BFSPlot constructs the BFS tree inside the graph G in respect with the source node S 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 breadth. The vector V gathers the chronological order how the network nodes are visited. P provides the predecessor of each node in order to reach the source node. W 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 W. The graph is plotted in the window I.

Pseudo-Code (Wikipedia)

1. Enqueue the root node.
2. Dequeue a node and examine it.
* If the element sought is found in this node, quit the search and return a result.
* Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined  quit the search and return "not found".
4. Repeat from Step 2.

Examples

n=150;//network size
L=1000;//network square area side
dmax=100;//Locality radius
[g]=NL_T_LocalityConnex(n,L,dmax);//generation of a topology in respect with the Locality method
i=NL_F_RandInt1n(length(g.node_x));//selection of the source node
dw=5;//display parameter
ind=1;//window index
[go,v,pred]=NL_R_BFSPlot(g,i,dw,ind);//application of NL_R_BFSPlot
i
v(1:10)//first ten values
pred(1:10)//first ten values

Dependency

NL_R_BFSSearchStart, NL_G_Nodes2Path, NL_G_ShowGraph

Report an issue
<< NL_R_BFS NL_R: Routing NL_R_BFSSearchStart >>