graph_template.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 graph_template_INCLUDED
#define graph_template_INCLUDED "graph_template.h"

#ifdef _KEEP_RCS_ID
#endif /* _KEEP_RCS_ID */

#ifndef defs_INCLUDED
#include "defs.h"
#endif
#ifndef mempool_INCLUDED
#include "mempool.h"
#endif
#ifndef cxx_template_INCLUDED
#include "cxx_template.h"
#endif
#ifndef cxx_graph_i_INCLUDED
#include "cxx_graph.i"
#endif
#include "cxx_memory.h"


template <class EDGE_TYPE, class VERTEX_TYPE>
class DIRECTED_GRAPH16 {
private:
  MEM_POOL      *_vmpool;       // pool used for vertex allocation
  MEM_POOL      *_empool;       // pool used for edge allocation
  VINDEX16      _vfree;         // the first vertex in the free vertex list
  EINDEX16      _efree;         // the first edge in the free edge list

                DIRECTED_GRAPH16(const DIRECTED_GRAPH16&);
protected:
  DYN_ARRAY<VERTEX_TYPE> _v;            // dynamic array for vertices
  VINDEX16      _vcnt;          // how many nodes there are in the graph
  DYN_ARRAY<EDGE_TYPE> _e;              // dynamic array for edges
  EINDEX16      _ecnt;          // how many edges there are in the graph

public:
                DIRECTED_GRAPH16(const VINDEX16 vsize, const EINDEX16 evsize);
                ~DIRECTED_GRAPH16()             { 
                        _v.Free_array();
                        _e.Free_array();
                        MEM_POOL_Pop(_vmpool);
                        MEM_POOL_Delete(_vmpool);
                        CXX_DELETE(_vmpool,Malloc_Mem_Pool);
                        MEM_POOL_Pop(_empool);
                        MEM_POOL_Delete(_empool);
                        CXX_DELETE(_empool,Malloc_Mem_Pool);
                        }

  DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>& 
                operator=(const DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>& g);

  void  Erase_Graph() { 
         _v.Setidx(0); _vcnt = 0; _vfree = 0; _e.Setidx(0); _ecnt = 0;
         _efree = 0; }

  VINDEX16      Add_Vertex();
  EINDEX16      Add_Edge(VINDEX16 from, VINDEX16 to);
  EINDEX16      Add_Unique_Edge(VINDEX16 from, VINDEX16 to);

  EINDEX16      Get_Edge(VINDEX16 from, VINDEX16 to) const;
  void          Delete_Vertex(VINDEX16 v);
  void          Delete_Edge(EINDEX16 e);

  VINDEX16      Get_Vertex() const;
  VINDEX16      Get_Next_Vertex(VINDEX16 v) const;

  EINDEX16      Get_Edge() const;
  EINDEX16      Get_Next_Edge(EINDEX16 e) const;

  BOOL          Vertex_Is_In_Graph(VINDEX16 v) const    {
                  return ((v <=_v.Lastidx()) && v>0 && !_v[v].Is_Free()); }
  BOOL          Edge_Is_In_Graph(EINDEX16 e) const      {
                  return ((e <=_e.Lastidx()) && e>0 && !_e[e].Is_Free()); }

  VINDEX16      Get_Source(EINDEX16 e) const    { 
                  Is_True (Edge_Is_In_Graph(e), ("Edge not in graph\n"));
                  return _e[e].Get_Source(); }
  VINDEX16      Get_Sink(EINDEX16 e) const      { 
                  Is_True (Edge_Is_In_Graph(e), ("Edge not in graph\n"));
                  return _e[e].Get_Sink(); }

  EINDEX16      Get_In_Edge(VINDEX16 v) const   { 
                  Is_True (Vertex_Is_In_Graph(v), ("Vertex not in graph\n"));
                  return _v[v].Get_In_Edge(); }
  EINDEX16      Get_Out_Edge(VINDEX16 v) const  { 
                  Is_True (Vertex_Is_In_Graph(v), ("Vertex not in graph\n"));
                  return _v[v].Get_Out_Edge(); }

  EINDEX16      Get_Next_In_Edge(EINDEX16 e) const
                                        { return _e[e].Get_Next_In_Edge(); }
  EINDEX16      Get_Next_Out_Edge(EINDEX16 e) const
                                        { return _e[e].Get_Next_Out_Edge(); }

  VINDEX16      Get_Vertex_Count() const        { return _vcnt; }
  EINDEX16      Get_Edge_Count() const          { return _ecnt; }

  BOOL          Is_Empty() const                { return _vcnt == 0; }

