
 // -*- C++ -*-


 namespace KNIK {

 /*! \class        Graph
  *  \brief        The routing graph.\n
  *                - \ref GraphAttributes   "Attributes"
  *                - \ref GraphConstructors "Constructors"
  *                - \ref GraphAccessors    "Accessors"
  *                - \ref GraphModifiers    "Modifiers"  
  *                - \ref GraphTupleQueue   "Tuple Priority Queue Methods"
  *
  *  \section      secGraphImplementation  Graph Implementation
  *                CEngine : Nimbus.
  *
  *  \section      secGraphUseful  Useful defines
  *                
  *  \define       EPSILON 10e-4
  *  \defineD      EPSILON is used two avoid several float roudness problems
  *  \defineEND
  *
  *  \anchor       GRAPH_FLUTELIMIT
  *  \define       FLUTE_LIMIT 150
  *  \defineD      When using congestion, <a href="http://class.ee.iastate.edu/cnchu/flute.html">FLUTE</a> algorithm will not work properly if number
  *                of pins exceed a limit : MAXD.\n
  *                Knik algorithm must not pass net with more than FLUTE_LIMIT pins to FLUTE.\n
  *                \n
  *                Flute.h:
  *  \code         #define MAXD 150   // Setting MAXD to more than 150 is not recommended
  *  \endcode
  *  \defineEND
  *
  *  \define      __USE_SLICINGTREE__
  *  \defineD     if defined, the search of a vertex givenits position will be done using a slicingtree instead of using nimbus methods.\n
  *               Using the slicing tree really faster
  *  \defineEND
  */

 /*! \anchor       GraphAttributes Attributes
  *  \name
  */
 // \{
 /*! \var          Nimbus* Graph::_nimbus
  *                The corresponding partitionning
  *
  *  \Initial      by constructor
  */

 /*! \var          SlicingTree* Graph::_slicingTree;
  *                The slicing tree, useful for searching a vertex given its position
  *
  *  \Initial      \NULL
  */

 /*! \var          Net* Graph::_working_net;
  *                The curret working net, all algorithms in Graph will refer to this net
  *
  *  \Initial      \NULL
  */

 /*! \var          VertexSet Graph::_vertexes_to_route;
  *                The set of vertexes to route, given a working net to route we can create this set
  *
  *  \Initial      empty
  *  \see          Graph::InitRouting
  */

 /*! \var          Vertex* Graph::_lowerLeftVertex;
  *                The lower left vertex of the graph, useful to skim through the graph
  */

 /*! \var          VertexVector Graph::_all_vertexes;
  *                The vector of all the vertexes
  */

 /*! \var          EdgeVector Graph::_all_edges;
  *                The vector of all the edges
  */

 /*! \var          TuplePriorityQueue Graph::_tuplePriorityQueue;
  *                The tuple priority queue for Dijkstra's algorithm implementation
  */

 /*! \var          Box Graph::_searchingArea;
  *                The _searchingArea limits the Dijkstra's algorithm toa certain range
  */

 /*! \var          unsigned Graph::_netStamp
  *                The net stamp associated with the working net
  *
  *  \Initial      \p 0
  *  \see          \ref grpNetStamp
  */
 // \}

 /*! \anchor       GraphConstructors Constructors
  *  \name
  */
 // \{
 /*! \function     static Graph* Graph::Create ( Nimbus* nimbus, RoutingGrid* routingGrid, bool benchMode, bool useSegments );
  *  \param        nimbus the partionning needed to create the routing graph
  *  \param        routingGrid the routingGrid, may be \NULL 
  *  \param        benchMode for ispd global routing benchmarks
  *  \param        useSegments defines if routing is done with segments or splitters
  *  \return       the newly created graph
  */
 // \}
 
 /*! \anchor       GraphAccessors Accessors
  *  \name
  */
 // \{

 /*! \function     Hurricane::Cell* Graph::GetCell();
  *  \Return       the current top cell
  */

 /*! \function     unsigned Graph::GetNetStamp();
  *  \Return       the net stamp of the current working net
  */

 /*! \function     Vertex* Graph::GetPredecessor ( const Vertex* vertex )
  *  \param        vertex is the vertex from which we want to get the predecessor
  *  \return       the predecessor vertex
  */

 /*! \function     Vertex* Graph::GetCentralVertex ();
  *  \Return       the most central vertex of Graph::_vertexes_to_route
  */

 /*! \function     Vertex* Graph::GetVertex ( Point p );
  *  \param        p a position
  *  \return       the vertex which corresponds to the position
  */

 /*! \function     Vertex* Graph::GetVertex ( Unit x, Unit y );
  *  \param        x is the x coordinate of the position
  *  \param        y is the y coordinate of the position
  *  \return       the vertex which corresponds to the position
  */

 // \}

 /*! \anchor       GraphModifiers Modifiers
  *  \name
  */
 // \{

 /*! \function     void Graph::CreateHEdge ( Vertex* from, Vertex* to, Fence* fence, DisplaySlot* displaySlot );
  *  \param        from        the source vertex
  *  \param        to          the target vertex
  *  \param        fence       the corresponding fence
  *  \param        displaySlot the GTK displaytSlot for edges' graphical display
  */

 /*! \function     void Graph::CreateVEdge ( Vertex* from, Vertex* to, Fence* fence, DisplaySlot* displaySlot );
  *  \param        from        the source vertex
  *  \param        to          the target vertex
  *  \param        fence       the corresponding fence
  *  \param        displaySlot the GTK displaytSlot for edges' graphical display
  */

 /*! \function     void Graph::InitConnexComp ( Vertex* vertex, int newConnexID = -1 );
  *                This function initialize a connex component as the source on for Dijkstra's algorithm implementation, the connex component
  *                is considered based on the connexID of given vertex.\n
  *                The connexID of the connex component may be changed by specifiing it as argument, if not the connexID will not be changed.
  *  \param        vertex      one vertex of the connex component
  *  \param        newConnexID the new connexID for the connex component (optional)
  *  \see          \ref grpConnexID, \ref grpConnexComponent
  */

 /*! \function     void Graph::InitConnexComp ( Vertex* vertex, Edge* arrivalEdge, int newConnexID );
  *                This is the recusive part of Graph::InitConnexComp
  *  \param        vertex      one vertex of the connex component
  *  \param        arrivalEdge the edge that leads to the current vertex (in order not to skim through it again)
  *  \param        newConnexID the new connexID for the connex component
  *  \see          \ref grpConnexID, \ref grpConnexComponent
  */

 /*! \function     void Graph::UpdateConnexComp ( VertexList reachedVertexes, Vertex* firstVertex );
  *                This function create the new connex component from a reached vertex to the first source vertex thanks to the path
  *                found by global routing.
  *  \param        reachedVertexes is the list of reachedVertexes (see <b>Bug</b>)
  *  \param        firstVertex     is the source vertex
  *  \see          \ref grpConnexID, \ref grpConnexComponent
  *  \bug          The parameter VertexList reachedVertexes should be a simple Vertex* reachedVertex !
  */

 /*! \function     void Graph::MaterializeRouting ( Vertex* vertex );
  *                This function materializes the routing of a net. Global routing algorithms have routed the net so there is only one connex
  *                component. Starting with one vertex of the connex component and using connexID, it's easy to skim through all the connex
  *                component.
  *  \param        vertex is a representant of the connex component to materialize
  */

 /*! \function     void Graph::MaterializeRouting ( Vertex* vertex, Edge* arrivalEdge, Contact* initialContact );
  *                This recursive function starts from a \e vertex and skim through all its edges (except the \e arrivalEdge) to check the ConnexID
  *                and materialize routing between 2 vertexes if the ConnexID match.
  *
  *                <b>\n What does "MaterializeRouting" means:</b>
  *
  *                The result of the global routing algorithms (Monotonic or Dijkstra) is a connex composant which is respresented by a set of
  *                vertexes and edges that have the same ConnexID.
  *
  *                Each edge of the connex component represents a crossing of the corresponding fence. Thus for the _working_net a Splitter is
  *                created and attached to the LocalRingHook of each vertex of the edge.
  *
  *                <b>\n Overview:</b>
  *
  *  \code
  * for each edge of vertex:
  *     // if edge and vertex have the same connexID
  *     if Vertex::GetConnexID equals Edge::GetConnexID :
  *         // creates the splitter (if not exist)
  *         edge-> Edge::CreateSplitter ( _working_net );
  *         // get the hook of the splitter corresponding to the vertex
  *         hook = edge-> Edge::GetSplitterHook ( vertex );
  *         // if the vertex has a LocalRingHook set
  *         if previousHook = Vertex::GetLocalRingHook exists:
  *             // attaches the 2 hooks
  *             hook->Attach ( previousHook );
  *         // sets the _localRingHook of the vertex
  *         Vertex::SetLocalRingHook ( hook );
  *         
  *         if edge is not arrivalEdge:
  *             // recursive call
  *             MaterializeRouting ( edge-> Edge::GetOpposite ( vertex ), edge );
  *  \endcode
  *  \param        vertex      starting vertex
  *  \param        arrivalEdge the edge that leaded to the starting vertex
  *  \param        initialContact optional
  *  \see          \ref grpConnexID
  */

 /*! \function     void Graph::ResetVertexes ();
  *                This function clears the Graph::_vertexes_to_route set.
  */

 /*! \function     void Graph::SetNetStamp ( unsigned netStamp );
  *  \param        netStamp is the netStamp corresponding to the Graph::_working_net
  *  \see          \ref grpNetStamp
  */

 /*! \function     void Graph::IncNetStamp ();
  *                Increments GRaph::_netStamp by 1.
  *  \see          \ref grpNetStamp
  */

 /*! \function     int Graph::CountVertexes ( Net* net );
  *                This function count the number of connex components that have to be routed for the given net.
  *
  *                It is very similar to the Graph::InitRouting function but is simpler since it just have to count and not initialize the routing
  *                graph.
  *  \param        net is the Graph::_working_net
  *  \return       the number of connex components
  */

 /*! \function     int Graph::InitRouting ( Net* net );
  *                This function prepares everything needed to properly global route a given net on the routing graph. It creates all the connex
  *                components (with connexID) and fills the _vertexes_to_route set which represents all the connex components that have to be routed.
  *                The set contains only one unique representant vertex for each connex components.
  *  \param        net the new Graph::_working_net
  *  \return       _vertexes_to_route.size()
  *
  *  \overview
  *  \code
  * _working_net = net;
  * // first sets the new _working_net
  *
  * currentConnexID = 0;
  * // initializes the connexID for the first connex component
  *
  * for each component in net->GetComponents()
  *     if the component is a routingPad
  *         vertex = Graph::GetVertex ( component->GetCenter() );
  *
  *         if vertex not in _vertexes_to_route
  *             _vertexes_to_route.Insert ( vertex );
  *             _searchingArea.Merge ( area of Vertex::_gcell );
  *             Vertex::SetConnexID ( currentConnexID );
  *             Vertex::SetNetStamp ( _netStamp );
  *             currentConnexID++;
  *
  *         Vertex::AttachToLocalRing ( component );
  *
  *         for each other_vertex that component would cover
  *             _searchingArea.Merge ( area of Vertex::_gcell );
  *             Vertex::SetConnexID ( currentConnexID - 1 );
  *             Vertex::SetNetStamp ( _netStamp );
  *             Vertex::LinkToVertex ( vertex );
  *  \endcode
  *  \exception    assert that the parameter \e net does exist
  *  \bug          the <em>for each other vertex that component would cover</em> part is not implemented right now !
  *  \see          \ref grpConnexID
  */

 /*! \function     void Graph::Dijkstra ();
  *                This is the implementation of Dijkstra's algorithm.
  */

 /*! \function     void Graph::Monotonic ();
  *                This is the implementation of Monotonic routing.
  *
  *                \b Definition:
  *
  *                The Monotonic routing is a very simple algorithm that found the shortest path between a single source and a single target
  *                whithin the bouding box of S and T. The idea is that the path always directs towards T, it implies a very important property
  *                of monotonic routing : each vertex within the bounding box has only one or two vertexes that can be its predecessor.
  *
  *                Thus it is easy to understand how the distance will be propagated from S to T in order to find the shortest path.
  *
  *                In order not to treat too many cases, the algorithm orders source and target vertexes so that the source is the leftest vertex
  *                (or most bottom if same x coordinate).
  *
  *  \overview
  *  \code
  * // first gets the source and target vertexes
  * source = (*_vertexes_to_route.begin());  // gets the first element of the set
  * target = (*_vertexes_to_route.rbegin()); // gets the last (second) element of the set
  *
  * // then their x and y coordinates
  * sourceX, sourceY, targetX and targetY with Vertex::GetPosition
  *
  * // the source vertex will be the bottom-leftest one :
  * if sourceX is greater than targetX:
  *     exchange source with target
  * else if sourceX equals targetX:
  *     if sourceY is greater than target Y:
  *         exchange source with target
  *
  * // now source and target vertex have been ordered, reinitializes x and y coordinates
  * sourceX, sourceY, targetX and targetY with Vertex::GetPosition
  * 
  * // sets the source vertex distance to 0
  * source-> Vertex::SetDistance (0);
  *
  * // find the shortest path from source
  * FindShortestPath(); 
  * 
  * // creates the new connex component 
  * while currentVertex has a predecessor:
  *     // set connexID
  *     currentVertex-> Vertex::SetConnexID ( sourceID );
  *     predecessor-> Edge::SetConnexID ( sourceID );
  *     // get next vertex
  *     currentVertex = predecessor-> Edge::GetOpposite ( currentVertex );
  *
  * // now materializes the routing
  * Graph::MaterializeRouting ( source );
  *
  * // since the net is now routed, substracts its contribution to estimated congestion
  * #if defined ( __USE_DYNAMIC_PRECONGESTION__ )
  *     Graph::UpdateEstimateCongestion();
  * #endif
  * \endcode
  *
  *                <b>\n How to find the shortest path:</b>
  *
  *                There are 2 cases to consider :
  *
  *                - 1st case:
  *                \image html  MonotonicRouting1.png "Monotonic routing first case"
  *                \image latex MonotonicRouting1.pdf "Monotonic routing first case" width=0.7\textwidth
  *
  * \code
  * if sourceY is lesser than or equal to targetY:
  *     // propagates distance for all vertexes which y coordinate is sourceY and x coordinate is lesser than or equal to targetX           (1)
  *     // propagates distance for all vertexes which x corrdinate is sourceX and y coordinate is greater than or equal to targetY          (2)
  *     // propagates distance for all other vertexes by column order                                                                            
  * \endcode
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  MonotonicRouting1-1.png "(1)"
  *                      \image latex MonotonicRouting1-1.png "(1)" width=0.5\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  MonotonicRouting1-2.png "(2)"
  *                      \image latex MonotonicRouting1-2.png "(2)" width=0.5\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                When all the distances of all vertexes have been set, it's easy to find the shortest path following the predecessor from target
  *                to source vertex.
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  MonotonicRouting1-3.png "Example of monotonic shortest path"
  *                      \image latex MonotonicRouting1-3.png "Example of monotonic shortest path" width=0.5\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  MonotonicRouting1-4.png "Monotonic default shortest path (when all edge costs are equal)"
  *                      \image latex MonotonicRouting1-4.png "Monotonic default shortest path (when all edge costs are equal)" width=0.5\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                - 2nd case:
  *                \image html  MonotonicRouting2.png "Monotonic routing second case"
  *                \image latex MonotonicRouting2.pdf "Monotonic routing second case" width=0.7\textwidth
  *
  * \code
  * if sourceY is greater than targetY:
  *     // propagates distance for all vertexes which y coordinate is sourceY and x coordinate is lesser than or equal to targetX           (1)
  *     // propagates distance for all vertexes which x corrdinate is sourceX and y coordinate is lesser than or equal to targetY           (2)
  *     // propagates distance for all other vertexes by column order                                                                            
  * \endcode
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  MonotonicRouting2-1.png "(1)"
  *                      \image latex MonotonicRouting2-1.png "(1)" width=0.5\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  MonotonicRouting2-2.png "(2)"
  *                      \image latex MonotonicRouting2-2.png "(2)" width=0.5\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                When all the distances of all vertexes have been set, it's easy to find the shortest path following the predecessor from target
  *                to source vertex.
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  MonotonicRouting2-3.png "Example of monotonic shortest path"
  *                      \image latex MonotonicRouting2-3.png "Example of monotonic shortest path" width=0.5\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  MonotonicRouting2-4.png "Monotonic default shortest path (when all edge costs are equal)"
  *                      \image latex MonotonicRouting2-4.png "Monotonic default shortest path (when all edge costs are equal)" width=0.5\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *  \exception    assert that Graph::_vertexes_to_route set size is equal to 2
  *  \exception    assert that the 2 vertexes present in Graph::_vertexes_to_route set are different
  *  \bug          For the moment Monotonic routing works only with a regular routing graph !
  */

 /*! \function     FTree Graph::CreateFluteTree ();
  *  \Return       the newly created FLUTE Tree
  */

 /*! \function     void Graph::CleanRoutingState ();
  *                This function cleans everything left by Monotonic, Dijkstra and MaterializeRouting functions
  */

 /*! \function     void Graph::UpdateEstimateCongestion ( bool create = false );
  *                This function manages the estimated congestion. It can either create or update it depending on the value of the \e create parameter.
  *
  *                <b>\n How to compute estimated congestion:</b>
  *
  *                The idea is that for each net a rectilinear Steiner minimal tree will be constructed and estimations will be done based on this
  *                Steiner tree. The important point is that when updating estimated congestion, we must be able to reconstruct the same Steiner tree.
  *                Thus the algorithm that creates the Steiner tree have to be determinist, it is also a good point if it is fast because the algorithm
  *                may be called many times.
  *
  *                Such an algorithm exists in FLUTE
  *                (<a href='http://class.ee.iastate.edu/cnchu/flute.html'>http://class.ee.iastate.edu/cnchu/flute.hml</a>).
  *
  *                Based on the Graph::_vertexes_to_route set, the Graph::CreateFluteTree function creates and returns the Steiner tree.
  *
  *                Let's consider a simple example to illustrates what FLUTE does :
  *                \image html  Steiner1.png "A simple example of a net with 4 pins"
  *                \image latex Steiner1.pdf "A simple example of a net with 4 pins" width=0.7\textwidth
  *
  *                To works, FLUTE needs the x and y coordinates of each pin (vertex), just like :
  *  \code
  * // FLUTE Input
  * 100 400
  * 200 100
  * 200 400
  * 300 200
  *  \endcode
  *
  *                And then FLUTE will return a Steiner tree. The Steiner tree is described based on its branches :
  *  \code
  * // FLUTE Output
  * 200 100
  * 200 200
  *
  * 300 200
  * 200 200
  *
  * 100 400
  * 200 400
  *
  * 200 200
  * 200 400
  *  \endcode
  *                \image html  Steiner2.png "Representation of the resulting Steiner tree with intermediate Steiner node"
  *                \image latex Steiner2.pdf "Representation of the resulting Steiner tree with intermediate Steiner node" width=0.7\textwidth
  *
  *                \n As said before, FLUTE creates a rectilinear Steiner minimal tree, but it is important to understand that when several rectilinear
  *                Steiner minimal sub-trees of the same length exist, FLUTE returns the different possibilities :
  *                <CENTER>
  *                <TABLE width=100% border=0>
  *                  <TR>
  *                    <TD width=70%>
  *                      \image html  Steiner3.png "A net with 4 pins"
  *                      \image latex Steiner3.pdf "A net with 4 pins" width=0.7\textwidth
  *                    </TD>
  *                    <TD width=30%>
  *  \code
  * // FLUTE Input
  * 100 100
  * 200 200
  * 400 200
  * 500 400
  *  \endcode
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                <TABLE width=100% border=0>
  *                  <TR>
  *                    <TD width=35%>
  *                      \image html  Steiner4.png "All rectilinear Steiner minimal trees"
  *                      \image latex Steiner4.pdf "All rectilinear Steiner minimal trees" width=0.7\textwidth
  *                    </TD>
  *                    <TD width=35%>
  *                      \image html  Steiner5.png "Representation of FLUTE result"
  *                      \image latex Steiner5.pdf "Representation of FLUTE result" width=0.7\textwidth
  *                    </TD>
  *                    <TD width=30%>
  *  \code
  * // FLUTE Output
  * 100 100
  * 200 200
  *
  * 500 400
  * 400 200
  *
  * 200 200
  * 400 200
  *  \endcode
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                \n Since we exactly know what FLUTE returns, we can now define how estimated congestion is computed. FLUTE returns a set of branches.
  *                Each branch is represented by 2 vertexes and the estimate congestion depends on 2 cases :
  *
  *                - the 2 vertexes are vertically or horizontally aligned:
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  SteinerCongestion1.png "Horizontally aligned"
  *                      \image latex SteinerCongestion1.pdf "Horizontally aligned" width=0.7\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  SteinerCongestion2.png "Vertically aligned"
  *                      \image latex SteinerCongestion2.pdf "Vertically aligned" width=0.7\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                For all the edges between the 2 vertexes the estimate congestion is incremented by 1.
  *
  *                - the 2 vertexes are not aligned:
  *                <CENTER>
  *                <TABLE width=75% border=0>
  *                  <TR>
  *                    <TD>
  *                      \image html  SteinerCongestion3.png ""
  *                      \image latex SteinerCongestion3.pdf "" width=0.7\textwidth
  *                    </TD>
  *                    <TD>
  *                      \image html  SteinerCongestion4.png ""
  *                      \image latex SteinerCongestion4.pdf "" width=0.7\textwidth
  *                    </TD>
  *                  </TR>
  *                </TABLE>
  *                </CENTER>
  *
  *                There are 2 possible L-pathes, the algorithm consider that each path has a 50% probability, that means that the estimated
  *                congestion of each edge on a path is incremented by 0.5.
  *
  *                <b>\n Create or Update estimated congestion:</b>
  *
  *                The \e create parameter determines wether to create or update the estimated congestion, in fact it affects the
  *                Edge::AddSubEstimateOccupancy function. So depending on it, the estimated congestion computed just as bellow is
  *                added or substracted.
  *                
  *                When creating the estimated congestion (during Knik::InitGlobalRouting) \e create is \True while during the global routing step,
  *                in Graph::Monotonic or Graph::Dijkstra, as the Graph::_working_net is routed it does not contribute to the estimated congestion
  *                and thus \e create is \False.
  *
  *
  *  \param        create specifies whether to create or to update the estimated congestion
  *  \exception    return if Graph::_vertexes_to_route size is lesser than 2
  *  \exception    return if Graph::_vertexes_to_route size is greater than or equal to \ref GRAPH_FLUTELIMIT
  */

 // \}

 /*! \anchor       GraphTupleQueue Tuple Priority Queue Methods
  *  \name
  */
 // \{

 /*! \function     Vertex* Graph::ExtractMinFromPriorityQueue();
  *  \Return       the vertex in tuple priority queue which has the minimum priority
  */

 // \}

}
