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.
san26
-13
Newbie Poster
Recommended Answers
Jump to Posthttp://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
Jump to PostWow such a nice problem to solve !!! I solved it now you too try !!! :)
All 6 Replies
Salem
5,138
Posting Sage
VernonDozier
commented:
Caught yet another cross poster.
+17
san26
-13
Newbie Poster
csurfer
422
Posting Pro
VernonDozier
2,218
Posting Expert
Featured Poster
san26
-13
Newbie Poster
Nick Evan
4,005
Industrious Poster
Team Colleague
Featured Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.