  void          Print(FILE *file) const;
};

// Implementation stuff from graph_template.cxx, since g++ (rightly)
// doesn't do implicit .cxx file inclusion.
template <class EDGE_TYPE, class VERTEX_TYPE>
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::
DIRECTED_GRAPH16( const VINDEX16 vsize, const EINDEX16 esize) {

  //Is_True( vsize >=0, ("Illegal graph size\n"));

  _vmpool = CXX_NEW(MEM_POOL,Malloc_Mem_Pool);
  MEM_POOL_Initialize(_vmpool,"vmpool",FALSE);
  MEM_POOL_Push(_vmpool);
  _v.Set_Mem_Pool(_vmpool);
  _v.Alloc_array(vsize+1);
  _v.Setidx( 0 );
  _vcnt = 0;
  _vfree = 0;

  //for (mINT16 i=1; i<=_vcnt; i++) {   // initialization
  //  _v[i].Set_Out_Edge(0);
  //  _v[i].Set_In_Edge(0);
  //}

  _empool = CXX_NEW(MEM_POOL,Malloc_Mem_Pool);
  MEM_POOL_Initialize(_empool,"empool",FALSE);
  MEM_POOL_Push(_empool);
  _e.Set_Mem_Pool(_empool);
  _e.Alloc_array(esize+1);
  _e.Setidx( 0 );
  _ecnt = 0;
  _efree = 0;

}

template <class EDGE_TYPE, class VERTEX_TYPE>
VINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Add_Vertex() {
  VINDEX16 new_vertex;

  // Is_True(_vcnt < GRAPH16_CAPACITY, ("Too many vertices\n"));
  if (_vcnt == GRAPH16_CAPACITY) return 0;

  if (_vfree == 0) { // grow the _v[] to accept more vertices
    new_vertex = _v.Newidx();
  } else {
    new_vertex = _vfree;
    _vfree = _v[_vfree].Get_Next_Free_Vertex();
  }

  // reset the in/out edge-lists to NULL
  _v[new_vertex].Set_Out_Edge(0);
  _v[new_vertex].Set_In_Edge(0);

  _vcnt++;

  return new_vertex;

}

template <class EDGE_TYPE, class VERTEX_TYPE>
EINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Add_Edge(VINDEX16 from, VINDEX16 to) {
  EINDEX16 new_edge;

  // Is_True(_ecnt < GRAPH16_CAPACITY, ("Too many edges\n"));
  if (_ecnt == GRAPH16_CAPACITY) return 0;
  if (_efree == 0) { // grow the _e[] to accept more edges
    new_edge = _e.Newidx();
  } else {
    new_edge = _efree;
    _efree = _e[_efree].Get_Next_Free_Edge();
  }
  
  _e[new_edge].Set_Source(from);
  _e[new_edge].Set_Sink(to);

  _ecnt++;

  // insert this edge into the out-edge list of the source vertex 'from'
  _e[new_edge].Set_Next_Out_Edge(_v[from].Get_Out_Edge());
  _v[from].Set_Out_Edge(new_edge);

  // insert this edge into the in-edge list of the sink vertex 'to'
  _e[new_edge].Set_Next_In_Edge(_v[to].Get_In_Edge());
  _v[to].Set_In_Edge(new_edge);

  return new_edge;

}

template <class EDGE_TYPE, class VERTEX_TYPE>
EINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Add_Unique_Edge(VINDEX16 from, VINDEX16 to) {
  EINDEX16 new_edge;

  // see if an edge already exists. No multiple edges between the same
  // pair of source and sink vertices.
  if (new_edge=Get_Edge(from,to)) return new_edge;

  return Add_Edge(from,to);

}

template <class EDGE_TYPE, class VERTEX_TYPE>
EINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Get_Edge(VINDEX16 from, VINDEX16 to) const {
  EINDEX16 e;
  e = _v[from].Get_Out_Edge();
  while (e != 0) {
    if (_e[e].Get_Sink() == to) return e;
    e = _e[e].Get_Next_Out_Edge();
  }
  return 0; // no corresponding edge
}

template <class EDGE_TYPE, class VERTEX_TYPE>
void
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Delete_Vertex(VINDEX16 v) {

  EINDEX16 e;

  // see if the vertex exists
  Is_True (Vertex_Is_In_Graph(v), ("Vertex not in graph\n"));

  while (e = _v[v].Get_In_Edge()) {
    Delete_Edge(e);
  };
  while (e = _v[v].Get_Out_Edge()) {
    Delete_Edge(e);
  };

  // insert the deleted vertex in free list
  _v[v].Set_Next_Free_Vertex(_vfree);
  _v[v].Set_To_Free();
  _vfree = v;

  _vcnt--;
  
}

