Simple algorithm

Completed Posted May 14, 2003 Paid on delivery
Completed Paid on delivery

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

C Programming Engineering Linux MySQL PHP Software Architecture Software Testing UNIX

Project ID: #2935373

About the project

6 proposals Remote project Active May 15, 2003

Awarded to:

bokbokan

See private message.

$21.25 USD in 14 days
(78 Reviews)
5.2

6 freelancers are bidding on average $135 for this job

lalesculiviu

See private message.

$51 USD in 14 days
(18 Reviews)
4.2
igorbartchenkov

See private message.

$34 USD in 14 days
(8 Reviews)
2.8
mokesoftware

See private message.

$510 USD in 14 days
(0 Reviews)
0.0
adnanbhutta

See private message.

$170 USD in 14 days
(0 Reviews)
0.0
vw354015vw

See private message.

$25.5 USD in 14 days
(0 Reviews)
0.0