cxx_graph.h

Go to the documentation of this file.

/*

  Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

  Further, this software is distributed without any warranty that it is
  free of the rightful claim of any third person regarding infringement 
  or the like.  Any license provided herein, whether implied or 
  otherwise, applies only to this software file.  Patent licenses, if 
  any, provided herein do not apply to combinations of this program with 
  other software, or any other product whatsoever.  

  You should have received a copy of the GNU General Public License along
  with this program; if not, write the Free Software Foundation, Inc., 59
  Temple Place - Suite 330, Boston MA 02111-1307, USA.

  Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
  Mountain View, CA 94043, or:

  http://www.sgi.com

  For further information regarding this notice, see:

  http://oss.sgi.com/projects/GenInfo/NoticeExplan

*/


//-*-c++-*-
#ifndef cxx_graph_INCLUDED
#define cxx_graph_INCLUDED "cxx_graph.h"

#ifdef _KEEP_RCS_ID
#endif /* _KEEP_RCS_ID */

#ifndef defs_INCLUDED
#include "defs.h"
#endif
#ifndef cxx_graph_i_INCLUDED
#include "cxx_graph.i"
#endif
#ifndef graph_template_INCLUDED
#include "graph_template.h"
#endif

/* To up the graph capacity, here's what all one needs to do:
 * 1. change the typedefs below to (say) mUINT32.
 * 2. change the typedefs in graph_template.h
 * 3. increase INVALID_VINDEX16 and GRAPH16_CAPACITY in cxx_graph.cxx.
 * 4. change 
 *       ARRAY_DIRECTED_GRAPH16(mUINT16 num_v, mUINT16 num_e, WN_MAP map, 
 *    to
 *       ARRAY_DIRECTED_GRAPH16(mUINT32 num_v, mUINT32 num_e, WN_MAP map, 
 *    in dep_graph.h
 * 5. increase LNO_Graph_Capacity in lnodriver.c.
 */


class VERTEX16 {
  friend        class DIRECTED_GRAPH16<class EDGE16, class VERTEX16>;
  friend  class DIRECTED_GRAPH16<class ARRAY_EDGE16,class ARRAY_VERTEX16>;  
  friend  class DIRECTED_GRAPH16<class LAT_EDGE16,class LAT_VERTEX16>;  
  friend  class DIRECTED_GRAPH16<class TEDGE,class TVERTEX>;  
  friend  class DIRECTED_GRAPH16<class FB_EDGE, class FB_NODE>;
private:
  EINDEX16      _from;          // link to in edges
                                // also used to link free vertices
  EINDEX16      _to;            // link to out edges
                                // also used to mark free vertices if
                                // _to == INVALID_VINDEX16

                VERTEX16(const VERTEX16&);

protected:
  void          Set_Next_Free_Vertex(VINDEX16 i){ _from = i; }
  void          Set_To_Free()                   { _to = INVALID_VINDEX16; }
  BOOL          Is_Free() const         { return _to == INVALID_VINDEX16; }
  VINDEX16      Get_Next_Free_Vertex() const    { return _from; }
  void          Set_Out_Edge(EINDEX16 i)        { _from = i; }
  void          Set_In_Edge(EINDEX16 i)         { _to = i; }

public:
                VERTEX16()                      { _from = 0; _to = 0; }
                ~VERTEX16()                     {};

  VERTEX16&     operator = (const VERTEX16&);

  EINDEX16      Get_In_Edge() const             { return _to; }
                                // Get the first in-edge of the vertex
  EINDEX16      Get_Out_Edge() const            { return _from; }
                                // Get the first out-edge of the vertex
};

class EDGE16 {
  friend        class DIRECTED_GRAPH16<class EDGE16,class VERTEX16>;
  friend  class DIRECTED_GRAPH16<class ARRAY_EDGE16,class ARRAY_VERTEX16>;  
  friend  class DIRECTED_GRAPH16<class LAT_EDGE16,class LAT_VERTEX16>;  
  friend  class DIRECTED_GRAPH16<class TEDGE,class TVERTEX>;  
  friend  class DIRECTED_GRAPH16<class FB_EDGE, class FB_NODE>;
  friend        class SCC_DIRECTED_GRAPH16;
private:

  VINDEX16      _from;          // the source of the edge
  VINDEX16      _to;            // the sink of the edge
  EINDEX16      _nfrom;         // next edge of same source
  EINDEX16      _nto;           // next edge of same sink

                EDGE16(const EDGE16&);

protected:
  void          Set_Source(VINDEX16 i)          { _from = i; }
  void          Set_Sink(VINDEX16 i)            { _to = i; }
  void          Set_Next_Out_Edge(EINDEX16 i)   { _nfrom = i; }
  void          Set_Next_In_Edge(EINDEX16 i)    { _nto = i; }
  void          Set_Next_Free_Edge(EINDEX16 i)  { _from = i; }
  void          Set_To_Free()                   { _to = INVALID_VINDEX16; }
  BOOL          Is_Free() const         { return _to == INVALID_VINDEX16; }
  VINDEX16      Get_Next_Free_Edge() const      { return _from; }
  EINDEX16      Get_Next_Out_Edge() const       { return _nfrom; }
  EINDEX16      Get_Next_In_Edge() const        { return _nto; }
public:
                EDGE16()                        { _from=_to=_nfrom=_nto=0; }
                ~EDGE16()                       {}

  EDGE16&       operator = (const EDGE16&);

  VINDEX16      Get_Source() const              { return _from; }
  VINDEX16      Get_Sink() const                { return _to; }
};

#endif          // cxx_graph_INCLUDED