00001
00002
00003 #ifndef _SPARSECONMTX_H__
00004 #define _SPARSECONMTX_H__
00005
00006 #include "ColHash.h"
00007 #include "ConList.h"
00008 #include "BigMatrix.h"
00009 #include "SparseMatrixF.h"
00010 #include "Ordering.h"
00011
00012 DSS_NAMESPASE_BEGIN
00013
00014
00015
00016
00017
00018
00019 class SparseConectivityMtxII :
00020 public TraceableMatrix,
00021 public IConectMatrix
00022 {
00023 public:
00024 IntArrayList** ColumnsIndexes;
00025 long n;
00026 long nonzeros;
00027
00028 public:
00029 long N() const {return n;}
00030 long Nonzeros() const {return nonzeros;}
00031
00032 public:
00033
00034 SparseConectivityMtxII(const SparseMatrixF& sm,char block_size);
00035 SparseConectivityMtxII(const SparseMatrixF& sm,Ordering* node_order,char block_size);
00036 SparseConectivityMtxII(SparseConectivityMtxII& mtx,Ordering* order);
00037 SparseConectivityMtxII(const SparseConectivityMtxII& mtx);
00038
00039 virtual ~SparseConectivityMtxII();
00040
00041 void AddGrow(long i, long j);
00042
00043 long ColumnLength(long i);
00044
00045
00046 void GetCmpRows(long* &adr, long* &ci);
00047
00048 IntArrayList* GetOrder_Cuthill_McKee2();
00049
00050 Ordering* GenerateMD(IntArrayList* fixed = NULL);
00051 Ordering* GenerateAMD(IntArrayList* fixed = NULL);
00052 Ordering* GenerateAMD_AA(IntArrayList* fixed = NULL);
00053 Ordering* Get_Cuthill_McKee();
00054 Ordering* Get_Reverse_Cuthill_McKee();
00055 Ordering* Get_Unity();
00056 Ordering* Get_RecursiveBiSection();
00057 Ordering* Get_MetisDiSection();
00058 Ordering* Get_ColAMD();
00059
00060 void GenerateFillInPresorted(Ordering* ord);
00061
00062 Ordering* GetOrdering(Ordering::Type ord);
00063
00064 IntArrayList* GetIndexesAboveDiagonalInColumn(long j);
00065
00066 IntArrayList* DetachIndexesAboveDiagonalInColumn(long j);
00067
00068 Ordering* GetPermutationAndPattern(Ordering::Type ord,IntArrayList* fixed = NULL);
00069 };
00070
00071
00072
00073
00074
00075 class MD_Qqraph
00076 {
00077 public:
00078 SparseConectivityMtxII* mtx;
00079 long* degrees;
00080 long* amd_w;
00081 private:
00082 long MinDegA,MinDegB,MinDegC;
00083 long vi_Min;
00084
00085 public:
00086 IntArrayList** A;
00087 IntArrayList** E;
00088 IntArrayList** I;
00089 IntArrayList** L;
00090
00091 long* pLIdx;
00092 long* pPIdx;
00093 long* pfixed;
00094
00095 IntLinkArray variables;
00096 IntArrayList* elements;
00097 long no_elements;
00098
00099 bool approximate_degree;
00100 bool keep_sorted_order;
00101 bool aggressive_absorbtion;
00102
00103 long n;
00104 long n_1;
00105 ColHash ht;
00106
00107 MD_Qqraph(SparseConectivityMtxII* mtx);
00108
00109 ~MD_Qqraph();
00110
00111 static void Insert(IntArrayList& al, long i);
00112
00113
00114
00115 inline bool IsFree(long i)
00116 {
00117 return bool(pfixed==NULL || pfixed[i]==0);
00118 }
00119
00120 void ComputeAMD_w_Le_Lp(long i);
00121
00122 void ClearAMD_w(long i);
00123
00124 long ApproximateMinumumDegree(long i,IntArrayList& Lp);
00125
00126
00127
00128
00129 long ExternalDegree(long i);
00130
00131
00132
00133 void Eliminate(long p);
00134
00135 long Hash(long i)
00136 {
00137 long hk = A[i]->SumElements() + E[i]->SumElements();
00138 return (hk % n_1)+1;
00139 }
00140
00141 bool IsIndistinguishable(long i,long j);
00142
00143 IntArrayList hash_parents;
00144 void SupervariablesDetection(IntArrayList& Lp);
00145
00146
00147
00148
00149
00150
00151 IntArrayList* GenerateMD(bool approximate_degree,IntArrayList* fixed = NULL);
00152 };
00153
00154
00155 DSS_NAMESPASE_END
00156
00157 #endif //_SPARSECONMTX_H__