<< NARVAL_R_PredRoute NARVAL NARVAL_R_RTPathPresence >>

NARVAL >> NARVAL > NARVAL_R_Prim

NARVAL_R_Prim

Perform the Prim's algorithm from a source node on a topology.

Calling Sequence

[go,v,p] = NARVAL_R_Prim(g,i,dw,ind)

Parameters

g :

network graph.

i :

source node.

dw :

display parameter.

ind :

window index.

go :

output graph.

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

NARVAL_R_Prim finds the minimum spanning tree in the weighted graph g (WIKIPEDIA). It constructs a tree in respect with the 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 nearest nodes, unexplored neighbor nodes are explored, and so on. The search is done in respect with a discovery propagation towards the nearest nodes. The vector v gathers the chronological order how network nodes are visited.p 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.

Pseudo-Code (Wikipedia)

for each vertex in graph
   set min_distance of vertex to infinity
   set parent of vertex to null
   set minimum_adjacency_list of vertex to empty list
   set is_in_Q of vertex to true
set min_distance of initial vertex to zero
add to minimum-heap Q all vertices in graph, keyed by min_distance

while latest_addition = remove minimum in Q
    set is_in_Q of latest_addition to false
    add latest_addition to (minimum_adjacency_list of (parent of latest_addition))
    add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)
    for each adjacent of latest_addition
    if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) is inferior to min_distance of adjacent)
        set parent of adjacent to latest_addition
        set min_distance of adjacent to weight-function(latest_addition, adjacent)
        update adjacent in Q, order by min_distance

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
[go,v,pred]=NARVAL_R_Prim(g,i,dw,ind);//application of NARVAL_R_Prim
v
pred

Dependency

NARVAL_R_SearchDistance, NARVAL_G_Nodes2Path, NARVAL_G_ShowGraph

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_PredRoute NARVAL NARVAL_R_RTPathPresence >>