/*------------------------------------------------------------------
AutoPart 1.2
This is a tool to automatically partition a ns2 script into a number 
of pdns scripts that could be run as fast as possible. Please check
out the tool's webpage:
  http://www.cc.gatech.edu/~xu/autopart/

Change history:
Version 1.2, 3/12/2005
Fixed a problem that would seg-fault if two connected agents
do not have traffic attached.

Version 1.1, 9/28/2004
Fixed a bug that assigned wrong ip addresses in some cases.

Version 1.0, 9/9/2004
Public release of this code.

Donghua Xu
College of Computing
Georgia Institute of Technology
Email: xu@cc.gatech.edu
------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <regex.h>
#include <string.h>
#include <unistd.h>
#include <getopt.h>
#include <math.h>

#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <iostream>
#include <fstream>
#include <string>
using std::string;
using namespace std;

#define MAX_LINE_LEN 1024
#define MAX_MATCHED 6
#define MAX_MATCHED_LEN  32

#define MAX_REGISTERS 10
struct re_registers regs;
regoff_t REG_STARTS[MAX_REGISTERS];
regoff_t REG_ENDS[MAX_REGISTERS];

typedef unsigned int oid_t; //the type for object id, e.g. nodes
typedef unsigned long long loid_t; //longer object id type, e.g. links, conns

int NODE_SELF_WEIGHT[2] = {1, 1};
int NODE_TRAFFIC_WEIGHT[2] = {20, 20};
int LINK_SELF_WEIGHT[2] = {1, 1};
int LINK_TRAFFIC_WEIGHT[2] = {20, 4};
int LINK_DELAY_WEIGHT[2] = {40, 40};
int LA_WEIGHT_CONSTANT[2] = {0, 0};
int CT_WEIGHT_CONSTANT[2] = {0, 0};
double LA_THRESHOLD = 0.002; 


int LEVEL_SIZES[2];
int LEVEL_BIT_LENS[2];
int ToReadRoutes = 0;
int ToWriteRoutes = 0;
string RRoutesFileName;
string WRoutesFileName;

const char *regexcompile(char *pattern, 
			 struct re_pattern_buffer *compiled_pattern) {
  const char *retc;
  memset(compiled_pattern, '\0', sizeof(*compiled_pattern));
  re_set_syntax(RE_NO_BK_PARENS);
  retc = re_compile_pattern(pattern, strlen(pattern), compiled_pattern);
  if (retc) {
    printf("re_compile_pattern retc=%s\n", retc);
    exit(1);
  }
  re_set_registers(compiled_pattern, &regs, MAX_REGISTERS, 
		   REG_STARTS, REG_ENDS);
  return retc;
 
}


int regexmatch(char *str, struct re_pattern_buffer *compiled_pattern, 
	       int numMatch, char Matched[][MAX_MATCHED_LEN]) {
  //  struct re_registers regs;
  int reti;

  //memset(&regs, '\0', sizeof(regs));
  reti = re_match(compiled_pattern, str, strlen(str), 0, &regs);
  if (reti > 0) {
    //printf("str = %s\n", str);
    //printf("num_regs=%d\n", regs.num_regs);
    for (int i=0; i<numMatch; i++) {
      //printf("i=%d, regs.end[i+1]=%d, regs.start[i+1]=%d\n", i, regs.end[i+1], regs.start[i+1]);
      int len = regs.end[i+1] - regs.start[i+1];
      strncpy(Matched[i], &(str[regs.start[i+1]]), len);
      Matched[i][len] = '\0';
    }
  }

  return reti;
  
}


int GetOpts(int argc, char *argv[], char *optstr, int LEVEL_SIZES[]) {
  int c, i, opt_count=0;
  string n;

  LEVEL_SIZES[0] = 0;
  LEVEL_SIZES[1] = 0;

  while ((c = getopt(argc, argv, "n:W:R:")) != -1) {
    opt_count ++;
    switch (c) {
    case 'n': 
      n = optarg; 
      i = n.find(".");
      if (i==string::npos) {
	LEVEL_SIZES[0] = atoi(n.c_str());
      } else {
	LEVEL_SIZES[0] = atoi(n.substr(0, i).c_str());
	LEVEL_SIZES[1] = atoi(n.substr(i+1, n.length()-i-1).c_str());
      }
      break;
    case 'R':
      ToReadRoutes = 1;
      RRoutesFileName = optarg;
      break;
    case 'W': 
      ToWriteRoutes = 1;
      WRoutesFileName = optarg;
      break;
    }

  }
  if (LEVEL_SIZES[0] == 0)
    LEVEL_SIZES[0] = 1;
  if (LEVEL_SIZES[1] == 0)
    LEVEL_SIZES[1] = 1;

  for (int i = 0; i < 2; i++)
    if (LEVEL_SIZES[i] == 1)
      LEVEL_BIT_LENS[i] = 1;
    else
      LEVEL_BIT_LENS[i] = int(log(LEVEL_SIZES[i] - 1.0) / log(2.0)) + 1;

  cout << "L0 SIZE=" << LEVEL_SIZES[0] 
       << ", L1 SIZE=" << LEVEL_SIZES[1] << endl;
  return opt_count;

}

map<int,string>QTypeID2Name;
map<string,int>QTypeName2ID;

class LinkClass {
public:
  double bandwidth;
  double delay;
  int qtype;
  unsigned int traffic_volume;

  LinkClass(char[], char[], char[]);
  ~LinkClass();

  void set_qtype(string qtname) {
    if (QTypeName2ID.find(qtname) == QTypeName2ID.end()) {
      //this queue type name has not been encounterd before
      int qtcount = QTypeID2Name.size();
      QTypeID2Name[qtcount] = qtname;
      QTypeName2ID[qtname] = qtcount;
      qtype = qtcount;
    } else {
      qtype = QTypeName2ID[qtname];
    }
  }
  
  const char* get_qtype() {
    return(QTypeID2Name[qtype].c_str());
  }

  /*
  const char* get_qtype() {
    if (qtype==1) 
      return "DropTail";
    else
      return "OtherQ";
  }
  */
};

struct re_pattern_buffer bandwidth_p, delay_p;

LinkClass::LinkClass(char bstr[], char dstr[], char qstr[]) {
  char line[MAX_LINE_LEN];
  char Matched[MAX_MATCHED][MAX_MATCHED_LEN];
  char tmp[80];

  traffic_volume = 0;

  if(regexmatch(bstr, &bandwidth_p, 4, Matched)>0) {
    bandwidth = atof(Matched[0]); // the number
    char bwunit = Matched[1][0]; // the unit, basic is bits
    switch (bwunit) {
    case 'k':
    case 'K': bandwidth *= 1000; break;
    case 'm':
    case 'M': bandwidth *= 1000000; break;
    case 'g':
    case 'G': bandwidth *= 1000000000; break;
    case 't':
    case 'T': bandwidth *= 1000000000000ULL; break;
    }
    
    //printf("converted bandwidth=%lf\n", bandwidth);
  }

  if(regexmatch(dstr, &delay_p, 4, Matched)>0) {
    delay = atof(Matched[0]); // the number
    char dlunit = Matched[1][0]; // the unit, basic is seconds
    switch (dlunit) {
    case 'm':
    case 'M': delay /= 1000; break;
    case 'u':
    case 'U': delay /= 1000000; break;
    case 'n':
    case 'N': delay /= 1000000000; break;
    }

    //printf("converted delay=%lf\n", delay);
    
  }

  string qtypestr = qstr;
  set_qtype(qtypestr);
}

