NGSolve
4.9
|
00001 #ifndef FILE_ORDER 00002 #define FILE_ORDER 00003 00004 /* *************************************************************************/ 00005 /* File: order.hh */ 00006 /* Author: Joachim Schoeberl */ 00007 /* Date: 18. Jun. 97 */ 00008 /* *************************************************************************/ 00009 00010 00011 namespace ngla 00012 { 00013 00014 /* 00015 reordering for sparse cholesky factoriztion 00016 */ 00017 00019 class MDOPriorityQueue 00020 { 00021 struct entry { 00022 int degree, prev, next; 00023 }; 00024 Array<entry> list; 00025 Array<int> first_in_class; 00026 public: 00027 MDOPriorityQueue (int size, int maxdeg); 00028 ~MDOPriorityQueue (); 00029 int MinDegree () const; 00030 int GetDegree (int nr) const { return list[nr].degree; } 00031 void SetDegree (int nr, int deg); 00032 void Invalidate (int nr); 00033 }; 00034 00035 00037 class MDOVertex 00038 { 00039 protected: 00040 int master; 00041 int nextslave; 00042 int numslaves; 00043 bool eliminated; 00044 bool used; 00045 bool flag; 00046 00047 00048 public: 00050 int * connected; 00052 int nconnected; 00053 00055 MDOVertex(int ma=0) { Init (ma); } 00057 ~MDOVertex() { ; } 00058 00060 void Init (int ma) 00061 { 00062 master = ma; 00063 nextslave = -1; 00064 numslaves = 0; 00065 flag = 0; 00066 eliminated = 0; 00067 used = 0; 00068 } 00069 00071 int Master() const { return master; }; 00073 void SetMaster(int ma) { master = ma; }; 00075 int NextSlave () const {return nextslave; }; 00077 void SetNextSlave( int ns ) { nextslave = ns; }; 00079 bool Eliminated() const {return eliminated; }; 00081 void SetEliminated(bool el) {eliminated = el; }; 00083 bool Used() const {return used; }; 00085 void SetUsed(bool us) {used = us; } ; 00087 bool Flag() const {return flag; }; 00089 void SetFlag(bool fl) {flag = fl;}; 00090 00091 friend class MinimumDegreeOrdering; 00092 }; 00093 00095 class CliqueEl 00096 { 00097 public: 00099 CliqueEl *next; 00100 CliqueEl *nextcl; 00102 int vnr:30; 00104 bool eliminate; 00106 bool flag; 00107 00109 CliqueEl () { 00110 next = NULL; 00111 nextcl = NULL; 00112 eliminate = 0; 00113 flag = 0; 00114 } 00115 00117 CliqueEl * GetNext() 00118 { return next; } 00119 00121 CliqueEl * GetNextClique() 00122 { return nextcl; } 00123 00125 int GetVertexNr() const 00126 { 00127 return vnr; 00128 } 00129 00130 /* 00132 static ngstd::BlockAllocator ball; 00134 00135 void * operator new(size_t) 00136 { 00137 cout << "call own new" << endl; 00138 return ball.Alloc(); 00139 } 00140 00142 void operator delete (void * p, size_t) 00143 { 00144 cout << "call own delete" << endl; 00145 ball.Free (p); 00146 } 00147 */ 00148 }; 00149 00150 00151 00153 class MinimumDegreeOrdering 00154 { 00155 public: 00157 int n; 00159 Array<CliqueEl*> cliques; 00161 Array<int> order; 00163 Array<int> blocknr; 00165 Array<MDOVertex> vertices; 00167 MDOPriorityQueue priqueue; 00169 ngstd::BlockAllocator ball; 00170 public: 00172 MinimumDegreeOrdering (int an); 00174 void AddEdge (int v1, int v2); 00176 void PrintCliques (); 00177 00179 int CalcDegree (int v1); 00181 void EliminateMasterVertex (int v); 00182 void EliminateSlaveVertex (int v); 00184 void Order(); 00186 ~MinimumDegreeOrdering(); 00187 00189 int NumCliques (int v) const; 00190 00192 void SetFlagNodes (int v); 00194 void ClearFlagNodes (int v); 00195 00197 void SetFlagCliques (int v); 00199 void ClearFlagCliques (int v); 00201 int Size () const { return n; } 00203 // int GetNZE() const; 00204 // friend class SparseCholesky; 00205 00206 int NextSlave (int vnr) const 00207 { 00208 return vertices[vnr].NextSlave(); 00209 } 00211 int NumSlaves (int vnr) const 00212 { 00213 return vertices[vnr].numslaves; 00214 /* 00215 int next = vertices[vnr].NextSlave(); 00216 int cnt = 0; 00217 while (next != -1) 00218 { 00219 next = vertices[next].NextSlave(); 00220 cnt++; 00221 } 00222 return cnt; 00223 */ 00224 } 00226 bool IsMaster (int vnr) const 00227 { 00228 return vertices[vnr].Master() == vnr; 00229 } 00230 00231 void SetMaster (int master, int slave); 00232 }; 00233 00234 00235 } 00236 00237 #endif