r775:6cab2ab9d8e7
Tue, 25 Aug 2009 16:32:47
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -165,135 +165,184 @@ |
| 165 | 165 |
nodeRef[n] = Node(node_index); |
| 166 | 166 |
node_first_in[node_index] = -1; |
| 167 | 167 |
++node_index; |
| 168 | 168 |
} |
| 169 | 169 |
|
| 170 | 170 |
ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef); |
| 171 | 171 |
|
| 172 | 172 |
int arc_index = 0; |
| 173 | 173 |
for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
|
| 174 | 174 |
int source = nodeRef[n].id; |
| 175 | 175 |
std::vector<GArc> arcs; |
| 176 | 176 |
for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
|
| 177 | 177 |
arcs.push_back(e); |
| 178 | 178 |
} |
| 179 | 179 |
if (!arcs.empty()) {
|
| 180 | 180 |
node_first_out[source] = arc_index; |
| 181 | 181 |
std::sort(arcs.begin(), arcs.end(), arcLess); |
| 182 | 182 |
for (typename std::vector<GArc>::iterator it = arcs.begin(); |
| 183 | 183 |
it != arcs.end(); ++it) {
|
| 184 | 184 |
int target = nodeRef[digraph.target(*it)].id; |
| 185 | 185 |
arcRef[*it] = Arc(arc_index); |
| 186 | 186 |
arc_source[arc_index] = source; |
| 187 | 187 |
arc_target[arc_index] = target; |
| 188 | 188 |
arc_next_in[arc_index] = node_first_in[target]; |
| 189 | 189 |
node_first_in[target] = arc_index; |
| 190 | 190 |
arc_next_out[arc_index] = arc_index + 1; |
| 191 | 191 |
++arc_index; |
| 192 | 192 |
} |
| 193 | 193 |
arc_next_out[arc_index - 1] = -1; |
| 194 | 194 |
} else {
|
| 195 | 195 |
node_first_out[source] = arc_index; |
| 196 | 196 |
} |
| 197 | 197 |
} |
| 198 | 198 |
node_first_out[node_num] = arc_num; |
| 199 | 199 |
} |
| 200 | 200 |
|
| 201 | 201 |
protected: |
| 202 | 202 |
|
| 203 | 203 |
void fastFirstOut(Arc& e, const Node& n) const {
|
| 204 | 204 |
e.id = node_first_out[n.id]; |
| 205 | 205 |
} |
| 206 | 206 |
|
| 207 | 207 |
static void fastNextOut(Arc& e) {
|
| 208 | 208 |
++e.id; |
| 209 | 209 |
} |
| 210 | 210 |
void fastLastOut(Arc& e, const Node& n) const {
|
| 211 | 211 |
e.id = node_first_out[n.id + 1]; |
| 212 | 212 |
} |
| 213 | 213 |
|
| 214 | 214 |
protected: |
| 215 | 215 |
bool built; |
| 216 | 216 |
int node_num; |
| 217 | 217 |
int arc_num; |
| 218 | 218 |
int *node_first_out; |
| 219 | 219 |
int *node_first_in; |
| 220 | 220 |
int *arc_source; |
| 221 | 221 |
int *arc_target; |
| 222 | 222 |
int *arc_next_in; |
| 223 | 223 |
int *arc_next_out; |
| 224 | 224 |
}; |
| 225 | 225 |
|
| 226 | 226 |
typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase; |
| 227 | 227 |
|
| 228 | 228 |
|
| 229 |
/// \ingroup graphs |
|
| 230 |
/// |
|
| 231 |
/// \brief A static directed graph class. |
|
| 232 |
/// |
|
| 233 |
/// \ref StaticDigraph is a highly efficient digraph implementation, |
|
| 234 |
/// but it is fully static. |
|
| 235 |
/// It stores only two \c int values for each node and only four \c int |
|
| 236 |
/// values for each arc. Moreover it provides faster item iteration than |
|
| 237 |
/// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt |
|
| 238 |
/// iterators, since its arcs are stored in an appropriate order. |
|
| 239 |
/// However it only provides build() and clear() functions and does not |
|
| 240 |
/// support any other modification of the digraph. |
|
| 241 |
/// |
|
| 242 |
/// This type fully conforms to the \ref concepts::Digraph "Digraph concept". |
|
| 243 |
/// Most of its member functions and nested classes are documented |
|
| 244 |
/// only in the concept class. |
|
| 245 |
/// |
|
| 246 |
/// \sa concepts::Digraph |
|
| 229 | 247 |
class StaticDigraph : public ExtendedStaticDigraphBase {
|
| 230 | 248 |
public: |
| 231 | 249 |
|
| 232 | 250 |
typedef ExtendedStaticDigraphBase Parent; |
| 233 | 251 |
|
| 234 | 252 |
public: |
| 235 | 253 |
|
| 254 |
/// \brief Clear the digraph. |
|
| 255 |
/// |
|
| 256 |
/// This function erases all nodes and arcs from the digraph. |
|
| 257 |
void clear() {
|
|
| 258 |
Parent::clear(); |
|
| 259 |
} |
|
| 260 |
|
|
| 261 |
/// \brief Build the digraph copying another digraph. |
|
| 262 |
/// |
|
| 263 |
/// This function builds the digraph copying another digraph of any |
|
| 264 |
/// kind. It can be called more than once, but in such case, the whole |
|
| 265 |
/// structure and all maps will be cleared and rebuilt. |
|
| 266 |
/// |
|
| 267 |
/// This method also makes possible to copy a digraph to a StaticDigraph |
|
| 268 |
/// structure using \ref DigraphCopy. |
|
| 269 |
/// |
|
| 270 |
/// \param digraph An existing digraph to be copied. |
|
| 271 |
/// \param nodeRef The node references will be copied into this map. |
|
| 272 |
/// Its key type must be \c Digraph::Node and its value type must be |
|
| 273 |
/// \c StaticDigraph::Node. |
|
| 274 |
/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" |
|
| 275 |
/// concept. |
|
| 276 |
/// \param arcRef The arc references will be copied into this map. |
|
| 277 |
/// Its key type must be \c Digraph::Arc and its value type must be |
|
| 278 |
/// \c StaticDigraph::Arc. |
|
| 279 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
|
| 280 |
/// |
|
| 281 |
/// \note If you do not need the arc references, then you could use |
|
| 282 |
/// \ref NullMap for the last parameter. However the node references |
|
| 283 |
/// are required by the function itself, thus they must be readable |
|
| 284 |
/// from the map. |
|
| 236 | 285 |
template <typename Digraph, typename NodeRefMap, typename ArcRefMap> |
| 237 | 286 |
void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
|
| 238 | 287 |
if (built) Parent::clear(); |
| 239 | 288 |
Parent::build(digraph, nodeRef, arcRef); |
| 240 | 289 |
} |
| 241 | 290 |
|
| 242 | 291 |
|
| 243 | 292 |
protected: |
| 244 | 293 |
|
| 245 | 294 |
using Parent::fastFirstOut; |
| 246 | 295 |
using Parent::fastNextOut; |
| 247 | 296 |
using Parent::fastLastOut; |
| 248 | 297 |
|
| 249 | 298 |
public: |
| 250 | 299 |
|
| 251 | 300 |
class OutArcIt : public Arc {
|
| 252 | 301 |
public: |
| 253 | 302 |
|
| 254 | 303 |
OutArcIt() { }
|
| 255 | 304 |
|
| 256 | 305 |
OutArcIt(Invalid i) : Arc(i) { }
|
| 257 | 306 |
|
| 258 | 307 |
OutArcIt(const StaticDigraph& digraph, const Node& node) {
|
| 259 | 308 |
digraph.fastFirstOut(*this, node); |
| 260 | 309 |
digraph.fastLastOut(last, node); |
| 261 | 310 |
if (last == *this) *this = INVALID; |
| 262 | 311 |
} |
| 263 | 312 |
|
| 264 | 313 |
OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
|
| 265 | 314 |
if (arc != INVALID) {
|
| 266 | 315 |
digraph.fastLastOut(last, digraph.source(arc)); |
| 267 | 316 |
} |
| 268 | 317 |
} |
| 269 | 318 |
|
| 270 | 319 |
OutArcIt& operator++() {
|
| 271 | 320 |
StaticDigraph::fastNextOut(*this); |
| 272 | 321 |
if (last == *this) *this = INVALID; |
| 273 | 322 |
return *this; |
| 274 | 323 |
} |
| 275 | 324 |
|
| 276 | 325 |
private: |
| 277 | 326 |
Arc last; |
| 278 | 327 |
}; |
| 279 | 328 |
|
| 280 | 329 |
Node baseNode(const OutArcIt &arc) const {
|
| 281 | 330 |
return Parent::source(static_cast<const Arc&>(arc)); |
| 282 | 331 |
} |
| 283 | 332 |
|
| 284 | 333 |
Node runningNode(const OutArcIt &arc) const {
|
| 285 | 334 |
return Parent::target(static_cast<const Arc&>(arc)); |
| 286 | 335 |
} |
| 287 | 336 |
|
| 288 | 337 |
Node baseNode(const InArcIt &arc) const {
|
| 289 | 338 |
return Parent::target(static_cast<const Arc&>(arc)); |
| 290 | 339 |
} |
| 291 | 340 |
|
| 292 | 341 |
Node runningNode(const InArcIt &arc) const {
|
| 293 | 342 |
return Parent::source(static_cast<const Arc&>(arc)); |
| 294 | 343 |
} |
| 295 | 344 |
|
| 296 | 345 |
}; |
| 297 | 346 |
|
| 298 | 347 |
} |
| 299 | 348 |
|
0 comments (0 inline)