00001
00002
00003 #include "BiSection.h"
00004
00005 DSS_NAMESPASE_BEGIN
00006
00007 CMcKee::CMcKee()
00008 {
00009 p_node_level = p_order = nodes = NULL;
00010 size=domA=domB=0;
00011 }
00012
00013 void CMcKee::Init(SparseConectivityMtxII* mtx)
00014 {
00015 this->mtx = mtx;
00016 n=mtx->N();
00017
00018 p_node_level = new long[n];
00019 memset(p_node_level,0,n*sizeof(long));
00020
00021 p_order = new long[n];
00022
00023 nodes = NULL;
00024 size = 0;
00025 }
00026
00027 CMcKee::~CMcKee()
00028 {
00029 delete [] p_node_level;
00030 delete [] p_order;
00031 }
00032
00033 BOOL CMcKee::IsAvailable(int v)
00034 {
00035 return (p_node_level[v]==0);
00036 }
00037
00038 void CMcKee::PrepareValid()
00039 {
00040 for (long v=0; v<n; v++)
00041 p_node_level[v]=-1;
00042
00043 for (long i=0; i<size;i++)
00044 p_node_level[nodes[i]]=0;
00045 }
00046
00047 long CMcKee::FindFirstNode()
00048 {
00049 long r=-1,cl,min = n+1;
00050 for (long i=0; i<size; i++)
00051 if (IsAvailable(nodes[i]) && (cl=mtx->ColumnLength(nodes[i]))<min) {min = cl;r=nodes[i];}
00052 return r;
00053 }
00054
00055
00056 void CMcKee::ComputeLevels()
00057 {
00058 PrepareValid();
00059
00060 long l=1;
00061 long k=0;
00062 long last_level_start = 0;
00063 long next_level_start = 0;
00064 long last_level_count = 0;
00065 long next_level_count = 0;
00066
00067 while(k<size)
00068 {
00069 if (last_level_count == 0)
00070 {
00071 long r=FindFirstNode();
00072 last_level_start = k;
00073
00074 if (r==-1)
00075 break;
00076 p_node_level[r] = l;
00077 p_order[k++] = r;last_level_count=1;
00078 }
00079 next_level_start = k;
00080 next_level_count = 0;
00081
00082 for (long ilr = last_level_start; ilr<next_level_start; ilr++)
00083 {
00084 long lr = p_order[ilr];
00085
00086 IntArrayList& al= *mtx->ColumnsIndexes[lr];
00087 for (long idx = al.Count-1; idx>=0; idx--)
00088 {
00089 long neig = al.Items[idx];
00090 if (!IsAvailable(neig)) continue;
00091 p_node_level[neig] = l+1;
00092 p_order[k++] = neig;next_level_count++;
00093 }
00094 }
00095 l++;
00096 last_level_count = next_level_count;
00097 last_level_start = next_level_start;
00098 }
00099 }
00100
00101 void CMcKee::DivideByMidLevel()
00102 {
00103 long last_level_start = size/2;
00104 int midlevel = p_node_level[p_order[last_level_start]];
00105 while(last_level_start>0 && p_node_level[p_order[last_level_start-1]]==midlevel)
00106 last_level_start--;
00107
00108 long next_level_start = last_level_start;
00109
00110 while(next_level_start<size && p_node_level[p_order[next_level_start]]==midlevel)
00111 next_level_start++;
00112
00113 domA = last_level_start;
00114 domB = size - next_level_start;
00115
00116 Array::Reverse(p_order+last_level_start,size-last_level_start);
00117 Array::Copy(p_order,nodes,size);
00118 }
00119
00120 CBiSection::CBiSection(SparseConectivityMtxII* mtx)
00121 {
00122 this->mtx = mtx;
00123 mck.Init(mtx);
00124 }
00125
00126 void CBiSection::RecurBiSectOrder(IntArrayList* order)
00127 {
00128 RecurBiSect(order->Items,order->Count);
00129 }
00130
00131 void CBiSection::RecurBiSect(long* nodes,long size)
00132 {
00133 if (size<=3)
00134 return;
00135
00136 long dA,dB;
00137 BiSect(nodes,size,dA,dB);
00138 RecurBiSect(nodes,dA);
00139 RecurBiSect(nodes+dA,dB);
00140 }
00141
00142 void CBiSection::BiSect(long* nodes,long size, long& domA, long& domB)
00143 {
00144 mck.nodes = nodes;
00145 mck.size = size;
00146 mck.ComputeLevels();
00147 mck.DivideByMidLevel();
00148
00149 domA = mck.domA;
00150 domB = mck.domB;
00151 }
00152
00153
00154
00155 DSS_NAMESPASE_END