lemon-1.3: comparison lemon/list

equal deleted inserted replaced

-:1912fc6fd8b2
+:63e7900277b7
 bool operator==(const Node& node) const {return id == node.id;}
 bool operator!=(const Node& node) const {return id != node.id;}
 bool operator<(const Node& node) const {return id < node.id;}
 };
+class RedNode : public Node {
+friend class ListBpGraphBase;
+protected:
+explicit RedNode(int pid) : Node(pid) {}
+public:
+RedNode() {}
+RedNode(const RedNode& node) : Node(node) {}
+RedNode(Invalid) : Node(INVALID){}
+};
+class BlueNode : public Node {
+friend class ListBpGraphBase;
+protected:
+explicit BlueNode(int pid) : Node(pid) {}
+public:
+BlueNode() {}
+BlueNode(const BlueNode& node) : Node(node) {}
+BlueNode(Invalid) : Node(INVALID){}
+};
 class Edge {
 friend class ListBpGraphBase;
 protected:
 int id;
 bool red(Node n) const { return nodes[n.id].red; }
 bool blue(Node n) const { return !nodes[n.id].red; }
+static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
+static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
 int maxNodeId() const { return nodes.size()-1; }
 int maxRedId() const { return max_red; }
 int maxBlueId() const { return max_blue; }
 int maxEdgeId() const { return arcs.size() / 2 - 1; }
 int maxArcId() const { return arcs.size()-1; }
 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
 Node target(Arc e) const { return Node(arcs[e.id].target); }
-Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
+RedNode redNode(Edge e) const {
-Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
+return RedNode(arcs[2 * e.id].target);
+}
+BlueNode blueNode(Edge e) const {
+return BlueNode(arcs[2 * e.id + 1].target);
+}
 static bool direction(Arc e) {
 return (e.id & 1) == 1;
 }
 void next(Node& node) const {
 node.id = nodes[node.id].next;
 }
-void firstRed(Node& node) const {
+void first(RedNode& node) const {
 node.id = first_red;
 }
-void nextRed(Node& node) const {
+void next(RedNode& node) const {
 node.id = nodes[node.id].partition_next;
 }
-void firstBlue(Node& node) const {
+void first(BlueNode& node) const {
 node.id = first_blue;
 }
-void nextBlue(Node& node) const {
+void next(BlueNode& node) const {
 node.id = nodes[node.id].partition_next;
 }
 void first(Arc& e) const {
 int n = first_node;
 d = true;
 }
 }
 static int id(Node v) { return v.id; }
-int redId(Node v) const {
+int id(RedNode v) const { return nodes[v.id].partition_index; }
-LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
+int id(BlueNode v) const { return nodes[v.id].partition_index; }
-return nodes[v.id].partition_index;
-}
-int blueId(Node v) const {
-LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
-return nodes[v.id].partition_index;
-}
 static int id(Arc e) { return e.id; }
 static int id(Edge e) { return e.id; }
 static Node nodeFromId(int id) { return Node(id);}
 static Arc arcFromId(int id) { return Arc(id);}
 bool valid(Edge e) const {
 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
 arcs[2 * e.id].prev_out != -2;
 }
-Node addRedNode() {
+RedNode addRedNode() {
 int n;
 if(first_free_red==-1) {
 n = nodes.size();
 nodes.push_back(NodeT());
 first_red = n;
 nodes[n].partition_prev = -1;
 nodes[n].first_out = -1;
-return Node(n);
+return RedNode(n);
 }
-Node addBlueNode() {
+BlueNode addBlueNode() {
 int n;
 if(first_free_blue==-1) {
 n = nodes.size();
 nodes.push_back(NodeT());
 first_blue = n;
 nodes[n].partition_prev = -1;
 nodes[n].first_out = -1;
-return Node(n);
+return BlueNode(n);
 }
 Edge addEdge(Node u, Node v) {
 int n;
 max_red = max_blue = first_free_red = first_free_blue = -1;
 }
 protected:
-void changeRed(Edge e, Node n) {
+void changeRed(Edge e, RedNode n) {
-LEMON_DEBUG(nodes[n].red, "Node has to be red");
 if(arcs[(2 * e.id) | 1].next_out != -1) {
 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
 arcs[(2 * e.id) | 1].prev_out;
 }
 if(arcs[(2 * e.id) | 1].prev_out != -1) {
 arcs[(2 * e.id) | 1].prev_out = -1;
 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
 nodes[n.id].first_out = ((2 * e.id) | 1);
 }
-void changeBlue(Edge e, Node n) {
+void changeBlue(Edge e, BlueNode n) {
-LEMON_DEBUG(nodes[n].red, "Node has to be blue");
+if(arcs[2 * e.id].next_out != -1) {
-if(arcs[2 * e.id].next_out != -1) {
 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
 }
 if(arcs[2 * e.id].prev_out != -1) {
 arcs[arcs[2 * e.id].prev_out].next_out =
 arcs[2 * e.id].next_out;
 /// \brief Add a new red node to the graph.
 ///
 /// This function adds a red new node to the graph.
 /// \return The new node.
-Node addRedNode() { return Parent::addRedNode(); }
+RedNode addRedNode() { return Parent::addRedNode(); }
 /// \brief Add a new blue node to the graph.
 ///
 /// This function adds a blue new node to the graph.
 /// \return The new node.
-Node addBlueNode() { return Parent::addBlueNode(); }
+BlueNode addBlueNode() { return Parent::addBlueNode(); }
 /// \brief Add a new edge to the graph.
 ///
 /// This function adds a new edge to the graph between nodes
 /// \c u and \c v with inherent orientation from node \c u to
 /// node \c v.
 /// \return The new edge.
-Edge addEdge(Node u, Node v) {
+Edge addEdge(RedNode u, BlueNode v) {
+return Parent::addEdge(u, v);
+}
+Edge addEdge(BlueNode v, RedNode u) {
 return Parent::addEdge(u, v);
 }
 ///\brief Erase a node from the graph.
 ///
 ///changed edge are invalidated and all other iterators whose
 ///base node is the changed node are also invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
-void changeRed(Edge e, Node n) {
+void changeRed(Edge e, RedNode n) {
-Parent::changeRed(e,n);
+Parent::changeRed(e, n);
 }
 /// \brief Change the blue node of an edge.
 ///
 /// This function changes the blue node of the given edge \c e to \c n.
 ///
 ///all other iterators whose base node is the changed node are also
 ///invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
-void changeBlue(Edge e, Node n) {
+void changeBlue(Edge e, BlueNode n) {
-Parent::changeBlue(e,n);
+Parent::changeBlue(e, n);
 }
 ///Clear the graph.
 ///This function erases all nodes and arcs from the graph.

changeset 1029	374a9519986b
parent 1021	a12cca3ad15a
child 1049	7bf489cf624e