00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 //-*-c++-*- 00037 // 00123 #ifndef lno_scc_RCS_ID 00124 #define lno_scc_RCS_ID 00125 #ifdef _KEEP_RCS_ID 00126 static char *lno_scc_rcs_id = "$Source$ $Revision$"; 00127 #endif /* _KEEP_RCS_ID */ 00128 #endif 00129 00130 #ifndef _lno_scc_INCLUDED 00131 #define _lno_scc_INCLUDED 00132 00133 #include "defs.h" 00134 #include "mempool.h" 00135 #include "cxx_template.h" 00136 #include "cxx_graph.h" 00137 #include "graph_template.h" 00138 00139 class SCC_DIRECTED_GRAPH16 : public DIRECTED_GRAPH16<EDGE16,VERTEX16> { 00140 private: 00141 00142 MEM_POOL *_sccmpool; // pool used for scc_id allocation 00143 VINDEX16 _scc_cnt; // total number of SCCs in this graph 00144 // it is set to -1 if the SCC info is not 00145 // valid 00146 DYN_ARRAY<VINDEX16> _scc_id; // dynamic array for SCC id (one element 00147 // for every vertex) 00148 00149 VINDEX16 *_link; // temporary array for SCC identification 00150 VINDEX16 *_dfn; // temporary array for SCC identification 00151 BOOL *_visited; // temporary array for SCC identification 00152 BOOL *_in_stack; // temporary array for SCC identification 00153 STACK<VINDEX16> *_dfs_stack; // temporary stack for SCC identification 00154 VINDEX16 _df_count; // counter for Depth-First-Search in SCC 00155 // identification 00156 00157 SCC_DIRECTED_GRAPH16(const SCC_DIRECTED_GRAPH16&); 00158 00159 void Scc_Dfs(VINDEX16 n); // Depth-First-Search used in SCC 00160 // identification 00161 00162 BOOL Scc_Is_Valid() { return _scc_cnt!=INVALID_VINDEX16; } 00163 00164 // _scc_cnt==INVALID_VINDEX16 00165 // invalidates SCC info 00166 void Invalidate_Scc() { _scc_cnt = INVALID_VINDEX16 ;} 00167 void Find_Scc(); // Identify SCCs in the graph 00168 public: 00169 SCC_DIRECTED_GRAPH16( 00170 const VINDEX16 vsize, const EINDEX16 evsize); 00171 ~SCC_DIRECTED_GRAPH16() { 00172 _scc_id.Free_array(); 00173 MEM_POOL_Pop(_sccmpool); 00174 MEM_POOL_Delete(_sccmpool); 00175 CXX_DELETE(_sccmpool,Malloc_Mem_Pool); 00176 } 00177 00178 SCC_DIRECTED_GRAPH16& operator=(const SCC_DIRECTED_GRAPH16& g); 00179 00180 EINDEX16 Add_Vertex(); 00181 void Delete_Vertex(VINDEX16 v); 00182 00183 EINDEX16 Add_Edge(VINDEX16 from, VINDEX16 to); 00184 EINDEX16 Add_Unique_Edge(VINDEX16 from, VINDEX16 to); 00185 void Delete_Edge(EINDEX16 e); 00186 00187 VINDEX16 Get_Scc_Id(VINDEX16 i) { 00188 if ( ! Scc_Is_Valid() ) Find_Scc(); 00189 return _scc_id[i]; } 00190 VINDEX16 Get_Scc_Count() { 00191 if ( ! Scc_Is_Valid() ) Find_Scc(); 00192 return _scc_cnt; } 00193 VINDEX16 Get_Scc_Size(VINDEX16 i); 00194 00195 mUINT16 Get_Level(mUINT16 level[]); 00196 00197 mUINT16 Level_Sort(VINDEX16 queue[]); 00198 00199 SCC_DIRECTED_GRAPH16* Acyclic_Condensation(MEM_POOL *mpool); 00200 00201 void Print(FILE *file) const { 00202 DIRECTED_GRAPH16<EDGE16,VERTEX16>::Print(file); 00203 } 00204 }; 00205 00206 #endif // _lno_scc_INCLUDED 00207
1.5.6