(@ #define INFINITY (1e100) @)

// build a routing table from the ring.

*operation* RoutingTable* build_routing_table(Ring* ring)
*init* (@ new RoutingTable(new DagDest_List()) @)
*traverse*
  *from* Commodity_List
  *through* -> *, sources, *
  *to* VNodeTraff
*carry* *inout* Dag* dag,
        *inout* VNode* dest_vnode
*along*
  *from* Commodity_List
  *through* -> *, sources, *
  *to* VNodeTraff
*wrapper* ~> Commodity_List, Commodity
  *suffix*
  (@
     DagDest* dagdest = new DagDest(dag, dest_vnode);
     return_val->get_dags()->append(dagdest);
   @)
*wrapper* Commodity
  (@
     dest_vnode = get_dest();
     dag = new Dag(new DagAdjacency_List());
     VNode* vnode = this->furthest_source(ring);
     VirtualAdjacency* adj = ring->find(vnode);
     DagAdjacency* dagadj;
     DagNeighbor* dagneighbor;
     do {
       dagadj = new DagAdjacency(this->get_traffic(vnode), 
                                 new DemReal(0.0),
                                 vnode, 
                                 new DagNeighbor_List());
       adj->add_dag_neighbors(dagadj, dest_vnode, ring);
       dag->get_start()->append(dagadj);
       adj = ring->get_nextdefault(adj);
       vnode = adj->get_source();
     }while (vnode != dest_vnode);
     
     // now vnode is the dest_vnode, and adj is the coresponding adjacency
     // we want to add the destination to the dag as well, with 
     // traffic = 0, proximity = INFINITY, no neighbors
     dagadj = new DagAdjacency(new DemReal(0.0), 
                               new DemReal(INFINITY),
                               vnode, 
                               new DagNeighbor_List());
     dag->get_start()->append(dagadj);
   @)



// return the traffic of "vnode" to the corresponding commodity
// destination.

*operation* DemReal* get_traffic(VNode* vnode)
*init* (@ new DemReal(0.0) @)
*traverse* 
  *from* Commodity
  *through* -> *, sources, *
  *to* VNodeTraff
*wrapper* VNodeTraff
  (@
     if (get_source() == vnode)
       *return_val = *(this->get_traffic());
   @)


// add to the DAG adjacency "dagadj" the neighbors of the current
// virtual adjacency for destination "dest_vnode".

*operation* void add_dag_neighbors(DagAdjacency* dagadj, VNode* dest_vnode, Ring* ring)
*traverse*
  *from* VirtualAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode
*carry* *in* int shortcut = (@ 0 @)
*along*
  *from* VirtualAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode  
*wrapper* -> *, shortcuts, *
  (@
     shortcut = 1;
  @)
*wrapper* -> *, jumps, *
  (@
     shortcut = 0;
   @)
*wrapper* VirtualAdjacency
  *suffix*
  (@
     VNode* next_vnode = ring->get_nextdefault(this)->get_source();
     DagNeighbor* dag_neighbor = new DagNeighbor(next_vnode, 
                                                 new DemReal(0.0), 
                                                 new DemReal(0.0),
					         new DemNumber(0)); 
     dagadj->get_neighbors()->append(dag_neighbor);
   @)
*wrapper* VNode
  (@
     if (ring->in_ring_order(dagadj->get_source(), this, dest_vnode)) {
       DagNeighbor* dag_neighbor = new DagNeighbor(this, 
						   new DemReal(0.0), 
						   new DemReal(0.0),
						   new DemNumber(shortcut));
       dagadj->get_neighbors()->append(dag_neighbor);
   }
   @)


*operation* void print_routing_table()
*traverse*
  *from* RoutingTable
  *to* DagDest
*wrapper* DagDest
  (@
     cout << "Destination: " << get_dest()->get_vid() << endl;
     cout << "----------------\n";
     get_dag()->print_dag();
   @)

*operation* void print_dag()
*traverse*
  *from* Dag
  *to-stop* DagNeighbor
*wrapper* DagAdjacency
  (@
     cout << "Virtual Node: " << get_source()->get_vid() << endl;
     cout << "   Traffic = " << get_traffic() << endl;
     cout << "   Proximity = " << get_proximity() << endl;
   @)
*wrapper* DagNeighbor
  (@
     cout << "   --> " << get_neighbor()->get_vid() 
                       << " prob = " << get_prob()
                       << " flow = " << get_flow() << endl;
  @)


// find the virtual node which is the furthest possible source
// in the ring, with respect to the found commodities.

*operation* VNode* furthest_source(Ring* ring)
*init* (@ NULL @)
*traverse* 
  *from* Commodity
  *through* -> *, sources, *
  *to-stop* VNode
*carry* *in* VNode* dest_vnode = (@ get_dest() @)
*along*
  *from* Commodity
  *through* -> *, sources, *
  *to-stop* VNode  
*carry* *inout* int max_dist = (@ 0 @)
*along*
  *from* VNodeTraff_List
  *through* -> *, source, *
  *to-stop* VNode
*wrapper* VNode
  (@
     int dist = ring->distance(this, dest_vnode);
     if (dist > max_dist) {
       return_val = this;
       max_dist = dist;
     }
   @)