#define INVALID 0xFFFFFFFF

LinkClass::~LinkClass() {
}

enum node_role_e {
  ENDHOST,
  ROUTER,
  INEFFECTIVE //ineffective node, meaning an endhost that does not send traffic
};

class NodeClass {
public:
  oid_t mid; //metis index
  vector<oid_t> agents; // the agents attached to this node
  vector<oid_t> nbrs; //the neighbors of this node
  unsigned int traffic_volume; // the traffic volume passing this node
  node_role_e role;

  NodeClass(oid_t metisid) {
    mid = metisid;
    traffic_volume = 0; //initialize the traffic volume
  }

  ~NodeClass();
};


map<int,string>AgtTypeID2Name;
map<string,int>AgtTypeName2ID;

class AgentClass {
public:
  int type; // the type of agent, e.g., "TCP"
  oid_t traffic; // the traffic source attached to this agent
  oid_t node; // the node this agent attached to

  AgentClass(char agent_type[]) {
    string atname = agent_type;
    if (AgtTypeName2ID.find(atname) == AgtTypeName2ID.end()) {
      //this application type name has not been encounterd before
      int atcount = AgtTypeID2Name.size();
      AgtTypeID2Name[atcount] = atname;
      AgtTypeName2ID[atname] = atcount;
      type = atcount;
    } else {
      type = AgtTypeName2ID[atname];
    }

    traffic = INVALID;
  }

  ~AgentClass();

  const char* get_type() {
    return(AgtTypeID2Name[type].c_str());
  }

};

map<int,string>AppTypeID2Name;
map<string,int>AppTypeName2ID;

class TrafficClass{
public:
  int type; // the type of this traffic, e.g., "FTP"
  oid_t agent; // the agent this traffic attached to
  double start_time; // the time this traffic starts
  double stop_time; // the time this traffic stops

  TrafficClass(char traff_type[]) {
    string atname = traff_type;
    if (AppTypeName2ID.find(atname) == AppTypeName2ID.end()) {
      //this application type name has not been encounterd before
      int atcount = AppTypeID2Name.size();
      AppTypeID2Name[atcount] = atname;
      AppTypeName2ID[atname] = atcount;
      type = atcount;
    } else {
      type = AppTypeName2ID[atname];
    }

  }

  ~TrafficClass();

  const char* get_type() {
    return(AppTypeID2Name[type].c_str());
  }

};

class ConnectionClass{
public:
  int tmp;
  deque<oid_t> PathHops;

  ConnectionClass(int t) {
    tmp = t;
  }

  ~ConnectionClass() {
  }
};

class RouterClass {
public:
  unsigned int weight[2]; //weight of the router
  vector<oid_t> routernbrs; // neighbors that are routers
  unsigned short group[2]; //group information
  
  RouterClass() {
    weight[0] = 0;
    weight[1] = 0;
    group[0] = 0;
    group[1] = 0;
  }
  ~RouterClass() {
  }
};

class RouterLinkClass {
public:
  unsigned weight[2];
  int split; // to mark whether this link is a split link

  RouterLinkClass() {
    weight[0] = 0;
    weight[1] = 0;
    split = 0;
  }
};

class AddRouteClass {
public:
  oid_t router;
  oid_t rlinkip;
  oid_t ip2;
  oid_t ip1;
  oid_t fnode;

  AddRouteClass(oid_t n, oid_t rip, oid_t i2, oid_t i1, oid_t fn) {
    router = n;
    rlinkip = rip;
    ip2 = i2;
    ip1 = i1;
    fnode = fn;
  }

  ~AddRouteClass() {
  }
    
};

class BindClass {
public:
  oid_t node;
  oid_t agent;
  oid_t port;

  BindClass(oid_t n, oid_t a, oid_t p) {
    node = n;
    agent = a;
    port = p;
  }
};

class IPConnectClass {
public:
  oid_t agent;
  oid_t ip;
  oid_t port;

  IPConnectClass(oid_t a, oid_t i, oid_t p) {
    agent = a;
    ip = i;
    port = p;
  }
};


typedef map<loid_t, oid_t>::iterator rlinks_it;
typedef map<oid_t, oid_t>::iterator assignips_it;

class PartitionClass {
public:
  oid_t *routers;
  oid_t rcount;
  map<loid_t, oid_t> rlinks; // remote links
  map<oid_t, oid_t> assignips;
  vector<AddRouteClass*> addroutes;
  vector<BindClass*> binds;
  vector<IPConnectClass*> ipconnects; //remote connects
  vector<loid_t> connects; // local connects

  PartitionClass() {
    rcount = 0;
  }
} *Whole_Part, **Level1_Parts, ***Level2_Parts;


map<oid_t, NodeClass*> nodes;
typedef map<oid_t, NodeClass*>::iterator nodes_it;
typedef map<oid_t, RouterClass*> routers_t;
routers_t routers;
typedef map<oid_t, RouterClass*>::iterator routers_it;
map<oid_t, AgentClass*> agents;
typedef map<oid_t, AgentClass*>::iterator agents_it;
map<oid_t, TrafficClass*> traffic;
typedef map<oid_t, TrafficClass*>::iterator traffic_it;
map<loid_t, ConnectionClass*> connections; 
typedef map<loid_t, ConnectionClass*>::iterator connections_it; 
map<oid_t, oid_t> orignodeidm2n; 
typedef map<oid_t, oid_t>::iterator orignodeidm2n_it; 
map<loid_t, LinkClass*> links;
typedef map<loid_t, LinkClass*>::iterator links_it;
map<loid_t, RouterLinkClass*> routerlinks;
typedef map<loid_t, RouterLinkClass*>::iterator routerlinks_it;


vector<string> beginning_lines;
typedef vector<string>::iterator beginning_lines_it;
vector<string> after_node_lines;
typedef vector<string>::iterator after_node_lines_it;
vector<string> after_link_lines;
typedef vector<string>::iterator after_link_lines_it;
vector<string> ending_lines;
typedef vector<string>::iterator ending_lines_it;
int line_count = 0;
int node_count = 0;
int link_count = 0;
int agent_count = 0;
int traffic_count = 0;
double finish_time;


