00001
00007 #include "Tree.hpp"
00008 #include "Debug.hpp"
00009 #include <vector>
00010 #include <queue>
00011 #include <algorithm>
00012 #include <cstring>
00013 #include <sstream>
00014 #include <string>
00015 #include <iostream>
00016 using namespace std;
00017
00018
00019 Tree::Tree() :
00020 mOrder( 0 ),
00021 mDegrees( NULL ),
00022 mOffsets( NULL ),
00023 mAdjArray( NULL )
00024 {
00025 }
00026
00027
00028
00029 Tree::Tree( unsigned int order, int *levelSequence ) :
00030 mOrder( order )
00031 {
00032
00033 mOffsets = new unsigned int[mOrder];
00034 mDegrees = new unsigned int[mOrder];
00035 memset( mOffsets, 0, sizeof( unsigned int ) * mOrder );
00036 memset( mDegrees, 0, sizeof( unsigned int ) * mOrder );
00037
00038
00039 vector<Edge> edges;
00040 Edge e;
00041 for( unsigned int i = 2; i <= mOrder; i++ )
00042 {
00043 e.u = i - 1;
00044 e.v = levelSequence[i - 1] - 1;
00045 mDegrees[e.u]++;
00046 mDegrees[e.v]++;
00047 edges.push_back( e );
00048 }
00049
00050
00051 for( unsigned int i = 1; i < mOrder; i++ )
00052 {
00053 mOffsets[i] = mOffsets[i - 1] + mDegrees[i - 1];
00054 }
00055
00056
00057 mAdjArray = new unsigned int[2 * ( mOrder - 1 )];
00058 unsigned int *currSizes = new unsigned int[mOrder];
00059 memset( currSizes, 0, sizeof( unsigned int ) * mOrder );
00060 for( unsigned int i = 0; i < edges.size(); i++ )
00061 {
00062 unsigned int u = edges[i].u;
00063 unsigned int v = edges[i].v;
00064 mAdjArray[mOffsets[u] + currSizes[u]++] = v;
00065 mAdjArray[mOffsets[v] + currSizes[v]++] = u;
00066 }
00067 delete [] currSizes;
00068 }
00069
00070 Tree::Tree( const Tree & that )
00071 {
00072
00073 mOrder = that.mOrder;
00074 mDegrees = new unsigned int[mOrder];
00075 mOffsets = new unsigned int[mOrder];
00076 mAdjArray = new unsigned int[2 * ( mOrder - 1 )];
00077
00078
00079 memcpy( mDegrees, that.mDegrees, sizeof( unsigned int ) * mOrder );
00080 memcpy( mOffsets, that.mOffsets, sizeof( unsigned int ) * mOrder );
00081 memcpy( mAdjArray, that.mAdjArray, sizeof( unsigned int ) * ( 2 * ( mOrder - 1 ) ) );
00082 }
00083
00084 Tree::~Tree()
00085 {
00086
00087 if( mDegrees != NULL )
00088 {
00089 delete [] mDegrees;
00090 }
00091 if( mOffsets != NULL )
00092 {
00093 delete [] mOffsets;
00094 }
00095 if( mAdjArray != NULL )
00096 {
00097 delete [] mAdjArray;
00098 }
00099 }
00100
00101 std::vector<Edge> Tree::getEdges() const
00102 {
00103 std::vector<Edge> edges;
00104 for( unsigned int i = 0; i < mOrder; i++ )
00105 {
00106 for( unsigned int j = 0; j < mDegrees[i]; j++ )
00107 {
00108 Edge e;
00109 e.u = i;
00110 e.v = mAdjArray[mOffsets[i] + j];
00111
00112 if( e.u < e.v )
00113 {
00114 edges.push_back( e );
00115 }
00116 }
00117 }
00118
00119 return edges;
00120 }
00121
00122 void Tree::getDegreeSequence( std::vector<unsigned int> & degreeSequence ) const
00123 {
00124
00125 degreeSequence.clear();
00126 degreeSequence.insert( degreeSequence.end(), &mDegrees[0], &mDegrees[mOrder] );
00127 std::sort( degreeSequence.begin(), degreeSequence.end(), std::greater<int>() );
00128 }
00129
00130 void Tree::getPathNums( std::vector<unsigned int> & pathNums ) const
00131 {
00132
00133 pathNums.clear();
00134 for( unsigned int i = 0; i < mOrder; i++ )
00135 {
00136 pathNums.push_back( 0 );
00137 }
00138
00139
00140 bool *visited = new bool[mOrder];
00141 for( unsigned int i = 0; i < mOrder; i++ )
00142 {
00143
00144 memset( visited, 0, sizeof( bool ) * mOrder );
00145
00146 pathNumsDfs( i, 1, visited, pathNums );
00147 }
00148 delete [] visited;
00149
00150
00151 for( unsigned int i = 0; i < pathNums.size(); i++ )
00152 {
00153 pathNums[i] /= 2;
00154 }
00155 }
00156
00157 void Tree::print() const
00158 {
00159 vector<Edge> edgeSet = getEdges();
00160 for( unsigned int i = 0; i < edgeSet.size(); i++ )
00161 {
00162 cout << "(" << edgeSet[i].u << ", " << edgeSet[i].v << ") ";
00163 }
00164 cout << endl;
00165 }
00166
00167 Tree & Tree::operator=( const Tree & that )
00168 {
00169
00170 if( this != &that )
00171 {
00172 delete [] mDegrees;
00173 delete [] mOffsets;
00174 delete [] mAdjArray;
00175
00176 mOrder = that.mOrder;
00177
00178 mDegrees = new unsigned int[mOrder];
00179 mOffsets = new unsigned int[mOrder];
00180 mAdjArray = new unsigned int[2 * ( mOrder - 1 )];
00181
00182 memcpy( mDegrees, that.mDegrees, sizeof( unsigned int ) * mOrder );
00183 memcpy( mOffsets, that.mOffsets, sizeof( unsigned int ) * mOrder );
00184 memcpy( mAdjArray, that.mAdjArray, sizeof( unsigned int ) * ( 2 * ( mOrder - 1 ) ) );
00185 }
00186
00187 return *this;
00188 }
00189
00190 void Tree::pathNumsDfs( unsigned int i, unsigned int count, bool *& visited, std::vector<unsigned int> & pathNums ) const
00191 {
00192
00193 visited[i] = true;
00194 for( unsigned int j = 0; j < mDegrees[i]; j++ )
00195 {
00196 unsigned int adjVert = mAdjArray[mOffsets[i] + j];
00197
00198 if( !visited[adjVert] )
00199 {
00200
00201 pathNums[count]++;
00202
00203 pathNumsDfs( adjVert, count + 1, visited, pathNums );
00204 }
00205 }
00206 }
00207