NGSolve  4.9
linalg/order.hpp
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