void ReadNSScript(char *fname) {
  enum {
    BEGINNING, 
    AFTER_NODE,
    AFTER_LINK, 
    ENDING} ReadingSegment = BEGINNING;

  char line[MAX_LINE_LEN];
  char Matched[MAX_MATCHED][MAX_MATCHED_LEN];

  cout << "Opening ns script " << fname << endl;
  ifstream orig_script(fname);
  if (!orig_script) {
    cerr << "Error: cannot open the input ns script " 
	 << fname << endl;
    exit(1);
  }

  const char *retc;
  struct re_pattern_buffer 
    set_node_p, 
    link_p,
    agent_p,
    node_attach_agent_p,
    set_traffic_source_p,
    traffic_attach_agent_p,
    traffic_start_p,
    traffic_stop_p,
    connection_p,
    finish_p;

  retc = regexcompile("([0-9\\.]+)((\\w?)([bB]?))?", &bandwidth_p);
  retc = regexcompile("([0-9\\.]+)((\\w?)([sS]?))?", &delay_p);
  retc = regexcompile("set node\\((.+)\\) ", &set_node_p);
  retc = regexcompile(".+duplex-link \\$node\\((.+)\\) \\$node\\((.+)\\) (.+) (.+) (.+)", &link_p);
  retc = regexcompile("set agent\\((.+)\\) \\[new Agent/(.+)\\]", &agent_p);
  retc = regexcompile(".+attach-agent \\$node\\((.+)\\) \\$agent\\((.+)\\)", &node_attach_agent_p);
  retc = regexcompile("set traffic_source\\((.+)\\) \\[new Application/(.+)\\]", &set_traffic_source_p);
  retc = regexcompile("\\$traffic_source\\((.+)\\) attach-agent \\$agent\\((.+)\\)", &traffic_attach_agent_p);
  retc = regexcompile(".+at (.+) .*traffic_source\\((.+)\\) start", &traffic_start_p);
  retc = regexcompile(".+at (.+) .*traffic_source\\((.+)\\) stop", &traffic_stop_p);
  retc = regexcompile(".+connect \\$agent\\((.+)\\) \\$agent\\((.+)\\)", &connection_p);
  retc = regexcompile(".+at (.+) .*finish", &finish_p);

  while (orig_script.getline(line, MAX_LINE_LEN)){
    if(regexmatch(line, &set_node_p, 1, Matched) > 0) {
      ReadingSegment = AFTER_NODE;
      oid_t nsnodeid = atoi(Matched[0]);
      oid_t metisid = node_count;
      orignodeidm2n[metisid] = nsnodeid;
      nodes[nsnodeid] = new NodeClass(metisid);
      //cout << "node[" << node_count << "] = " << atoi(Matched[0]) << endl;
      node_count ++;
    } else if (regexmatch(line, &link_p, 5, Matched) > 0) {
      loid_t n1, n2;
      ReadingSegment = AFTER_LINK;
      n1 = atoi(Matched[0]);
      n2 = atoi(Matched[1]);
      if (nodes.find(n1) == nodes.end() ) {
	printf("Error: undefined node %d link to node %d\n", n1, n2);
	exit(1);
      }
      if (nodes.find(n2) == nodes.end() ) {
	printf("Error: node %d link to undefined node %d\n", n1, n2);
	exit(1);
      }
      //the index of link is 8 bytes, higher 4 bytes for n1 and lower for n2
      links[(n1<<32) + n2] = new LinkClass(Matched[2], Matched[3], Matched[4]);
      nodes[n1]->nbrs.push_back(n2);
      nodes[n2]->nbrs.push_back(n1);
      link_count++;
    } else if (regexmatch(line, &agent_p, 2, Matched) > 0) {
      ReadingSegment = ENDING;
      oid_t agent = atoi(Matched[0]);
      agents[agent] = new AgentClass(Matched[1]);
      agent_count ++;
    } else if (regexmatch(line, &node_attach_agent_p, 2, Matched) > 0) {
      oid_t node = atoi(Matched[0]);
      oid_t agent = atoi(Matched[1]);
      if (nodes.find(node) == nodes.end()) {
	printf("Error: agent %d attached to undefined node %d\n", agent, node);
	exit(1);
      }
      if (agents.find(agent) == agents.end()) {
	printf("Error: undefined agent %d attached to node %d\n", agent, node);
	exit(1);
      }

      agents[agent]->node = node;
      nodes[node]->agents.push_back(agent);
    } else if (regexmatch(line, &set_traffic_source_p, 2, Matched) > 0) {
      oid_t traff = atoi(Matched[0]);
      traffic[traff] = new TrafficClass(Matched[1]);
      traffic_count ++;
    } else if (regexmatch(line, &traffic_attach_agent_p, 2, Matched) > 0) {
      oid_t traff = atoi(Matched[0]);
      oid_t agent = atoi(Matched[1]);
      if (traffic.find(traff) == traffic.end()) {
	printf("Error: undefined traffic source %d attached to agent %d\n",
	       traff, agent);
	exit(1);
      }
      if (agents.find(agent) == agents.end()) {
	printf("Error: traffic source %d attached to undefined agent %d\n",
	       traff, agent);
	exit(1);
      }

      traffic[traff]->agent = agent;
      agents[agent]->traffic = traff;
    } else if (regexmatch(line, &traffic_start_p, 2, Matched) > 0) {
      double start_time = atof(Matched[0]);
      oid_t traff = atoi(Matched[1]);
      if (traffic.find(traff) == traffic.end()) {
	printf("Error: undefined traffic source %d starts at %lf\n",
	       traff, start_time);
	exit(1);
      }
      traffic[traff]->start_time = start_time;
    } else if (regexmatch(line, &traffic_stop_p, 2, Matched) > 0) {
      double stop_time = atof(Matched[0]);
      oid_t traff = atoi(Matched[1]);
      if (traffic.find(traff) == traffic.end()) {
	printf("Error: undefined traffic source %d stops at %lf\n",
	       traff, stop_time);
	exit(1);
      }
      traffic[traff]->stop_time = stop_time;
    } else if (regexmatch(line, &connection_p, 2, Matched) > 0) {
      oid_t a1 = atoi(Matched[0]);
      oid_t a2 = atoi(Matched[1]);
      if (agents.find(a1) == agents.end()) {
	printf("Error: connect agent %d undefined\n", a1);
	exit(1);
      }
      if (agents.find(a2) == agents.end()) {
	printf("Error: connect agent %d undefined\n", a2);
	exit(1);
      }
      //between the two agents, the one attached with a traffic should be a1
      //the other should be a2 in this program
      if (agents[a1]->traffic == INVALID) 
	//a1 is without traffic attached
	if (agents[a2]->traffic == INVALID) {
	  //both agents are without traffic attached
	  printf("Error: connect agents %d and %d without traffic source\n",
		 a1, a2);
	  exit(1);
	} else {
	  //a2 is attached with traffic, 
	  //swap a1 and a2 to make a1 the agent with traffic
	  oid_t tmp = a1; 
	  a1 = a2;
	  a2 = tmp;
	}
      connections[((loid_t)a1<<32) + a2] = new ConnectionClass(0);
    } else if (regexmatch(line, &finish_p, 1, Matched) > 0) {
      finish_time = atof(Matched[0]);
      string tmps = line;
      ending_lines.push_back(tmps);
    } else {
      //other lines
      if ((line[0] != '#') && (line[0] != '\0') && 
	  !(line[0] == ' ' && line[1] == '\0')) {
	//neither comment nor blank line, need to store 
	string tmps = line;
	switch (ReadingSegment) {
	case BEGINNING :
	  beginning_lines.push_back(tmps);
	  break;
	case AFTER_NODE :
	  after_node_lines.push_back(tmps);
	  break;
	case AFTER_LINK :
	  after_link_lines.push_back(tmps);
	  break;
	default :
	  ending_lines.push_back(tmps);
	}
      }
    }
    line_count++;
  }

  cout << node_count << " nodes, " 
       << link_count << " links, "
       << agent_count << " agents, "
       << traffic_count << " traffic streams\n";

}

