Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/graph_extender.h
changeset 2255 4a9cc8c800ae
parent 2222 a24939ee343c
child 2260 4274224f8a7d
equal deleted inserted replaced
22:355dbb0f6352 23:9408b60d4b4c 
   728   ///
 
   728   ///
 
   729   /// \brief Extender for the BpUGraphs
 
   729   /// \brief Extender for the BpUGraphs
 
   730   template <typename Base>
 
   730   template <typename Base>
 
   731   class BpUGraphExtender : public Base {
 
   731   class BpUGraphExtender : public Base {
 
   732   public:
 
   732   public:
 
       
   733 
   733     typedef Base Parent;
 
   734     typedef Base Parent;
 
   734     typedef BpUGraphExtender Graph;
 
   735     typedef BpUGraphExtender Graph;
 
   735 
   736 
   736     typedef typename Parent::Node Node;
 
   737     typedef typename Parent::Node Node;
 
       
   738     typedef typename Parent::ANode ANode;
 
       
   739     typedef typename Parent::BNode BNode;
 
       
   740     typedef typename Parent::Edge Edge;
 
   737     typedef typename Parent::UEdge UEdge;
 
   741     typedef typename Parent::UEdge UEdge;
 
   738 
   742 
   739 
   743 
   740     using Parent::first;
 
   744     Node oppositeNode(const Node& node, const UEdge& edge) const {
 
   741     using Parent::next;
 
   745       return Parent::aNode(edge) == node ? 
   742 
   746 	Parent::bNode(edge) : Parent::aNode(edge);
 
   743     using Parent::id;
 
   747     }
 
   744 
   748 
   745     class ANode : public Node {
 
   749     using Parent::direct;
 
   746       friend class BpUGraphExtender;
 
       
   747     public:
 
       
   748       ANode() {}
 
       
   749       ANode(const Node& node) : Node(node) {
 
       
   750 	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
       
   751 		     typename Parent::NodeSetError());
 
       
   752       }
 
       
   753       ANode(Invalid) : Node(INVALID) {}
 
       
   754     };
 
       
   755 
       
   756     void first(ANode& node) const {
 
       
   757       Parent::firstANode(static_cast<Node&>(node));
 
       
   758     }
 
       
   759     void next(ANode& node) const {
 
       
   760       Parent::nextANode(static_cast<Node&>(node));
 
       
   761     }
 
       
   762 
       
   763     int id(const ANode& node) const {
 
       
   764       return Parent::aNodeId(node);
 
       
   765     }
 
       
   766 
       
   767     class BNode : public Node {
 
       
   768       friend class BpUGraphExtender;
 
       
   769     public:
 
       
   770       BNode() {}
 
       
   771       BNode(const Node& node) : Node(node) {
 
       
   772 	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
 
       
   773 		     typename Parent::NodeSetError());
 
       
   774       }
 
       
   775       BNode(Invalid) : Node(INVALID) {}
 
       
   776     };
 
       
   777 
       
   778     void first(BNode& node) const {
 
       
   779       Parent::firstBNode(static_cast<Node&>(node));
 
       
   780     }
 
       
   781     void next(BNode& node) const {
 
       
   782       Parent::nextBNode(static_cast<Node&>(node));
 
       
   783     }
 
       
   784   
       
   785     int id(const BNode& node) const {
 
       
   786       return Parent::aNodeId(node);
 
       
   787     }
 
       
   788 
       
   789     Node source(const UEdge& edge) const {
 
       
   790       return aNode(edge);
 
       
   791     }
 
       
   792     Node target(const UEdge& edge) const {
 
       
   793       return bNode(edge);
 
       
   794     }
 
       
   795 
       
   796     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
 
       
   797       if (Parent::aNode(node)) {
 
       
   798 	Parent::firstFromANode(edge, node);
 
       
   799 	direction = true;
 
       
   800       } else {
 
       
   801 	Parent::firstFromBNode(edge, node);
 
       
   802 	direction = static_cast<UEdge&>(edge) == INVALID;
 
       
   803       }
 
       
   804     }
 
       
   805     void nextInc(UEdge& edge, bool& direction) const {
 
       
   806       if (direction) {
 
       
   807 	Parent::nextFromANode(edge);
 
       
   808       } else {
 
       
   809 	Parent::nextFromBNode(edge);
 
       
   810 	if (edge == INVALID) direction = true;
 
       
   811       }
 
       
   812     }
 
       
   813 
       
   814     class Edge : public UEdge {
 
       
   815       friend class BpUGraphExtender;
 
       
   816     protected:
 
       
   817       bool forward;
 
       
   818 
       
   819       Edge(const UEdge& edge, bool _forward)
 
       
   820 	: UEdge(edge), forward(_forward) {}
 
       
   821 
       
   822     public:
 
       
   823       Edge() {}
 
       
   824       Edge (Invalid) : UEdge(INVALID), forward(true) {}
 
       
   825       bool operator==(const Edge& i) const {
 
       
   826 	return UEdge::operator==(i) && forward == i.forward;
 
       
   827       }
 
       
   828       bool operator!=(const Edge& i) const {
 
       
   829 	return UEdge::operator!=(i) || forward != i.forward;
 
       
   830       }
 
       
   831       bool operator<(const Edge& i) const {
 
       
   832 	return UEdge::operator<(i) || 
       
   833 	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));
 
       
   834       }
 
       
   835     };
 
       
   836 
       
   837     void first(Edge& edge) const {
 
       
   838       Parent::first(static_cast<UEdge&>(edge));
 
       
   839       edge.forward = true;
 
       
   840     }
 
       
   841 
       
   842     void next(Edge& edge) const {
 
       
   843       if (!edge.forward) {
 
       
   844 	Parent::next(static_cast<UEdge&>(edge));
 
       
   845       }
 
       
   846       edge.forward = !edge.forward;
 
       
   847     }
 
       
   848 
       
   849     void firstOut(Edge& edge, const Node& node) const {
 
       
   850       if (Parent::aNode(node)) {
 
       
   851 	Parent::firstFromANode(edge, node);
 
       
   852 	edge.forward = true;
 
       
   853       } else {
 
       
   854 	Parent::firstFromBNode(edge, node);
 
       
   855 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
 
       
   856       }
 
       
   857     }
 
       
   858     void nextOut(Edge& edge) const {
 
       
   859       if (edge.forward) {
 
       
   860 	Parent::nextFromANode(edge);
 
       
   861       } else {
 
       
   862 	Parent::nextFromBNode(edge);
 
       
   863         edge.forward = static_cast<UEdge&>(edge) == INVALID;
 
       
   864       }
 
       
   865     }
 
       
   866 
       
   867     void firstIn(Edge& edge, const Node& node) const {
 
       
   868       if (Parent::bNode(node)) {
 
       
   869 	Parent::firstFromBNode(edge, node);
 
       
   870 	edge.forward = true;	
       
   871       } else {
 
       
   872 	Parent::firstFromANode(edge, node);
 
       
   873 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
 
       
   874       }
 
       
   875     }
 
       
   876     void nextIn(Edge& edge) const {
 
       
   877       if (edge.forward) {
 
       
   878 	Parent::nextFromBNode(edge);
 
       
   879       } else {
 
       
   880 	Parent::nextFromANode(edge);
 
       
   881 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
 
       
   882       }
 
       
   883     }
 
       
   884 
       
   885     Node source(const Edge& edge) const {
 
       
   886       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
 
       
   887     }
 
       
   888     Node target(const Edge& edge) const {
 
       
   889       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
 
       
   890     }
 
       
   891 
       
   892     int id(const Edge& edge) const {
 
       
   893       return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 
       
   894         (edge.forward ? 0 : 1);
 
       
   895     }
 
       
   896     Edge edgeFromId(int id) const {
 
       
   897       return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
 
       
   898     }
 
       
   899     int maxEdgeId() const {
 
       
   900       return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
 
       
   901     }
 
       
   902 
       
   903     bool direction(const Edge& edge) const {
 
       
   904       return edge.forward;
 
       
   905     }
 
       
   906 
       
   907     Edge direct(const UEdge& edge, bool direction) const {
 
       
   908       return Edge(edge, direction);
 
       
   909     }
 
       
   910 
       
   911     int edgeNum() const {
 
       
   912       return 2 * Parent::uEdgeNum();
 
       
   913     }
 
       
   914 
       
   915     int uEdgeNum() const {
 
       
   916       return Parent::uEdgeNum();
 
       
   917     }
 
       
   918 
       
   919     Node oppositeNode(const UEdge& edge, const Node& node) const {
 
       
   920       return source(edge) == node ? 
       
   921 	target(edge) : source(edge);
 
       
   922     }
 
       
   923 
       
   924     Edge direct(const UEdge& edge, const Node& node) const {
 
   750     Edge direct(const UEdge& edge, const Node& node) const {
 
   925       return Edge(edge, node == Parent::source(edge));
 
   751       return Parent::direct(edge, node == Parent::source(edge));
 
   926     }
 
   752     }
 
   927 
   753 
   928     Edge oppositeEdge(const Edge& edge) const {
 
   754     Edge oppositeEdge(const Edge& edge) const {
 
   929       return Parent::direct(edge, !Parent::direction(edge));
 
   755       return direct(edge, !Parent::direction(edge));
 
   930     }
 
   756     }
 
   931 
   757     
   932 
       
   933     int maxId(Node) const {
 
   758     int maxId(Node) const {
 
   934       return Parent::maxNodeId();
 
   759       return Parent::maxNodeId();
 
   935     }
 
   760     }
 
   936     int maxId(BNode) const {
 
   761     int maxId(BNode) const {
 
   937       return Parent::maxBNodeId();
 
   762       return Parent::maxBNodeId();
 
   938     }
 
   763     }
 
   939     int maxId(ANode) const {
 
   764     int maxId(ANode) const {
 
   940       return Parent::maxANodeId();
 
   765       return Parent::maxANodeId();
 
   941     }
 
   766     }
 
   942     int maxId(Edge) const {
 
   767     int maxId(Edge) const {
 
   943       return maxEdgeId();
 
   768       return Parent::maxEdgeId();
 
   944     }
 
   769     }
 
   945     int maxId(UEdge) const {
 
   770     int maxId(UEdge) const {
 
   946       return Parent::maxUEdgeId();
 
   771       return Parent::maxUEdgeId();
 
   947     }
 
   772     }
 
   948 
   773 
   949 
   774 
   950     Node fromId(int id, Node) const {
 
   775     Node fromId(int id, Node) const {
 
   951       return Parent::nodeFromId(id);
 
   776       return Parent::nodeFromId(id);
 
   952     }
 
   777     }
 
   953     ANode fromId(int id, ANode) const {
 
   778     ANode fromId(int id, ANode) const {
 
   954       return Parent::fromANodeId(id);
 
   779       return Parent::nodeFromANodeId(id);
 
   955     }
 
   780     }
 
   956     BNode fromId(int id, BNode) const {
 
   781     BNode fromId(int id, BNode) const {
 
   957       return Parent::fromBNodeId(id);
 
   782       return Parent::nodeFromBNodeId(id);
 
   958     }
 
   783     }
 
   959     Edge fromId(int id, Edge) const {
 
   784     Edge fromId(int id, Edge) const {
 
   960       return Parent::edgeFromId(id);
 
   785       return Parent::edgeFromId(id);
 
   961     }
 
   786     }
 
   962     UEdge fromId(int id, UEdge) const {
 
   787     UEdge fromId(int id, UEdge) const {
 
  1302       }
 
  1127       }
 
  1303     
  1128     
  1304       template <typename CMap>
 
  1129       template <typename CMap>
 
  1305       NodeMap& operator=(const CMap& cmap) {
 
  1130       NodeMap& operator=(const CMap& cmap) {
 
  1306 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
 
  1131 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
 
  1307 	const typename Parent::Notifier* notifier = Parent::getNotifier();
 
  1132         aNodeMap = cmap;
 
  1308 	Edge it;
 
  1133         bNodeMap = cmap;
 
  1309 	for (graph.first(it); it != INVALID; graph.next(it)) {
 
  1134         return *this;
 
  1310 	  Parent::set(it, cmap[it]);
 
       
  1311 	}
 
       
  1312 	return *this;
 
       
  1313       }
 
  1135       }
 
  1314 
  1136 
  1315       ConstReference operator[](const Key& node) const {
 
  1137       ConstReference operator[](const Key& node) const {
 
  1316 	if (Parent::aNode(node)) {
 
  1138 	if (Parent::aNode(node)) {
 
  1317 	  return aNodeMap[node];
 
  1139 	  return aNodeMap[node];
 
  1457     UEdge addEdge(const Node& source, const Node& target) {
 
  1279     UEdge addEdge(const Node& source, const Node& target) {
 
  1458       UEdge uedge = Parent::addEdge(source, target);
 
  1280       UEdge uedge = Parent::addEdge(source, target);
 
  1459       getNotifier(UEdge()).add(uedge);
 
  1281       getNotifier(UEdge()).add(uedge);
 
  1460     
  1282     
  1461       std::vector<Edge> edges;
 
  1283       std::vector<Edge> edges;
 
  1462       edges.push_back(direct(uedge, true));
 
  1284       edges.push_back(Parent::direct(uedge, true));
 
  1463       edges.push_back(direct(uedge, false));
 
  1285       edges.push_back(Parent::direct(uedge, false));
 
  1464       getNotifier(Edge()).add(edges);
 
  1286       getNotifier(Edge()).add(edges);
 
  1465     
  1287     
  1466       return uedge;
 
  1288       return uedge;
 
  1467     }
 
  1289     }
 
  1468 
  1290 
  1497       Parent::erase(node);
 
  1319       Parent::erase(node);
 
  1498     }
 
  1320     }
 
  1499     
  1321     
  1500     void erase(const UEdge& uedge) {
 
  1322     void erase(const UEdge& uedge) {
 
  1501       std::vector<Edge> edges;
 
  1323       std::vector<Edge> edges;
 
  1502       edges.push_back(direct(uedge, true));
 
  1324       edges.push_back(Parent::direct(uedge, true));
 
  1503       edges.push_back(direct(uedge, false));
 
  1325       edges.push_back(Parent::direct(uedge, false));
 
  1504       getNotifier(Edge()).erase(edges);
 
  1326       getNotifier(Edge()).erase(edges);
 
  1505       getNotifier(UEdge()).erase(uedge);
 
  1327       getNotifier(UEdge()).erase(uedge);
 
  1506       Parent::erase(uedge);
 
  1328       Parent::erase(uedge);
 
  1507     }
 
  1329     }
 
  1508 
  1330 
  1524     }
 
  1346     }
 
  1525 
  1347 
  1526     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
 
  1348     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
 
  1527       UEdge uedge = Parent::findUEdge(u, v, prev);
 
  1349       UEdge uedge = Parent::findUEdge(u, v, prev);
 
  1528       if (uedge != INVALID) {
 
  1350       if (uedge != INVALID) {
 
  1529         return direct(uedge, Parent::aNode(u));
 
  1351         return Parent::direct(uedge, Parent::aNode(u));
 
  1530       } else {
 
  1352       } else {
 
  1531         return INVALID;
 
  1353         return INVALID;
 
  1532       }
 
  1354       }
 
  1533     }
 
  1355     }
 
  1534 
  1356
lemon-0.x