template <class EDGE_TYPE, class VERTEX_TYPE>
void
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Delete_Edge(EINDEX16 e) {

  VINDEX16 from, to;
  EINDEX16 e1;

  // see if the edge exists
  Is_True (Edge_Is_In_Graph(e), ("Edge not in graph\n"));

  from = _e[e].Get_Source();
  to = _e[e].Get_Sink();

  if (_v[from].Get_Out_Edge() == e) {  // to delete the first edge in list
    _v[from].Set_Out_Edge(_e[e].Get_Next_Out_Edge());
  } else {
    e1 = _v[from].Get_Out_Edge();
    while (_e[e1].Get_Next_Out_Edge() != e) 
        e1 = _e[e1].Get_Next_Out_Edge();
    _e[e1].Set_Next_Out_Edge(_e[e].Get_Next_Out_Edge());
  }

  if (_v[to].Get_In_Edge() == e) {  // to delete the first edge in list
    _v[to].Set_In_Edge(_e[e].Get_Next_In_Edge());
  } else {
    e1 = _v[to].Get_In_Edge();
    while (_e[e1].Get_Next_In_Edge() != e) 
        e1 = _e[e1].Get_Next_In_Edge();
    _e[e1].Set_Next_In_Edge(_e[e].Get_Next_In_Edge());
  }

  _e[e].Set_Next_Free_Edge(_efree);  // insert the deleted edge in free list
  _e[e].Set_To_Free();
  _efree = e;

  _ecnt--;
  
}

template <class EDGE_TYPE, class VERTEX_TYPE>
VINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Get_Vertex() const {
  VINDEX16 v;

  if (Is_Empty()) return 0;

  v = _v.Lastidx();
  while (v>0 &&_v[v].Is_Free() ) v--;   // skip over free vertices
  Is_True( v>0 , ("Fail to get vertex\n"));

  return v;
}

template <class EDGE_TYPE, class VERTEX_TYPE>
VINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Get_Next_Vertex(VINDEX16 v) const {

  Is_True( Vertex_Is_In_Graph(v), ("Vertex does not exist in graph\n"));

  do {
    v--;
  } while (v>0 && _v[v].Is_Free() );    // skip over free vertices

  return v;
}

template <class EDGE_TYPE, class VERTEX_TYPE>
EINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Get_Edge() const {
  EINDEX16 e;

  if (_ecnt == 0) return 0;

  e = _e.Lastidx();
  while (_e[e].Is_Free() && e>0) e--;   // skip over free edges
  Is_True( e>0 , ("Fail to get edge\n"));

  return e;
}

template <class EDGE_TYPE, class VERTEX_TYPE>
EINDEX16
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Get_Next_Edge(EINDEX16 e) const {

  Is_True( Edge_Is_In_Graph(e), ("Edge does not exist in graph\n"));

  do {
    e--;
  } while (e > 0 && _e[e].Is_Free() );  // skip over free edges

  return e;
}

template <class EDGE_TYPE, class VERTEX_TYPE>
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>&
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::
operator=(const DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>& g) {

  // copy everything except mpool

  _vfree = g._vfree;
  _vcnt = g._vcnt;
  _efree = g._efree;
  _ecnt = g._ecnt;

  _v = g._v;
  _e = g._e;

  return *this;
}

template <class EDGE_TYPE, class VERTEX_TYPE>
void
DIRECTED_GRAPH16<EDGE_TYPE,VERTEX_TYPE>::Print(FILE *file) const {
  VINDEX16 i;
  EINDEX16 e;

  fprintf(file,"Print out graph edges and vertices ...\n");
  for (i=1; i<_e.Lastidx()+1; i++)
   if (!_e[i].Is_Free())
    fprintf(file, "%d: %d --> %d\n", i, _e[i]._from, _e[i]._to);

  for (i=1; i<_v.Lastidx()+1; i++)
   if (!_v[i].Is_Free()) {
    fprintf(file, "( ");
    e = _v[i].Get_In_Edge();
    while (e) {
      fprintf(file, "%d ", e);
      e = _e[e].Get_Next_In_Edge();
    }
    fprintf(file, ") %d ( ", i);
    e = _v[i].Get_Out_Edge();
    while (e) {
      fprintf(file, "%d ", e);
      e = _e[e].Get_Next_Out_Edge();
    }
    fprintf(file, ")\n");
  }
}

#endif          // graph_template_INCLUDED