void DetermineNodeRoles () {
  cout << "determining node roles...";
  oid_t router_count = 0, endhost_count = 0, ineffective_count = 0;

  for (nodes_it it = nodes.begin(); it != nodes.end(); it++) {
    oid_t node = it->first;
    if(nodes[node]->nbrs.size() > 1) {
      //this node has more than one neighbor, then it's a router
      nodes[node]->role = ROUTER;
      router_count ++;
      routers[node] = new RouterClass();
    } else {
      //this node has one or less neighbor, then it's an endhost
      if (nodes[node]->agents.size() == 0) {
	//there's no agent attached to this endhost, then it's ineffective
	nodes[node]->role = INEFFECTIVE;
	ineffective_count ++;
      } else {
	nodes[node]->role = ENDHOST;
	endhost_count ++;
      }
    }
  }

  //for every router, store its neighbor routers to save future processing
  for (routers_it it = routers.begin(); it != routers.end(); it++) {
    oid_t r = it->first;
    for (int i = 0; i < nodes[r]->nbrs.size(); i++) {
      oid_t nbr = nodes[r]->nbrs[i];
      if (nodes[nbr]->role == ROUTER) {
	routers[r]->routernbrs.push_back(nbr);
      }
    }
  }
  
  cout << router_count << " routers, "
       << endhost_count << " endhosts, "
       << ineffective_count << " ineffective\n";

}


loid_t GetLinkID(oid_t n1, oid_t n2) {
  loid_t lid;
  lid = ((loid_t)n1<<32) + n2;
  if (links.find(lid) != links.end()) 
    return lid;

  lid = ((loid_t)n2<<32) + n1;
  if (links.find(lid) != links.end()) 
    return lid;
  else 
    return 0;
}

//to determine whether the link between n1 and n2 exists
LinkClass* GetLink(oid_t n1, oid_t n2) {
  loid_t lid;
  lid = ((loid_t)n1<<32) + n2;
  if (links.find(lid) != links.end()) 
    return links[lid];

  lid = ((loid_t)n2<<32) + n1;
  if (links.find(lid) != links.end()) 
    return links[lid];
  else 
    return NULL;
}

//the routers with the consecutive integer id's starting from 0
class TRouterClass {
public:
  oid_t *trouternbrs; // neighbors that are routers
  oid_t nbrs_count;
  oid_t nid;
};


void EstablishRoutes() {
  int i;

  if (ToReadRoutes) {
    cout << "Reading routes from " << RRoutesFileName << endl;
    ifstream routefile(RRoutesFileName.c_str());
    if (routefile.bad()) {
      printf("Error: cannot open routes file %s\n", RRoutesFileName.c_str());
      exit(1);
    }
    char line[MAX_LINE_LEN];
    while (routefile.getline(line, MAX_LINE_LEN)) {
      //folllowing is to get the hops from a line
      vector<oid_t> hops;
      oid_t n;
      char data[20];
      char *ptr1 = line;
      char *ptr2 = strchr(ptr1, '-');
      while (ptr2) {
	int len = ptr2 - ptr1;
	strncpy(data, ptr1, len);
	data[len] = '\0';
	n = atoi(data);
	if (nodes.find(n) == nodes.end()) {
	  printf("Error: node %d in routes not defined by ns script\n", n);
	  exit(1);
	}
	hops.push_back(n);
	ptr1 = ptr2+1;
	ptr2 = strchr(ptr1, '-');
      }; 
      strcpy(data, ptr1); // the last hop
      n = atoi(data);
      if (nodes.find(n) == nodes.end()) {
	printf("Error: node %d in routes not defined by ns script\n", n);
	exit(1);
      }
      hops.push_back(n);

      if(hops.size() < 3) {
	printf("Error: the route %s has less than 3 hops\n", line);
	exit(1);
      }

      loid_t n1 = hops[0];
      loid_t n2 = hops[hops.size()-1];
      int foundconn = 0;
      loid_t cid;
      for (int i = 0; i < nodes[n1]->agents.size(); i++) {
	for (int j = 0; j< nodes[n2]->agents.size(); j++) {
	  cid = ((loid_t)(nodes[n1]->agents[i])<<32) 
	    + nodes[n2]->agents[j];
	  if (connections.find(cid) != connections.end()) {
	    foundconn = 1;
	    if (connections[cid]->PathHops.empty()) {
	      //this path has not been defined
	      for (int i = 1; i < hops.size() - 1; i++) {
		if (!GetLink(hops[i-1], hops[i])) {
		  printf("Error: route link between nodes %d and %d not defined\n",
			 hops[i-1], hops[i]);
		  exit(1);
		};

		connections[cid]->PathHops.push_back(hops[i]);
	      }
      
	      if (!GetLink(hops[hops.size()-1], hops[hops.size()-2])) {
		printf("Error: route link between nodes %d and %d not defined\n",
		       hops[hops.size()-1], hops[hops.size()-2]);
		exit(1);
	      }
	    }
	  }
	}
      }

      if (!foundconn) {
	printf("Error: the ns script defined no conn between nodes %d and %d\n",
	       n1, n2);
	exit(1);
      }

    }
    routefile.close();
  }


  cout << "establishing routes" << endl;

  TRouterClass* trouters = 
    (TRouterClass*)malloc(routers.size() * sizeof(TRouterClass));
  oid_t trouter_count = 0;
  oid_t allnbr_count = 0;
  map<oid_t, int> idn2t;
  for (routers_it it = routers.begin(); it != routers.end(); it++) {
    oid_t r = it->first;
    idn2t[r] = trouter_count;
    trouters[trouter_count].nid = r;
    trouters[trouter_count].nbrs_count = routers[r]->routernbrs.size();
    allnbr_count += trouters[trouter_count].nbrs_count;
    trouter_count++;
  }
  oid_t *allnbrs = 
    (oid_t*)malloc(allnbr_count * sizeof(oid_t));
  oid_t nbrptr = 0;
  for (int i = 0; i < trouter_count; i++) {
    oid_t r = trouters[i].nid;
    trouters[i].trouternbrs = &(allnbrs[nbrptr]);
    nbrptr += trouters[i].nbrs_count;
    for (int j = 0; j < trouters[i].nbrs_count; j++) 
      trouters[i].trouternbrs[j] = idn2t[routers[r]->routernbrs[j]];
  }
  

  //the full queue, enough space for all routers
  oid_t *fq = 
    (oid_t*)malloc(trouter_count * sizeof(oid_t));
  oid_t* parent_of_node =
    (oid_t*)malloc(trouter_count * sizeof(oid_t));
  oid_t* node_processed =
    (oid_t*)malloc(trouter_count * sizeof(oid_t));


  //for each connection, try to establish the route between 2 ends
  for (connections_it it = connections.begin(); it !=connections.end(); it++) {
    if (!it->second->PathHops.empty()) {
      //this connection path defined before, most likely read from file. skip.
      continue;
    }
    oid_t a1 = (oid_t)(it->first>>32);
    oid_t a2 = (oid_t)(it->first&0xFFFFFFFF);
    oid_t n1 = agents[a1]->node;
    oid_t n2 = agents[a2]->node;
    oid_t t1 = agents[a1]->traffic;

    
    if (nodes[n1]->nbrs.empty()) {
      printf("Error: agent %d attached to unconnected node %d\n", a1, n1);
      exit(1);
    }
    if (nodes[n2]->nbrs.empty()) {
      printf("Error: agent %d attached to unconnected node %d\n", a2, n2);
      exit(1);
    }

    oid_t fqhead = 0, fqtail = 0;
    memset(node_processed, '\0', trouter_count * sizeof(oid_t));
     
    oid_t n1r = nodes[n1]->nbrs[0]; //router for endhost n1
    oid_t n2r = nodes[n2]->nbrs[0]; //router for endhost n2
    oid_t tn1r = idn2t[n1r]; 
    oid_t tn2r = idn2t[n2r]; 

    //starting from n1, use breadth-first search to find a route to n2
    int foundpath = 0;
    fq[fqtail++] = tn1r;
    node_processed[tn1r] = 1;
    while(fqhead != fqtail && !foundpath) { 
      //queue not empty and not found
      oid_t curnode = fq[fqhead++];
      
      if (curnode == tn2r) {
	//reached the endhost n2's router
	//this condition is left here for the case where there is only
	//1 router between two endhosts
	foundpath = 1;
      } else {
	for (int i = 0; i < trouters[curnode].nbrs_count; i++) {
	  oid_t nb = trouters[curnode].trouternbrs[i];
	  if (!node_processed[nb]) {
	    //this nb has not been processed, i.e., not in queue yet
	    parent_of_node[nb] = curnode;
	    if (nb == tn2r) {
	      //this neighbor is already the n2's router
	      foundpath = 1;
	      break;
	    } // if (nb == tn2r) {
	    fq[fqtail++] = nb;
	    node_processed[nb] = 1;
	  } // if (!node_processed[nb]) {
	} // for (int i = 0; i < trouters[curnode].nbrs_count; i++) {
      } // else {
    } // while(fqhead != fqtail && !foundpath) { 

    //tracing back from n2's router to n1's router
    if (foundpath) {
      for (oid_t tcurnode = tn2r; tcurnode != tn1r; 
	   tcurnode = parent_of_node[tcurnode]) {
	//push from the front the hops
	oid_t curnode = trouters[tcurnode].nid;
	it->second->PathHops.push_front(curnode);
      }
      it->second->PathHops.push_front(n1r);
    } else {
      printf("Error: no path from agent %d (node %d) to agent %d (node %d)\n",
	     a1, n1, a2, n2);
      exit(1);
    }

  }

  free(fq); // freeing the space of full quque
  free(parent_of_node);
  free(node_processed);
  free(allnbrs);
  free(trouters);
  
  if (ToWriteRoutes) {
    cout << "Writing routes to file " << WRoutesFileName << endl;
    ofstream routefile(WRoutesFileName.c_str());
    if (routefile.bad()) {
      printf("Error: cannot open routes file %s\n", WRoutesFileName.c_str());
      exit(1);
    }
    
    for (connections_it it = connections.begin(); 
	 it !=connections.end(); it++) {
      oid_t a1 = (oid_t)(it->first>>32);
      oid_t a2 = (oid_t)(it->first&0xFFFFFFFF);
      oid_t n1 = agents[a1]->node;
      oid_t n2 = agents[a2]->node;
      
      routefile << n1; 
      for (int i = 0; i < it->second->PathHops.size(); i++) 
	routefile << "-" << it->second->PathHops[i];
      routefile << "-" << n2 << endl;
    }
    routefile.close();
  }
}

