| 131 | } |
| 132 | |
| 133 | static void ConstructTreeLimitBranching(TDistrTree* res, const TVector<TTreeConnectorCost>& links, int nodeCount, int maxBranching) { |
| 134 | if (links.empty() || nodeCount == 1) { |
| 135 | res->FinalNodeId = 0; |
| 136 | return; |
| 137 | } |
| 138 | TDistrTreeConstructor treeConstr(nodeCount); |
| 139 | |
| 140 | int groupCount = nodeCount; |
| 141 | for (int level = 1; groupCount > 1; ++level) { |
| 142 | int limit = maxBranching; |
| 143 | if (groupCount < maxBranching * 2) |
| 144 | limit = maxBranching * 2; |
| 145 | for (int i = 0; i < links.ysize(); ++i) { |
| 146 | const TTreeConnectorCost& tc = links[i]; |
| 147 | int g1 = treeConstr.GetParent(tc.Vec1); |
| 148 | int g2 = treeConstr.GetParent(tc.Vec2); |
| 149 | if (g1 == g2) |
| 150 | continue; // already connected |
| 151 | |
| 152 | const TDistrTree& gg1 = treeConstr.Group[g1]; |
| 153 | const TDistrTree& gg2 = treeConstr.Group[g2]; |
| 154 | int g1count = gg1.Cost == level ? gg1.Children.ysize() : 1; |
| 155 | int g2count = gg2.Cost == level ? gg2.Children.ysize() : 1; |
| 156 | if (g1count + g2count > limit) |
| 157 | continue; |
| 158 | |
| 159 | int newGroupId; |
| 160 | TDistrTree& newGroup = treeConstr.AddTree(&newGroupId); |
| 161 | if (gg1.Cost == level) |
| 162 | newGroup.Children.insert(newGroup.Children.end(), gg1.Children.begin(), gg1.Children.end()); |
| 163 | else |
| 164 | newGroup.Children.push_back(gg1); |
| 165 | if (gg2.Cost == level) |
| 166 | newGroup.Children.insert(newGroup.Children.end(), gg2.Children.begin(), gg2.Children.end()); |
| 167 | else |
| 168 | newGroup.Children.push_back(gg2); |
| 169 | newGroup.Cost = level; |
| 170 | |
| 171 | treeConstr.Group2parent[g1] = newGroupId; |
| 172 | treeConstr.Group2parent[g2] = newGroupId; |
| 173 | --groupCount; |
| 174 | } |
| 175 | } |
| 176 | *res = treeConstr.Group[treeConstr.GetParent(0)]; |
| 177 | } |
| 178 | |
| 179 | const ui16 N_GROUP_START = 0xffff; |
| 180 | const ui16 N_GROUP_END = 0xfffe; |