Simple algorithm

Completado Publicado May 14, 2003 Pagado a la entrega
Completado Pagado a la entrega

The algorithm should do the following: 1) Accept a text file that has a graph represented as an adjacency list. 2) Get a designated root from the user .For example, "r". The root is nothing but a vertex from the input graph. 3) Find the layering of the graph with respect to the root as the following: a) Layer 1 has nodes that are adjacent to the root. b) Layer 2 has nodes that are adjacent to ones in Layer 2 but not adjacent to the root. c) In general, Layer n has nodes that have the shortest path to the root as n. 4) Find the set of "unavoidable edges" with repect to the selected root. Unavoidable edges are computed as the following: a) Edge (x,y) is unavoidable by the root "r" if "x" is in Layer "n", and "x" has only one adjacent node "y" in the previous layer (Layer "n-1"). 5) Contruct the following array from the previous steps: a) The array has |V|+1 rows such that |V| is the number of verticex in the input graph. b) The array has |E| columns such that |E| is the number of edges in the input graph. c) Cell[i][j] is set to "1" if edge "j" is unavoidable by vertex "i", and is set to "0" otherwise. d) We have |V| counters, each one counts the number of unavoidable edges in the array with repect to each vertex. That is, each counter has the number of "1"s in each row. 6) Apply the follwoing algorithm on the array constructed in step (5). a) Set the value of "R" to nill. "R" is a list/set of vertices. b) Repeat c) Choose the vertex that has a maximum number of unavoidable edges (largest counter value). Assume this vertex is "z". d) Add "z" to "R". e) Remove all edges which are unavoidabe by "z" from the array by setting the values of ALL cells in the columns represent these edges to "zero". f) Update the values of counters. g) Until all counters are "zero". 7) Write the follwoing in an output file: a) The layering of the input graph. That is, layer number and vertices in that layer. b) The value of "R" which is the result

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased.

## Platform

Standard Unix/Linux

Programación en C Ingeniería Linux MySQL PHP Arquitectura de software Verificación de software UNIX

Nº del proyecto: #2935373

Sobre el proyecto

6 propuestas Proyecto remoto Activo May 15, 2003

Adjudicado a:

bokbokan

See private message.

$21.25 USD en 14 días
(78 comentarios)
5.2

6 freelancers están ofertando un promedio de $135 por este trabajo

lalesculiviu

See private message.

$51 USD en 14 días
(18 comentarios)
4.2
igorbartchenkov

See private message.

$34 USD en 14 días
(8 comentarios)
2.8
mokesoftware

See private message.

$510 USD en 14 días
(0 comentarios)
0.0
adnanbhutta

See private message.

$170 USD en 14 días
(0 comentarios)
0.0
vw354015vw

See private message.

$25.5 USD en 14 días
(0 comentarios)
0.0