void EstimateTraffic () {
  cout << "estimating traffic\n";
  for (connections_it it = connections.begin(); 
       it != connections.end(); it++) {
    oid_t a1 = (oid_t)(it->first>>32);
    oid_t a2 = (oid_t)(it->first&0xFFFFFFFF);
    oid_t n1 = agents[a1]->node;
    oid_t n2 = agents[a2]->node;
    oid_t t1 = agents[a1]->traffic;
    double traffic_period;

    if (traffic[t1]->stop_time > finish_time) 
      traffic_period = finish_time - traffic[t1]->start_time;
    else 
      traffic_period = traffic[t1]->stop_time - traffic[t1]->start_time;

    int size = it->second->PathHops.size();
    LinkClass *link;
    for (int i = 0; i < size - 1; i++) {
      oid_t curnode = it->second->PathHops[i];
      oid_t nb = it->second->PathHops[i+1];
      nodes[curnode]->traffic_volume += (unsigned int)(traffic_period + .5);
      link = GetLink(curnode, nb);
      link->traffic_volume += (unsigned int)(traffic_period + .5);
    }

    nodes[n1]->traffic_volume += (unsigned int)(traffic_period + .5);
    nodes[n2]->traffic_volume += (unsigned int)(traffic_period + .5);
    nodes[it->second->PathHops[size-1]]->traffic_volume += 
      (unsigned int)(traffic_period + .5);

    link = GetLink(n1, it->second->PathHops[0]);
    if (!link) {
      printf("Error: link %d-%d from routes fril not defined in ns script\n",
	     n1, it->second->PathHops[0]);
      exit(1);
    }
    link->traffic_volume += (unsigned int)(traffic_period + .5);

    link = GetLink(n2, it->second->PathHops[size-1]);
    if (!link) {
      printf("Error: link %d-%d from routes fril not defined in ns script\n",
	     n2, it->second->PathHops[size-1]);
      exit(1);
    }
    link->traffic_volume += (unsigned int)(traffic_period + .5);
    
  }
}


unsigned int CalculateNodeWeight(oid_t node, int level) {
  return NODE_SELF_WEIGHT[level] + 
    int(nodes[node]->traffic_volume * NODE_TRAFFIC_WEIGHT[level] + .5);
}

unsigned int CalculateLinkWeight(loid_t link, int level) {
  double delayweight, trafficweight;
  if (links[link]->delay >= LA_THRESHOLD) 
    delayweight = LA_WEIGHT_CONSTANT[level] * LINK_DELAY_WEIGHT[level];
  else
    delayweight = (log(LA_THRESHOLD/links[link]->delay) + 
		   LA_WEIGHT_CONSTANT[level]) * LINK_DELAY_WEIGHT[level];

  trafficweight = (links[link]->traffic_volume + 
		   CT_WEIGHT_CONSTANT[level]) * LINK_TRAFFIC_WEIGHT[level];

  return 
    (unsigned)(LINK_SELF_WEIGHT[level] + delayweight + trafficweight + .5);
}

