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 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...............

Wow such a nice problem to solve !!! I solved it now you too try !!! :)

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...............

Yeah, post the work here and a specific question. And mark the other thread solved.

i am attaching two documents ..............now my problem arises from step 6 onwards.how pini is calculated and what the logic behind it and onwards........that means step7,8.............so plz help.............

Post your code using codetags instead of attaching it as files.

Also read this.

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.