equal
deleted
inserted
replaced
13 |
13 |
14 namespace hugo { |
14 namespace hugo { |
15 |
15 |
16 class SymListGraph; |
16 class SymListGraph; |
17 |
17 |
18 ///A smart graph class. |
18 ///A list graph class. |
19 |
19 |
20 ///This is a simple and fast erasable graph implementation. |
20 ///This is a simple and fast erasable graph implementation. |
21 /// |
21 /// |
22 ///It conforms to the graph interface documented under |
22 ///It conforms to the graph interface documented under |
23 ///the description of \ref GraphSkeleton. |
23 ///the description of \ref GraphSkeleton. |
721 }; |
721 }; |
722 |
722 |
723 }; |
723 }; |
724 |
724 |
725 |
725 |
726 ///A smart graph class. |
726 ///A graph class containing only nodes. |
727 |
727 |
728 ///This is a simple and fast erasable graph implementation. |
728 ///This class implements a graph structure without edges. |
|
729 ///The most useful application of this class is to be the node set of an |
|
730 ///\ref EdgeSet class. |
729 /// |
731 /// |
730 ///It conforms to the graph interface documented under |
732 ///It conforms to the graph interface documented under |
731 ///the description of \ref GraphSkeleton. |
733 ///the description of \ref GraphSkeleton with the exception that you cannot |
732 ///\sa \ref GraphSkeleton. |
734 ///add (or delete) edges. The usual edge iterators are exists, but they are |
|
735 ///always \ref INVALID. |
|
736 ///\sa \ref GraphSkeleton |
|
737 ///\se \ref EdgeSet |
733 class NodeSet { |
738 class NodeSet { |
734 |
739 |
735 //Nodes are double linked. |
740 //Nodes are double linked. |
736 //The free nodes are only single linked using the "next" field. |
741 //The free nodes are only single linked using the "next" field. |
737 struct NodeT |
742 struct NodeT |
1112 }; |
1117 }; |
1113 }; |
1118 }; |
1114 |
1119 |
1115 |
1120 |
1116 |
1121 |
1117 ///This is a simple and fast erasable graph implementation. |
1122 ///Graph structure using a node set of another graph. |
|
1123 |
|
1124 ///This structure can be used to establish another graph over a node set |
|
1125 /// of an existing one. The node iterator will go through the nodes of the |
|
1126 /// original graph, and the NodeMap's of both graphs will convert to |
|
1127 /// each other. |
|
1128 /// |
|
1129 ///\param GG The type of the graph which shares its node set with this class. |
|
1130 ///Its interface must conform with \ref GraphSkeleton. |
1118 /// |
1131 /// |
1119 ///It conforms to the graph interface documented under |
1132 ///It conforms to the graph interface documented under |
1120 ///the description of \ref GraphSkeleton. |
1133 ///the description of \ref GraphSkeleton. |
1121 ///\sa \ref GraphSkeleton. |
1134 ///\sa \ref GraphSkeleton. |
|
1135 ///\sa \ref NodeSet. |
1122 template<typename GG> |
1136 template<typename GG> |
1123 class EdgeSet { |
1137 class EdgeSet { |
1124 |
1138 |
1125 typedef GG NodeGraphType; |
1139 typedef GG NodeGraphType; |
1126 |
1140 |
1189 template <typename T> class NodeMap; |
1203 template <typename T> class NodeMap; |
1190 template <typename T> class EdgeMap; |
1204 template <typename T> class EdgeMap; |
1191 |
1205 |
1192 public: |
1206 public: |
1193 |
1207 |
1194 EdgeSet(const NodeGraphType &_G) : G(_G), |
1208 EdgeSet(NodeGraphType &_G) : G(_G), |
1195 nodes(_G), edges(), |
1209 nodes(_G), edges(), |
1196 first_free_edge(-1) {} |
1210 first_free_edge(-1) { } |
1197 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), |
1211 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), |
1198 first_free_edge(_g.first_free_edge) {} |
1212 first_free_edge(_g.first_free_edge) { } |
1199 |
1213 |
1200 ~EdgeSet() |
1214 ~EdgeSet() |
1201 { |
1215 { |
1202 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
1216 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
1203 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
1217 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
1285 else { |
1299 else { |
1286 n = first_free_edge; |
1300 n = first_free_edge; |
1287 first_free_edge = edges[n].next_in; |
1301 first_free_edge = edges[n].next_in; |
1288 } |
1302 } |
1289 |
1303 |
1290 edges[n].tail = u.n; edges[n].head = v.n; |
1304 edges[n].tail = u; edges[n].head = v; |
1291 |
1305 |
1292 edges[n].next_out = nodes[u.n].first_out; |
1306 edges[n].next_out = nodes[u].first_out; |
1293 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; |
1307 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; |
1294 edges[n].next_in = nodes[v.n].first_in; |
1308 edges[n].next_in = nodes[v].first_in; |
1295 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; |
1309 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; |
1296 edges[n].prev_in = edges[n].prev_out = -1; |
1310 edges[n].prev_in = edges[n].prev_out = -1; |
1297 |
1311 |
1298 nodes[u.n].first_out = nodes[v.n].first_in = n; |
1312 nodes[u].first_out = nodes[v].first_in = n; |
1299 |
1313 |
1300 Edge e; e.n=n; |
1314 Edge e; e.n=n; |
1301 |
1315 |
1302 //Update dynamic maps |
1316 //Update dynamic maps |
1303 for(typename std::vector<DynMapBase<Edge> * >::iterator |
1317 for(typename std::vector<DynMapBase<Edge> * >::iterator |
1371 class NodeIt : public NodeGraphType::NodeIt { |
1385 class NodeIt : public NodeGraphType::NodeIt { |
1372 friend class EdgeSet; |
1386 friend class EdgeSet; |
1373 public: |
1387 public: |
1374 NodeIt() : NodeGraphType::NodeIt() { } |
1388 NodeIt() : NodeGraphType::NodeIt() { } |
1375 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} |
1389 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} |
1376 NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { } |
1390 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } |
1377 NodeIt(const typename NodeGraphType::NodeIt &n) |
1391 NodeIt(const typename NodeGraphType::NodeIt &n) |
1378 : NodeGraphType::NodeIt(n) {} |
1392 : NodeGraphType::NodeIt(n) {} |
1379 operator Node() { return Node(*this);} |
1393 operator Node() { return Node(*this);} |
1380 }; |
1394 }; |
1381 |
1395 |
1449 NodeMap(const typename NodeGraphType::NodeMap<T> &m) |
1463 NodeMap(const typename NodeGraphType::NodeMap<T> &m) |
1450 : NodeGraphType::NodeMap<T>(m) { } |
1464 : NodeGraphType::NodeMap<T>(m) { } |
1451 |
1465 |
1452 ///\todo It can copy between different types. |
1466 ///\todo It can copy between different types. |
1453 /// |
1467 /// |
1454 template<typename TT> friend class NodeMap; |
1468 template<typename TT> |
1455 NodeMap(const typename NodeGraphType::NodeMap<TT> &m) |
1469 NodeMap(const typename NodeGraphType::NodeMap<TT> &m) |
1456 : NodeGraphType::NodeMap<T>(m) { } |
1470 : NodeGraphType::NodeMap<T>(m) { } |
1457 }; |
1471 }; |
1458 |
1472 |
1459 template <typename T> class EdgeMap : public DynMapBase<Edge> |
1473 template <typename T> class EdgeMap : public DynMapBase<Edge> |