 |  |  |  |  |  |  |  |
need c++ implementation of the algorithm
Please support our C++ advertiser: Intel Parallel Studio Home
 |
can anybody help me on this algo provided below....................
I need a c++ implementation for the following algorithm.............
Algorithm RST-T
Input: A set of points P = {(xi, yi)}
Output: A rectilinear Steiner tree with all points in P connected
A. Build an RST-T with horizontal trunk
1. Set ymid = median of all yi
2. Set xmin = Min{xi|(xi,ymid)∈P}, xmax = Max{xi|(xi,ymid)∈P}
3. Construct a horizontal trunk from (xmin,ymid) to (xmax, ymid)
4. Set U = {(x,y)|(x,y)∈P and y > ymid}
L = {(x,y)|(x,y)∈P and y <ymid}
5. Sort all points in U according to their x coordinate by
descending order
6. Set Pini=(x,y),where (x,y)∈U and (x,y) minimize |x-xmin|+|x- xmax|
7. Connect Pini to the trunk, going vertical direction first
8. For all the points in U and to the left of Pini, from right to left,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
9. For all the points in U and to the right of Pini, from left to right,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
10. Repeat the procedure from step 5 to step 9, process points in L
B. Build an RST-T with vertical trunk in the similar way to A.
C. Return one tree with shorter total wirelength from two trees built
by step A and step B.
I need a c++ implementation for the following algorithm.............
Algorithm RST-T
Input: A set of points P = {(xi, yi)}
Output: A rectilinear Steiner tree with all points in P connected
A. Build an RST-T with horizontal trunk
1. Set ymid = median of all yi
2. Set xmin = Min{xi|(xi,ymid)∈P}, xmax = Max{xi|(xi,ymid)∈P}
3. Construct a horizontal trunk from (xmin,ymid) to (xmax, ymid)
4. Set U = {(x,y)|(x,y)∈P and y > ymid}
L = {(x,y)|(x,y)∈P and y <ymid}
5. Sort all points in U according to their x coordinate by
descending order
6. Set Pini=(x,y),where (x,y)∈U and (x,y) minimize |x-xmin|+|x- xmax|
7. Connect Pini to the trunk, going vertical direction first
8. For all the points in U and to the left of Pini, from right to left,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
9. For all the points in U and to the right of Pini, from left to right,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
10. Repeat the procedure from step 5 to step 9, process points in L
B. Build an RST-T with vertical trunk in the similar way to A.
C. Return one tree with shorter total wirelength from two trees built
by step A and step B.
•
•
Join Date: Dec 2005
Posts: 5,850
Reputation: 
Solved Threads: 751
http://www.daniweb.com/forums/announcement8-2.html
And we need you to make an effort to solve your own homework, which is more than just cross-posting
And we need you to make an effort to solve your own homework, which is more than just cross-posting
i have developed coding upto step 5 btt after that i am getting confused..............so plz help and if u want to see my work i can post here...............
•
•
Join Date: Jan 2009
Posts: 476
Reputation:
Solved Threads: 76
Posting Pro in Training
Wow such a nice problem to solve !!! I solved it now you too try !!! 
I Surf in "C"....
•
•
Join Date: Jan 2008
Posts: 3,842
Reputation:
Solved Threads: 503
•
•
•
•
Originally Posted by san26 
i have developed coding upto step 5 btt after that i am getting confused..............so plz help and if u want to see my work i can post here...............
|
Similar Threads
- Question about string pattern matching (Java)
- The fastest combination generator (Computer Science)
- implementation of algorithm (Computer Science)
- Graphe implementation (Java)
- request code for a non-recursive binary search in MIPS (Assembly)
- finding extrimum of function (C++)
- help with parrallel arrays (C++)
- project (Java)
Other Threads in the C++ Forum
Views: 320 | Replies: 6
| Thread Tools | Search this Thread |
Latest C++ Posts
- Today's Posts
- Unanswered Threads
Related Forum Features
Tag cloud for C++
6 api array arrays beginner binary bmp c++ c/c++ calculator char class classes code compile compiler console conversion convert count data delete desktop directshow dll download dynamic encryption error file forms fstream function functions game givemetehcodez google graph gui iamthwee ifstream input int java lib library lines linkedlist linker loop looping loops map math matrix memory microsoft newbie news number output pointer problem program programming project python random read recursion recursive reference return sort stream string strings struct studio system temperature template templates test text text-file tree unix url variable vector video visual visualstudio void win32 windows winsock wordfrequency wxwidgets
