Member Avatar for san26

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.

  • 5 Contributors
  • 6 Replies
  • 128 Views
  • 13 Hours Discussion Span
  • Latest Post Latest Post by Nick Evan
Member Avatar for 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...............

Member Avatar for csurfer

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

Member Avatar for VernonDozier

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.

Member Avatar for san26

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

#include<stdio.h>
#include<iostream.h>
#include<math.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
#include<process.h>
#include<time.h>
#include "stst.h"
int main(void)

{

	int n,n1=0,n2=0;// no of Demand points
	int *x_list,*y_list;
	int x_no,y_no,st_can_no,visited_no,rx1_no,rx2_no,ry1_no,ry2_no;
	float y_mid,x_mid,mid;
	int xmin,xmax;
	int i,j,k,insertpos,insertpos1;
	int x,y;
	int wrst_no;
	long int mincost,cost1,cost2;
	vertex *temp,*temp1, *uterm,*lterm;
	/*vertex *state;
	vertex * st_can,temp;
	vertex centre1,centre2;
	int found =0;
	edge *wrst;  */
	edge tedge;
	long int wrstcost;
       //	int gd = DETECT,gm;
       //	int maxx=1,maxy=1;
	int long x_range,y_range,rx_range,ry_range;
	float scale,scale1;
	int long p1,q1,p2,q2;
	int  x1,y1,x2,y2,x3,y3;
	long int r,total_weight, reg_n;
	time_t stime,ftime;
	clrscr();
	cout<<"--------------------------------------------------"<<endl;
	cout <<"                     Input                       "<<endl;
	cout<<"--------------------------------------------------"<<endl;
	cout<<"\nEnter the no of Points: - ";
	cin>>n;
	temp=new vertex[n];
	temp1=new vertex[n];
	uterm=new vertex[n];
	lterm=new vertex[n];

	x_list=new  int[n];
	y_list=new  int[n];
   //	st_can=new vertex[n*(n-1)];
	cout<<"\nEnter the co-ordinates of node 1 :";
	cin>>x;
	cin>>y;
	x_list[0]=x;
	x_no=1;
	y_list[0]=y;
	y_no=1;
	temp[0].xpos=x;
	temp[0].ypos=y;
	for(i=1;i<n;i++)
	{

		cout<<"\nEnter the co-ordinate of Node:" << i+1 <<" : " ;
		cin>>x;
		cin>>y;
		/********** Insert X Value into sorted X_list***************/
		j=0;
		while((x_list[j]<=x)&&(j<x_no))
			j++;
		insertpos=j;
		x_no++;
		for(j=x_no-1;j>insertpos;j--)
		       x_list[j]=x_list[j-1];
		x_list[insertpos]=x;
		/********** Insert Y Value into sorted X_list***************/
		j=0;
		while((y_list[j]<=y)&&(j<y_no))
			j++;
		insertpos=j;
		y_no++;
		for(j=y_no-1;j>insertpos;j--)
		       y_list[j]=y_list[j-1];
		y_list[insertpos]=y;
		j=0;
		while((temp[j].xpos<=x)&&(j<i))
			j++;
		insertpos=j;
		for(j=i;j>insertpos;j--)
		{
			temp[j].xpos=temp[j-1].xpos;
			temp[j].ypos=temp[j-1].ypos;
	       }
		temp[insertpos].xpos=x;
		temp[insertpos].ypos=y;

	}
	xmin=x_list[0];
	xmax=x_list[n-1];
	cout<<"Xmin= "<<xmin;
	cout<<"\nXmax= "<<xmax;
       cout<<"\nValues Of X list "<<endl ;
       /*****display x list********/
       {
	       for(i=0;i<x_no;i++)
	       cout<<x_list[i]<<endl;
       }
       cout<<"\nValues Of Y list "<<endl ;
       /*****display x list********/
       {
	       for(i=0;i<y_no;i++)
	       cout<<y_list[i]<<endl;
       }
       /*******Dispaly Of Temp list **********/
	cout<<"display of Temp"<<endl;
	for (i=0;i<n; i++)
	{
	    cout<<temp[i].xpos<<" , "<<temp[i].ypos<<" ,"<<endl;
	}
       if(y_no%2!=0)
       {
	      y_mid=y_list[(y_no+1)/2 - 1];
	      cout<<"Y-Median:= "<<y_mid;
       }
       else
	  {
	      mid = y_list[y_no/2] + y_list[(y_no/2)-1];
	      y_mid=mid/2;
	      cout<<"Y-Median:= "<<y_mid;

	   }
      tedge.start.xpos=xmin;
      tedge.start.ypos=y_mid;
      tedge.end.xpos=xmax;
      tedge.end.ypos=y_mid;
      cout<<"\n"<<tedge.start.xpos<<","<<tedge.start.ypos <<"->"<<tedge.end.xpos<<","<<tedge.end.ypos;
      j=0;
      k=0;
      for(i=0;i<n;i++)
      {
	  if(temp[i].ypos>y_mid)
	  {
		 uterm[j].xpos= temp[i].xpos;
		 uterm[j].ypos=temp[i].ypos;
		 n1++;
		 j++;
	  }
	  else
	  {
	     if(temp[i].ypos!=y_mid)
	     {
		    lterm[k].xpos= temp[i].xpos;
		    lterm[k].ypos=temp[i].ypos;
		    n2++;
		    k++;
	     }
	  }
	 /* for(j=0;j<n1;j++)
	  {
	    if(uterm[j].xpos<uterm[j+1].xpos)
	    {
		 temp1[j].xpos=uterm[j].xpos;
		 uterm[j].xpos=uterm[j+1].xpos;
		 uterm[j+1].xpos= temp1[j].xpos;

	    }

	 } */
   }
      cout<<"\ndisplay of UTerm"<<endl;
      //cout<<"\n"<<n1<<"\n";
	for (j=0;j<n1; j++)
	{
	    cout<<uterm[j].xpos<<" , "<<uterm[j].ypos<<endl;
	}

      cout<<"\ndisplay of LTerm"<<endl;
      //cout<<"\n"<<n1<<"\n";
	for (k=0;k<n2; k++)
	{
	    cout<<lterm[k].xpos<<" , "<<lterm[k].ypos<<endl;
	}

      getch();
       return 0;
}
#include <math.h>
#define MAX_NODES 20
#define TEMP 0
#define PERM 1
class vertex
{
	public:
	float xpos;
	float ypos;
	long int gain;
	int status;

};
class edge
{
	public:
	vertex start;
	vertex end;
	long int cost;
};
Member Avatar for Nick Evan

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.