Changeset 1472:c3bda060cfa3 in lemon0.x
 Timestamp:
 06/10/05 14:22:22 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1952
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_adaptor.h
r1435 r1472 28 28 #include <lemon/invalid.h> 29 29 #include <lemon/maps.h> 30 #include <lemon/bits/erasable_graph_extender.h> 31 #include <lemon/bits/clearable_graph_extender.h> 32 #include <lemon/bits/extendable_graph_extender.h> 30 33 #include <lemon/bits/iterable_graph_extender.h> 34 #include <lemon/bits/alteration_notifier.h> 35 #include <lemon/bits/default_map.h> 31 36 #include <lemon/bits/undir_graph_extender.h> 32 37 #include <iostream> … … 1211 1216 }; 1212 1217 1218 /// \e 1219 template <typename _Graph> 1220 class NewEdgeSetAdaptorBase { 1221 public: 1222 1223 typedef _Graph Graph; 1224 typedef typename Graph::Node Node; 1225 typedef typename Graph::NodeIt NodeIt; 1226 1227 protected: 1228 1229 struct NodeT { 1230 int first_out, first_in; 1231 NodeT() : first_out(1), first_in(1) {} 1232 }; 1233 1234 class NodesImpl : protected Graph::template NodeMap<NodeT> { 1235 1236 typedef typename Graph::template NodeMap<NodeT> Parent; 1237 typedef NewEdgeSetAdaptorBase<Graph> Adaptor; 1238 1239 Adaptor& adaptor; 1240 1241 public: 1242 1243 NodesImpl(Adaptor& _adaptor, const Graph& _graph) 1244 : Parent(_graph), adaptor(_adaptor) {} 1245 1246 virtual ~NodesImpl() {} 1247 1248 virtual void build() { 1249 Parent::build(); 1250 } 1251 1252 virtual void clear() { 1253 adaptor._clear(); 1254 Parent::clear(); 1255 } 1256 1257 virtual void add(const Node& node) { 1258 Parent::add(node); 1259 adaptor._add(node); 1260 } 1261 1262 virtual void erase(const Node& node) { 1263 adaptor._erase(node); 1264 Parent::erase(node); 1265 } 1266 1267 NodeT& operator[](const Node& node) { 1268 return Parent::operator[](node); 1269 } 1270 1271 const NodeT& operator[](const Node& node) const { 1272 return Parent::operator[](node); 1273 } 1274 1275 }; 1276 1277 NodesImpl* nodes; 1278 1279 struct EdgeT { 1280 Node source, target; 1281 int next_out, next_in; 1282 int prev_out, prev_in; 1283 EdgeT() : prev_out(1), prev_in(1) {} 1284 }; 1285 1286 std::vector<EdgeT> edges; 1287 1288 int first_edge; 1289 int first_free_edge; 1290 1291 virtual void _clear() = 0; 1292 virtual void _add(const Node& node) = 0; 1293 virtual void _erase(const Node& node) = 0; 1294 1295 const Graph* graph; 1296 1297 void initalize(const Graph& _graph, NodesImpl& _nodes) { 1298 graph = &_graph; 1299 nodes = &_nodes; 1300 } 1301 1302 public: 1303 1304 class Edge { 1305 friend class NewEdgeSetAdaptorBase<Graph>; 1306 protected: 1307 Edge(int _id) : id(_id) {} 1308 int id; 1309 public: 1310 Edge() {} 1311 Edge(Invalid) : id(1) {} 1312 bool operator==(const Edge& edge) const { return id == edge.id; } 1313 bool operator!=(const Edge& edge) const { return id != edge.id; } 1314 bool operator<(const Edge& edge) const { return id < edge.id; } 1315 }; 1316 1317 NewEdgeSetAdaptorBase() : first_edge(1), first_free_edge(1) {} 1318 virtual ~NewEdgeSetAdaptorBase() {} 1319 1320 Edge addEdge(const Node& source, const Node& target) { 1321 int n; 1322 if (first_free_edge == 1) { 1323 n = edges.size(); 1324 edges.push_back(EdgeT()); 1325 } else { 1326 n = first_free_edge; 1327 first_free_edge = edges[first_free_edge].next_in; 1328 } 1329 edges[n].next_in = (*nodes)[target].first_in; 1330 (*nodes)[target].first_in = n; 1331 edges[n].next_out = (*nodes)[source].first_out; 1332 (*nodes)[source].first_out = n; 1333 edges[n].source = source; 1334 edges[n].target = target; 1335 return Edge(n); 1336 } 1337 1338 void erase(const Edge& edge) { 1339 int n = edge.id; 1340 if (edges[n].prev_in != 1) { 1341 edges[edges[n].prev_in].next_in = edges[n].next_in; 1342 } else { 1343 (*nodes)[edges[n].target].first_in = edges[n].next_in; 1344 } 1345 if (edges[n].next_in != 1) { 1346 edges[edges[n].next_in].prev_in = edges[n].prev_in; 1347 } 1348 1349 if (edges[n].prev_out != 1) { 1350 edges[edges[n].prev_out].next_out = edges[n].next_out; 1351 } else { 1352 (*nodes)[edges[n].source].first_out = edges[n].next_out; 1353 } 1354 if (edges[n].next_out != 1) { 1355 edges[edges[n].next_out].prev_out = edges[n].prev_out; 1356 } 1357 1358 } 1359 1360 void first(Node& node) const { 1361 graph>first(node); 1362 } 1363 1364 void next(Node& node) const { 1365 graph>next(node); 1366 } 1367 1368 void first(Edge& edge) const { 1369 Node node; 1370 for (first(node); node != INVALID && (*nodes)[node].first_in == 1; 1371 next(node)); 1372 edge.id = (node == INVALID) ? 1 : (*nodes)[node].first_in; 1373 } 1374 1375 void next(Edge& edge) const { 1376 if (edges[edge.id].next_in != 1) { 1377 edge.id = edges[edge.id].next_in; 1378 } else { 1379 Node node = edges[edge.id].target; 1380 for (next(node); node != INVALID && (*nodes)[node].first_in == 1; 1381 next(node)); 1382 edge.id = (node == INVALID) ? 1 : (*nodes)[node].first_in; 1383 } 1384 } 1385 1386 void firstOut(Edge& edge, const Node& node) const { 1387 edge.id = (*nodes)[node].first_out; 1388 } 1389 1390 void nextOut(Edge& edge) const { 1391 edge.id = edges[edge.id].next_out; 1392 } 1393 1394 void firstIn(Edge& edge, const Node& node) const { 1395 edge.id = (*nodes)[node].first_in; 1396 } 1397 1398 void nextIn(Edge& edge) const { 1399 edge.id = edges[edge.id].next_in; 1400 } 1401 1402 int id(const Node& node) const { return graph>id(node); } 1403 int id(const Edge& edge) const { return edge.id; } 1404 1405 Node fromId(int id, Node) const { return graph>fromId(id, Node()); } 1406 Edge fromId(int id, Edge) const { return Edge(id); } 1407 1408 int maxId(Node) const { return graph>maxId(Node()); }; 1409 int maxId(Edge) const { return edges.size()  1; } 1410 1411 Node source(const Edge& edge) const { return edges[edge.id].source;} 1412 Node target(const Edge& edge) const { return edges[edge.id].target;} 1413 1414 }; 1415 1416 template <typename _Graph> 1417 class NewEdgeSetAdaptor : 1418 public ErasableGraphExtender< 1419 ClearableGraphExtender< 1420 ExtendableGraphExtender< 1421 DefaultMappableGraphExtender< 1422 IterableGraphExtender< 1423 AlterableGraphExtender< 1424 NewEdgeSetAdaptorBase<_Graph> > > > > > > { 1425 1426 public: 1427 1428 typedef ErasableGraphExtender< 1429 ClearableGraphExtender< 1430 ExtendableGraphExtender< 1431 DefaultMappableGraphExtender< 1432 IterableGraphExtender< 1433 AlterableGraphExtender< 1434 NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent; 1435 1436 1437 typedef typename Parent::Node Node; 1438 typedef typename Parent::Edge Edge; 1439 1440 private: 1441 1442 virtual void _clear() { 1443 Parent::edges.clear(); 1444 Parent::first_edge = 1; 1445 Parent::first_free_edge = 1; 1446 Parent::getNotifier(Edge()).clear(); 1447 Parent::getNotifier(Node()).clear(); 1448 } 1449 1450 virtual void _add(const Node& node) { 1451 Parent::getNotifier(Node()).add(node); 1452 } 1453 1454 virtual void _erase(const Node& node) { 1455 Edge edge; 1456 Parent::firstOut(edge, node); 1457 while (edge != INVALID) { 1458 Parent::erase(edge); 1459 Parent::firstOut(edge, node); 1460 } 1461 1462 Parent::firstIn(edge, node); 1463 while (edge != INVALID) { 1464 Parent::erase(edge); 1465 Parent::firstIn(edge, node); 1466 } 1467 1468 Parent::getNotifier(Node()).erase(node); 1469 } 1470 1471 1472 typedef typename Parent::NodesImpl NodesImpl; 1473 1474 NodesImpl nodes; 1475 1476 public: 1477 1478 NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) { 1479 Parent::initalize(_graph, nodes); 1480 } 1481 1482 void clear() { 1483 Parent::edges.clear(); 1484 Parent::first_edge = 1; 1485 Parent::first_free_edge = 1; 1486 1487 Parent::getNotifier(Edge()).clear(); 1488 } 1489 1490 }; 1491 1213 1492 ///@} 1214 1493
Note: See TracChangeset
for help on using the changeset viewer.