void CalculateNodeLinkWeights() {
  //to compress the effective endhosts with respectiveadjacent routers
  //and ignore all ineffective endhosts. 
  //i.e., we only partition router topology

  cout << "calculating node & link weights\n";
  for (nodes_it it = nodes.begin(); it != nodes.end(); it++) {
     oid_t node = it->first;
     if (nodes[node]->role == ENDHOST) {
       //this is an effective endhost
       oid_t r = nodes[node]->nbrs[0]; // the adjacent router
       if (routers.find(r) == routers.end()) {
	 //this router not defined before, something wrong!
	 printf("Error: router %d for endhost %d not defined\n", r, node);
	 exit(1);
       } else 
	 for (int level = 0; level < 2; level++)
	   routers[r]->weight[level] +=  CalculateNodeWeight(node, level);
     } else if (nodes[node]->role == ROUTER) {
       for (int level = 0; level < 2; level++)
	 routers[node]->weight[level] += CalculateNodeWeight(node, level);
     }
  }

  for (links_it it = links.begin(); it != links.end(); it++) {
     loid_t link = it->first;
     oid_t n1 = (oid_t)(link >> 32);
     oid_t n2 = (oid_t)(link & 0xFFFFFFFF);
     loid_t reverselink = ((loid_t)n2 << 32) + n1;

     if (nodes[n1]->role == ROUTER && nodes[n2]->role == ROUTER ) {
       //both nodes of the link are routers, then we calculate the link weight
       if (routerlinks.find(link) == routerlinks.end() &&
	   routerlinks.find(reverselink) == routerlinks.end()) {
	 routerlinks[link] = new RouterLinkClass();
	 for (int level = 0; level < 2; level++)
	   routerlinks[link]->weight[level] = CalculateLinkWeight(link, level);
       }
     }
  }

  Whole_Part = new PartitionClass();
  Whole_Part->routers = 
    (oid_t *)malloc(sizeof(oid_t)*routers.size());
  int rcount = 0;
  for (routers_it it = routers.begin(); it != routers.end(); it++) {
    Whole_Part->routers[rcount++] = it->first;
  }
  Whole_Part->rcount = rcount;

  Level1_Parts = 
    (PartitionClass **)malloc(sizeof(PartitionClass)*LEVEL_SIZES[0]);
  Level2_Parts = 
    (PartitionClass ***)malloc(sizeof(PartitionClass*)*LEVEL_SIZES[0]);

  for (int i = 0; i < LEVEL_SIZES[0]; i++) {
    Level1_Parts[i] = new PartitionClass();
    Level2_Parts[i] = 
      (PartitionClass **)malloc(sizeof(PartitionClass)*LEVEL_SIZES[1]);
    for (int j = 0; j < LEVEL_SIZES[1]; j++) 
      Level2_Parts[i][j] = new PartitionClass();
  }
}

void CallMetisToPartition(PartitionClass *opart, PartitionClass **npart, 
			  int level) {
  map<oid_t, oid_t> idm2n; //convert metis node id to ns node id
  map<oid_t, oid_t> idn2m;
  //int router_mcount = 1; //metis start from 1

  cout << "calling metis to partition\n";
  
  for (int i = 0; i < opart->rcount; i++) {
    oid_t r = opart->routers[i];
    //unsigned int rweight = routers[r]->weight[level];
    idm2n[i+1] = r;
    idn2m[r] = i+1;
  }

  string outstr;
  char work[80];
  int lcount = 0;
  
  //for each router, output its weight and the weights for its links
  for (int mid = 1; mid < opart->rcount+1; mid++) {
    oid_t r = idm2n[mid];
    unsigned int rweight = routers[r]->weight[level];
    sprintf(work, "%d", rweight);
    outstr += work;

    for (int i = 0; i < routers[r]->routernbrs.size(); i++) {
      oid_t nbr = routers[r]->routernbrs[i];
      if ( (level == 0) || 
	   ((level == 1) && 
	    (routers[r]->group[0] == routers[nbr]->group[0])) ) {
	//if level 0 then all routers need to be considered
	//if level 1 then only the same group of routers need be considered
	loid_t link = GetLinkID(r, nbr);
	if (!link) {
	  //this router link does not exist
	  printf("Error: %d-%d router link weight not calculated\n", 
		 r, nbr);
	  exit(1);
	} else {
	  lcount ++;
	  sprintf(work, " %d %d", idn2m[nbr], 
		  routerlinks[link]->weight[level]);
	  outstr += work;
	  //outfile << " " << idn2m[nbr] << " " << routerlinks[link]->weight;
	}
      }
    } // for (int i = 0; i < routers[r]->routernbrs.size(); i++) {
    outstr += "\n";
    //outfile << endl;
  }

  //input the header line for the partitioning input
  sprintf(work, "%d %d 11 1\n", opart->rcount, lcount/2);
  outstr = work + outstr;
  //writing to metis graph file
  ofstream outfile("out.graph");
  if (outfile.bad()) {
    printf("Error: cannot write to metis grahp file out.graph\n");
    exit(1);
  }

  outfile << outstr;
  outfile.close();


  // now call the metis program to partition the writen graph

  string METIS;
  char command[80];
  if (LEVEL_SIZES[level] > 8) 
    METIS = "kmetis";
  else
    METIS = "pmetis";
  sprintf(command, "%s out.graph %d",METIS.c_str(), LEVEL_SIZES[level]);
  system(command);


  // now read the partition result

  int *pids = (int*) malloc(sizeof(int) * (opart->rcount+1));

  char ifname[80];
  sprintf(ifname, "out.graph.part.%d", LEVEL_SIZES[level]);
  ifstream infile(ifname);
  if (infile.bad()) {
    printf("Error: cannot read from metis partitioning result file %s\n", 
	   ifname);
    exit(1);
  }

  char line[MAX_LINE_LEN];
  int mid = 1;
  while (infile.getline(line, MAX_LINE_LEN)){
    int pid = atoi(line);
    if (pid >= LEVEL_SIZES[level]) {
      printf("Error: partition results in part id %d >= requested %d\n",
	     pid, LEVEL_SIZES[level]);
      exit(1);
    }
    routers[idm2n[mid]]->group[level] = pid;
    pids[mid] = pid;
    npart[pid]->rcount++;
    mid ++;
  }

  if (mid < opart->rcount) {
    printf("Error: %s has less nodes than original\n", ifname);
    exit(1);
  }

  int *rindex = (int *) malloc(sizeof(int) * LEVEL_SIZES[level]);

  for (int i = 0; i < LEVEL_SIZES[level]; i++) {
    npart[i]->routers = 
      (oid_t *)malloc(sizeof(oid_t) * npart[i]->rcount);
    //npart[i]->rcount ++;
    rindex[i] = 0;
  }

  for (int mid = 1; mid < opart->rcount+1; mid++) {
    int pid = pids[mid];
    npart[pid]->routers[rindex[pid]] = idm2n[mid];
    rindex[pid] ++;
  }


  free(pids);
  free(rindex);
  
}

oid_t GenerateNetAddr(oid_t g0, oid_t g1) {
  oid_t size = Level2_Parts[g0][g1]->rlinks.size() 
    + Level2_Parts[g0][g1]->assignips.size() + 20;
  oid_t netaddr = (g0 << (32 - LEVEL_BIT_LENS[0])) 
    | (g1 << (32 - LEVEL_BIT_LENS[0] - LEVEL_BIT_LENS[1]))
    | (size << 8);
  return netaddr;
}


