equal
deleted
inserted
replaced
53 int first_in,first_out; |
53 int first_in,first_out; |
54 NodeT() : first_in(-1), first_out(-1) {} |
54 NodeT() : first_in(-1), first_out(-1) {} |
55 }; |
55 }; |
56 struct EdgeT |
56 struct EdgeT |
57 { |
57 { |
58 int head, tail, next_in, next_out; |
58 int target, source, next_in, next_out; |
59 //FIXME: is this necessary? |
59 //FIXME: is this necessary? |
60 EdgeT() : next_in(-1), next_out(-1) {} |
60 EdgeT() : next_in(-1), next_out(-1) {} |
61 }; |
61 }; |
62 |
62 |
63 std::vector<NodeT> nodes; |
63 std::vector<NodeT> nodes; |
95 |
95 |
96 /// Maximum edge ID. |
96 /// Maximum edge ID. |
97 ///\sa id(Edge) |
97 ///\sa id(Edge) |
98 int maxId(Edge = INVALID) const { return edges.size()-1; } |
98 int maxId(Edge = INVALID) const { return edges.size()-1; } |
99 |
99 |
100 Node tail(Edge e) const { return edges[e.n].tail; } |
100 Node source(Edge e) const { return edges[e.n].source; } |
101 Node head(Edge e) const { return edges[e.n].head; } |
101 Node target(Edge e) const { return edges[e.n].target; } |
102 |
102 |
103 /// Node ID. |
103 /// Node ID. |
104 |
104 |
105 /// The ID of a valid Node is a nonnegative integer not greater than |
105 /// The ID of a valid Node is a nonnegative integer not greater than |
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
125 return n; |
125 return n; |
126 } |
126 } |
127 |
127 |
128 Edge addEdge(Node u, Node v) { |
128 Edge addEdge(Node u, Node v) { |
129 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... |
129 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... |
130 edges[e.n].tail=u.n; edges[e.n].head=v.n; |
130 edges[e.n].source=u.n; edges[e.n].target=v.n; |
131 edges[e.n].next_out=nodes[u.n].first_out; |
131 edges[e.n].next_out=nodes[u.n].first_out; |
132 edges[e.n].next_in=nodes[v.n].first_in; |
132 edges[e.n].next_in=nodes[v.n].first_in; |
133 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
133 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
134 |
134 |
135 return e; |
135 return e; |
209 } |
209 } |
210 |
210 |
211 Edge _findEdge(Node u,Node v, Edge prev = INVALID) |
211 Edge _findEdge(Node u,Node v, Edge prev = INVALID) |
212 { |
212 { |
213 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
213 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
214 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; |
214 while(e!=-1 && edges[e].source!=v.n) e = edges[e].next_out; |
215 prev.n=e; |
215 prev.n=e; |
216 return prev; |
216 return prev; |
217 } |
217 } |
218 |
218 |
219 }; |
219 }; |
305 |
305 |
306 void rollBack(const SnapShot &s) |
306 void rollBack(const SnapShot &s) |
307 { |
307 { |
308 while(s.edge_num>edges.size()) { |
308 while(s.edge_num>edges.size()) { |
309 edge_observers.erase(Edge(edges.size()-1)); |
309 edge_observers.erase(Edge(edges.size()-1)); |
310 nodes[edges.back().head].first_in=edges.back().next_in; |
310 nodes[edges.back().target].first_in=edges.back().next_in; |
311 nodes[edges.back().tail].first_out=edges.back().next_out; |
311 nodes[edges.back().source].first_out=edges.back().next_out; |
312 edges.pop_back(); |
312 edges.pop_back(); |
313 } |
313 } |
314 //nodes.resize(s.nodes_num); |
314 //nodes.resize(s.nodes_num); |
315 while(s.node_num>nodes.size()) { |
315 while(s.node_num>nodes.size()) { |
316 node_observers.erase(Node(nodes.size()-1)); |
316 node_observers.erase(Node(nodes.size()-1)); |