Find Jobs
Hire Freelancers

Simple algorithm

$30-5000 USD

Selesai
Disiarkan hampir 21 tahun yang lalu

$30-5000 USD

Dibayar semasa penghantaran
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
ID Projek: 2935373

Tentang projek

6 cadangan
Projek jarak jauh
Aktif 21 tahun yang lalu

Ingin menjana wang?

Faedah membida di Freelancer

Tetapkan bajet dan garis masa anda
Dapatkan bayaran untuk kerja anda
Tuliskan cadangan anda
Ianya percuma untuk mendaftar dan membida pekerjaan
Dianugerahkan kepada:
Avatar Pengguna
See private message.
$21.25 USD dalam 14 hari
5.0 (78 ulasan)
5.2
5.2
6 pekerja bebas membida secara purata $135 USD untuk pekerjaan ini
Avatar Pengguna
See private message.
$51 USD dalam 14 hari
5.0 (18 ulasan)
4.2
4.2
Avatar Pengguna
See private message.
$34 USD dalam 14 hari
5.0 (8 ulasan)
2.8
2.8
Avatar Pengguna
See private message.
$510 USD dalam 14 hari
0.0 (0 ulasan)
0.0
0.0
Avatar Pengguna
See private message.
$170 USD dalam 14 hari
0.0 (0 ulasan)
0.0
0.0
Avatar Pengguna
See private message.
$25.50 USD dalam 14 hari
0.0 (0 ulasan)
0.0
0.0

Tentang klien

Bendera UNITED STATES
United States
5.0
17
Ahli sejak Jan 24, 2003

Pengesahan Klien

Terima kasih! Kami telah menghantar pautan melalui e-mel kepada anda untuk menuntut kredit percuma anda.
Sesuatu telah berlaku semasa menghantar e-mel anda. Sila cuba lagi.
Pengguna Berdaftar Jumlah Pekerjaan Disiarkan
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Memuatkan pratonton
Kebenaran diberikan untuk Geolocation.
Sesi log masuk anda telah luput dan telah dilog keluar. Sila log masuk sekali lagi.