void SplitNSTopology() {
  //for each router link, check if the two ends of the link are in different
  //partitions. if yes, then mark it as a split link
  cout << "splitting ns topology\n";
  for (routerlinks_it it = routerlinks.begin(); 
       it != routerlinks.end(); it++) {
    loid_t lid = it->first;
    oid_t n1 = (oid_t)(lid >> 32);
    oid_t n2 = (oid_t)(lid & 0xFFFFFFFF);
    oid_t g10 = routers[n1]->group[0];
    oid_t g11 = routers[n1]->group[1];
    oid_t g20 = routers[n2]->group[0];
    oid_t g21 = routers[n2]->group[1];
    if (g10 != g20 || g11 != g21) {
      //the two nodes are in different partitions, then this link is split
      routerlinks[lid]->split = 1;
      oid_t netaddr = GenerateNetAddr(g10, g11);
      Level2_Parts[g10][g11]->rlinks[lid] = netaddr + 1;
      Level2_Parts[g20][g21]->rlinks[lid] = netaddr + 2;
    }
  }

  map<oid_t, oid_t> ports_of_node_count;

  //or each connection between agents, check if the path cross 
  //cross between different partitions. if yes, then construct
  //necessary remote connections.
  for (connections_it it = connections.begin(); it != connections.end();
       it++) {
    loid_t c = it->first;
    oid_t a1 = (oid_t)(c >> 32);
    oid_t a2 = (oid_t)(c & 0xFFFFFFFF);
    oid_t n1 = agents[a1]->node;
    oid_t n2 = agents[a2]->node;
    oid_t n1r = nodes[n1]->nbrs[0];
    oid_t n2r = nodes[n2]->nbrs[0];
    int HasSplit = 0;
    oid_t ip1, ip2;
    oid_t g10, g11, g20, g21;
    g10 = routers[n1r]->group[0];
    g11 = routers[n1r]->group[1];
    g20 = routers[n2r]->group[0];
    g21 = routers[n2r]->group[1];
    
    oid_t fn = n1;
    for (int i = 1; i < it->second->PathHops.size(); i++) {
      oid_t r1 = it->second->PathHops[i-1];
      oid_t r2 = it->second->PathHops[i];
      loid_t lid = GetLinkID(r1, r2);
      if (routerlinks[lid]->split) {
	//this link is a split link
	if (!HasSplit) {
	  //first time coming across a split link.
	  //define assignips for the two end points of this connection
	  //if the end points have not been assigned ip before
	  if (Level2_Parts[g10][g11]->assignips.find(n1) == 
	      Level2_Parts[g10][g11]->assignips.end()) {
	    ip1 = GenerateNetAddr(g10, g11) + 11;
	    Level2_Parts[g10][g11]->assignips[n1] = ip1;
	  } else
	    ip1 = Level2_Parts[g10][g11]->assignips[n1];

	  if (Level2_Parts[g20][g21]->assignips.find(n2) == 
	      Level2_Parts[g20][g21]->assignips.end()) {
	    ip2 = GenerateNetAddr(g20, g21) + 11;
	    Level2_Parts[g20][g21]->assignips[n2] = ip2;
	  } else
	    ip2 = Level2_Parts[g20][g21]->assignips[n2];

	  HasSplit = 1;
	}

	//defining add-routes for this split link
	oid_t gr10 = routers[r1]->group[0];
	oid_t gr11 = routers[r1]->group[1];
	oid_t rlinkip1 = Level2_Parts[gr10][gr11]->rlinks[lid];
	AddRouteClass *ar = new AddRouteClass(r1, rlinkip1, ip2, ip1, fn);
	Level2_Parts[gr10][gr11]->addroutes.push_back(ar);
	fn = r2;
      }
    }

    //trace back the path for reversed direction add-routes
    fn = n2;
    for (int i = it->second->PathHops.size() - 1; i > 0; i--) {
      oid_t r2 = it->second->PathHops[i];
      oid_t r1 = it->second->PathHops[i-1];
      loid_t lid = GetLinkID(r1, r2);
      if (routerlinks[lid]->split) {
	//this link is a split link

	//defining add-routes for this split link
	oid_t gr20 = routers[r2]->group[0];
	oid_t gr21 = routers[r2]->group[1];
	oid_t rlinkip2 = Level2_Parts[gr20][gr21]->rlinks[lid];
	AddRouteClass *arc = new AddRouteClass(r2, rlinkip2, ip1, ip2, fn);
	Level2_Parts[gr20][gr21]->addroutes.push_back(arc);
	fn = r1;
      }
    }

    if (HasSplit) {
      //defining bind ports
      if (ports_of_node_count.find(n1) == ports_of_node_count.end()) 
	ports_of_node_count[n1] = 100;
      if (ports_of_node_count.find(n2) == ports_of_node_count.end()) 
	ports_of_node_count[n2] = 100;

      BindClass *b = new BindClass(n1, a1, ports_of_node_count[n1]);
      Level2_Parts[g10][g11]->binds.push_back(b);
      b = new BindClass(n2, a2, ports_of_node_count[n2]);
      Level2_Parts[g20][g21]->binds.push_back(b);

      //defining ipconnects
      IPConnectClass *ipc 
	= new IPConnectClass(a1, ip2, ports_of_node_count[n2]);
      Level2_Parts[g10][g11]->ipconnects.push_back(ipc);
      ipc  = new IPConnectClass(a2, ip1, ports_of_node_count[n1]);
      Level2_Parts[g20][g21]->ipconnects.push_back(ipc);
      
      ports_of_node_count[n1]++;
      ports_of_node_count[n2]++;
    } else {
      Level2_Parts[g10][g11]->connects.push_back(c);
    }
  }

}

void GetIPStr(oid_t ip, char ipstr[]) {
  sprintf(ipstr, "%d.%d.%d.%d", 
	  ip>>24, (ip>>16) & 0xFF, (ip>>8) & 0xFF, ip & 0xFF);
}


