The graph_factory branch (@ 1321) has been merged to trunk.
3 #ifndef LEMON_LIST_GRAPH_H
4 #define LEMON_LIST_GRAPH_H
6 #include <lemon/erasable_graph_extender.h>
7 #include <lemon/clearable_graph_extender.h>
8 #include <lemon/extendable_graph_extender.h>
10 #include <lemon/idmappable_graph_extender.h>
12 #include <lemon/iterable_graph_extender.h>
14 #include <lemon/alteration_observer_registry.h>
16 #include <lemon/default_map.h>
24 int first_in,first_out;
30 int prev_in, prev_out;
31 int next_in, next_out;
34 std::vector<NodeT> nodes;
40 std::vector<EdgeT> edges;
46 typedef ListGraphBase Graph;
53 Node(int pid) { id = pid;}
57 Node (Invalid) { id = -1; }
58 bool operator==(const Node& node) const {return id == node.id;}
59 bool operator!=(const Node& node) const {return id != node.id;}
60 bool operator<(const Node& node) const {return id < node.id;}
68 Edge(int pid) { id = pid;}
72 Edge (Invalid) { id = -1; }
73 bool operator==(const Edge& edge) const {return id == edge.id;}
74 bool operator!=(const Edge& edge) const {return id != edge.id;}
75 bool operator<(const Edge& edge) const {return id < edge.id;}
81 : nodes(), first_node(-1),
82 first_free_node(-1), edges(), first_free_edge(-1) {}
85 ///it possible to avoid the superfluous memory allocation.
86 void reserveEdge(int n) { edges.reserve(n); };
92 int maxNodeId() const { return nodes.size()-1; }
98 int maxEdgeId() const { return edges.size()-1; }
100 Node tail(Edge e) const { return edges[e.id].tail; }
101 Node head(Edge e) const { return edges[e.id].head; }
104 void first(Node& node) const {
105 node.id = first_node;
108 void next(Node& node) const {
109 node.id = nodes[node.id].next;
113 void first(Edge& e) const {
116 n!=-1 && nodes[n].first_in == -1;
118 e.id = (n == -1) ? -1 : nodes[n].first_in;
121 void next(Edge& edge) const {
122 if (edges[edge.id].next_in != -1) {
123 edge.id = edges[edge.id].next_in;
126 for(n = nodes[edges[edge.id].head].next;
127 n!=-1 && nodes[n].first_in == -1;
129 edge.id = (n == -1) ? -1 : nodes[n].first_in;
133 void firstOut(Edge &e, const Node& v) const {
134 e.id = nodes[v.id].first_out;
136 void nextOut(Edge &e) const {
137 e.id=edges[e.id].next_out;
140 void firstIn(Edge &e, const Node& v) const {
141 e.id = nodes[v.id].first_in;
143 void nextIn(Edge &e) const {
144 e.id=edges[e.id].next_in;
148 static int id(Node v) { return v.id; }
149 static int id(Edge e) { return e.id; }
151 /// Adds a new node to the graph.
153 /// \warning It adds the new node to the front of the list.
154 /// (i.e. the lastly added node becomes the first.)
158 if(first_free_node==-1) {
160 nodes.push_back(NodeT());
163 first_free_node = nodes[n].next;
166 nodes[n].next = first_node;
167 if(first_node != -1) nodes[first_node].prev = n;
171 nodes[n].first_in = nodes[n].first_out = -1;
176 Edge addEdge(Node u, Node v) {
179 if (first_free_edge == -1) {
181 edges.push_back(EdgeT());
184 first_free_edge = edges[n].next_in;
187 edges[n].tail = u.id;
188 edges[n].head = v.id;
190 edges[n].next_out = nodes[u.id].first_out;
191 if(nodes[u.id].first_out != -1) {
192 edges[nodes[u.id].first_out].prev_out = n;
195 edges[n].next_in = nodes[v.id].first_in;
196 if(nodes[v.id].first_in != -1) {
197 edges[nodes[v.id].first_in].prev_in = n;
200 edges[n].prev_in = edges[n].prev_out = -1;
202 nodes[u.id].first_out = nodes[v.id].first_in = n;
207 void erase(const Node& node) {
210 if(nodes[n].next != -1) {
211 nodes[nodes[n].next].prev = nodes[n].prev;
214 if(nodes[n].prev != -1) {
215 nodes[nodes[n].prev].next = nodes[n].next;
217 first_node = nodes[n].next;
220 nodes[n].next = first_free_node;
225 void erase(const Edge& edge) {
228 if(edges[n].next_in!=-1) {
229 edges[edges[n].next_in].prev_in = edges[n].prev_in;
232 if(edges[n].prev_in!=-1) {
233 edges[edges[n].prev_in].next_in = edges[n].next_in;
235 nodes[edges[n].head].first_in = edges[n].next_in;
239 if(edges[n].next_out!=-1) {
240 edges[edges[n].next_out].prev_out = edges[n].prev_out;
243 if(edges[n].prev_out!=-1) {
244 edges[edges[n].prev_out].next_out = edges[n].next_out;
246 nodes[edges[n].tail].first_out = edges[n].next_out;
249 edges[n].next_in = first_free_edge;
257 first_node = first_free_node = first_free_edge = -1;
262 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
263 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
264 typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
265 typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
266 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
267 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
268 typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
270 typedef ErasableListGraphBase ListGraph;