void WriteAPDNSScript(char*fname, oid_t g0, oid_t g1) {
  char work[40];
  char origname[40];
  char *tp = strstr(fname, ".tcl");
  strncpy(origname, fname, tp - fname);
  origname[tp-fname] = 0;
  sprintf(work, "%s_%d_%d.tcl", origname, g0, g1);
  FILE *F = fopen(work, "w");

  for (int i = 0; i < beginning_lines.size(); i++) {
    fprintf(F, "%s\n", beginning_lines[i].c_str());
  }
  fprintf(F, "$ns use-scheduler RTI\n");

  fprintf(F, "\n");
  
  PartitionClass *part = Level2_Parts[g0][g1];

  //writing nodes
  for (int i = 0; i < part->rcount; i++) {
    oid_t r = part->routers[i];
    fprintf(F, "set node(%d) [$ns node]\n", r);

    //also write all end host neghbors that are effective
    for (int j = 0; j < nodes[r]->nbrs.size(); j++) {
      oid_t nb = nodes[r]->nbrs[j];
      if (nodes[nb]->role == ENDHOST) {
	fprintf(F, "set node(%d) [$ns node]\n", nb);
      }
    }
  }


  for (int i = 0; i < after_node_lines.size(); i++) {
    fprintf(F, "%s\n", after_node_lines[i].c_str());
  }

  fprintf(F, "\n");

  //writing links
  for (int i = 0; i < part->rcount; i++) {
    oid_t r = part->routers[i];
    for (int j = 0; j < nodes[r]->nbrs.size(); j++) {
      oid_t nb = nodes[r]->nbrs[j];
      loid_t l = ((loid_t)r << 32) + nb;
      if (nodes[nb]->role == ENDHOST ||
	  nodes[nb]->role == ROUTER && 
	  routerlinks.find(l) != routerlinks.end() &&
	  routers[nb]->group[0] == routers[r]->group[0] &&
	  routers[nb]->group[1] == routers[r]->group[1])  {
	//if the neighbr is an end host, then go ahead write this link
	//if the nbr is a router, and it is in the same partition as r,
	//then we write the originally defined link
	loid_t lid = GetLinkID(r, nb);
	fprintf(F, "$ns duplex-link $node(%d) $node(%d) %0.0lf %lf %s\n", 
		r, nb, 
		links[lid]->bandwidth, links[lid]->delay, 
		links[lid]->get_qtype());
      }
    }
  }

  for (int i = 0; i < after_link_lines.size(); i++) {
    fprintf(F, "%s\n", after_link_lines[i].c_str());
  }

  fprintf(F, "\n");

  //writing agents, connections within the same partition
  for (int i = 0; i < part->rcount; i++) {
    oid_t r = part->routers[i];
    for (int j = 0; j < nodes[r]->nbrs.size(); j++) {
      oid_t nb = nodes[r]->nbrs[j];
      if (nodes[nb]->role == ENDHOST) {
	//the end hosts belogning to this partition
	for (int k = 0; k < nodes[nb]->agents.size(); k++) {
	  oid_t a = nodes[nb]->agents[k];
	  fprintf(F, "set agent(%d) [new Agent/%s]\n", 
		  a, agents[a]->get_type());
	  fprintf(F, "$ns attach-agent $node(%d) $agent(%d)\n", nb, a);
	  if (agents[a]->traffic != INVALID) {
	    //this agent is a traffic source
	    oid_t tr = agents[a]->traffic;
	    fprintf(F, "set traffic_source(%d) [new Application/%s]\n", 
		    tr, traffic[tr]->get_type());
	    fprintf(F, "$traffic_source(%d) attach-agent $agent(%d)\n", 
		    tr, a);
	    fprintf(F, "$ns at %lf \"$traffic_source(%d) start\"\n",
		    traffic[tr]->start_time, tr);
	    fprintf(F, "$ns at %lf \"$traffic_source(%d) stop\"\n",
		    traffic[tr]->stop_time, tr);

	  }
	  fprintf(F, "\n");
	}
      }
    }
  }

  fprintf(F, "\n");

  char ipstr[16];

  //writing the local connects
  for (int i = 0; i < part->connects.size(); i++) {
    loid_t c = part->connects[i];
    oid_t a1 = (oid_t)(c >> 32);
    oid_t a2 = (oid_t)(c & 0xFFFFFFFF);
    fprintf(F, "$ns connect $agent(%d) $agent(%d)\n", a1, a2);
  }

  fprintf(F, "\n");

  //writing set-ipaddrs 
  for (assignips_it it = part->assignips.begin(); 
       it != part->assignips.end(); it++) {
    oid_t n = it->first;
    oid_t ip = it->second;
    oid_t r = nodes[n]->nbrs[0];
    GetIPStr(ip, ipstr);
    fprintf(F, "[$ns link $node(%d) $node(%d)] set-ipaddr %s 255.255.255.0\n",
	    n, r, ipstr);
    GetIPStr(ip+1, ipstr);
    fprintf(F, "[$ns link $node(%d) $node(%d)] set-ipaddr %s 255.255.255.0\n",
	    r, n, ipstr);
  }

  fprintf(F, "\n");

  //writing rlinks
  for (rlinks_it it = part->rlinks.begin(); it != part->rlinks.end(); it++) {
    loid_t lid = it->first;
    oid_t ip = it->second;
    oid_t n1 = (oid_t)(lid >> 32);
    oid_t n2 = (oid_t)(lid & 0xFFFFFFFF);
    oid_t n;
    if (routers[n1]->group[0] == g0 && routers[n1]->group[1] == g1) 
      //n1 is the router node in this partition
      n = n1;
    else if (routers[n2]->group[0] == g0 && routers[n2]->group[1] == g1) 
      // n2 is the node
      n = n2;
    else {
      printf("Error: rlink between nodes %d and %d not in any partition\n",
	     n1, n2);
      exit(1);
    }

    GetIPStr(ip, ipstr);
    fprintf(F, "$node(%d) rlink %0.0lf %lf %s %s 255.255.255.0\n",
	    n, links[lid]->bandwidth, links[lid]->delay, 
	    links[lid]->get_qtype(), ipstr);
  }
       
  fprintf(F, "\n");

  //writing add-routes
  for (int i = 0; i < part->addroutes.size(); i++) {
    AddRouteClass *ar = part->addroutes[i];
    char ipstr1[16], ipstr2[16];
    GetIPStr(ar->rlinkip, ipstr);
    GetIPStr(ar->ip1, ipstr1);
    GetIPStr(ar->ip2, ipstr2);
    fprintf(F, "$ns add-route $node(%d) %s %s %s %s %s $node(%d)\n",
	    ar->router, ipstr, 
	    ipstr2, "255.255.255.0", 
	    ipstr1, "255.255.255.0", 
	    ar->fnode);
  }

  fprintf(F, "\n");

  //writing binds
  for (int i = 0; i < part->binds.size(); i++) {
    BindClass *b = part->binds[i];
    fprintf(F, "$node(%d) bind $agent(%d) %d\n",
	    b->node, b->agent, b->port);
  }

  fprintf(F, "\n");

  //writing ip-connects
  for (int i = 0; i < part->ipconnects.size(); i++) {
    IPConnectClass *ipc = part->ipconnects[i];
    GetIPStr(ipc->ip, ipstr);
    fprintf(F, "$ns ip-connect $agent(%d) %s %d\n",
	    ipc->agent, ipstr, ipc->port);
  }


  for (int i = 0; i < ending_lines.size(); i++) {
    fprintf(F, "%s\n", ending_lines[i].c_str());
  }

  fclose(F);
}


int main(int argc, char *argv[]) {
  char is[80];

  int opt_count = GetOpts(argc, argv, "n:W:R:", LEVEL_SIZES);

  if (opt_count+1 >= argc) {
    cerr << "Error: no input ns script specified\n";
    exit(1);
  }

  ReadNSScript(argv[opt_count+1]);

  DetermineNodeRoles();
  EstablishRoutes();
  EstimateTraffic();
  CalculateNodeLinkWeights();

  if (LEVEL_SIZES[0] > 1)
    CallMetisToPartition(Whole_Part, Level1_Parts, 0);
  else 
    Level1_Parts[0] = Whole_Part;

  for (int i = 0; i < LEVEL_SIZES[0]; i++)
    if (LEVEL_SIZES[1] > 1)
      CallMetisToPartition(Level1_Parts[i], Level2_Parts[i], 1);
    else 
      Level2_Parts[i][0] = Level1_Parts[i];

  SplitNSTopology();

  cout << "writing pdns scripts\n";
  for (int i = 0; i < LEVEL_SIZES[0]; i++) 
    for (int j = 0; j < LEVEL_SIZES[1]; j++) 
      WriteAPDNSScript(argv[opt_count+1], i, j);

  //cout << "Press Enter to quit: ";
  //cin.getline(is,80);
}