OdinAI

- Main Page
- Namespaces
- Classes
- Files
- Examples

- File List

All Classes Namespaces Functions Variables
SparseGraph.h
1 #ifndef ODINAI_SPARSE_GRAPH_H_
2 #define ODINAI_SPARSE_GRAPH_H_
3
4 #include <vector>
5 #include <list>
6 #include <iostream>
7 #include "DebugUtil.h"
8 #include "SharedDefs.h"
9
10 namespace OdinAI
11 {
12
18 template<class NODE_TYPE, class EDGE_TYPE>
19 class SparseGraph
20 {
21 public:
22 typedef NODE_TYPE NodeType;
23 typedef EDGE_TYPE EdgeType;
24
25 typedef std::vector<NODE_TYPE> NodeVector;
26 typedef std::list<EDGE_TYPE> EdgeList;
27 typedef std::vector<EdgeList> EdgeListVector;
28
29 SparseGraph(bool digraph) : m_nextNodeIndex(0), m_isDigraph(digraph) {}
30
35 const NodeType &GetNode(int index) const;
36
41 NodeType &GetNode(int index);
42
47 const EdgeType &GetEdge(int from, int to) const;
48
53 EdgeType &GetEdge(int from, int to);
54
55 int GetNextNodeIndex() const;
56
60 int AddNode(const NodeType &node);
61
65 void RemoveNode(int node);
66
70 void AddEdge(const EdgeType &edge);
71
75 void RemoveEdge(int from, int to);
76
80 int NumNodes() const;
81
85 int NumActiveNodes() const;
86
90 int NumEdges() const;
91
95 bool IsDigraph() const {return m_isDigraph;}
96
100 bool IsEmpty() const {return m_nextNodeIndex <= 0;}
101
105 bool IsPresent(int node) const;
106
110 void Clear();
111
112 class EdgeIterator
113 {
114 public:
115 EdgeIterator(SparseGraph<NodeType, EdgeType> &graph, int node) : m_graph(graph), m_nodeIndex(node)
116 {
117 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
118 }
119
120 EdgeType *Begin()
121 {
122 if(m_graph.m_edges[m_nodeIndex].size() < 1)
123 {
124 return 0;
125 }
126
127 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
128 return &(*m_currentEdge);
129 }
130
131 EdgeType *Next()
132 {
133 ++m_currentEdge;
134 if(End())
135 {
136 return 0;
137 }
138
139 return &(*m_currentEdge);
140 }
141
142 bool End()
143 {
144 return m_currentEdge == m_graph.m_edges[m_nodeIndex].end();
145 }
146 private:
147 SparseGraph<NodeType, EdgeType> &m_graph;
148 const int m_nodeIndex;
149 typename EdgeList::iterator m_currentEdge;
150 };
151
152 friend EdgeIterator;
153
154 class ConstEdgeIterator
155 {
156 public:
157 ConstEdgeIterator(const SparseGraph<NodeType, EdgeType> &graph, int node) : m_graph(graph), m_nodeIndex(node)
158 {
159 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
160 }
161
162 const EdgeType *Begin()
163 {
164 if(m_graph.m_edges[m_nodeIndex].size() < 1)
165 {
166 return 0;
167 }
168
169 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
170
171 return &(*m_currentEdge);
172 }
173
174 const EdgeType *Next()
175 {
176 ++m_currentEdge;
177 if(End())
178 {
179 return 0;
180 }
181
182 return &(*m_currentEdge);
183 }
184
185 bool End()
186 {
187 return m_currentEdge == m_graph.m_edges[m_nodeIndex].end();
188 }
189 private:
190 const SparseGraph<NodeType, EdgeType> &m_graph;
191 const int m_nodeIndex;
192 typename EdgeList::const_iterator m_currentEdge;
193 };
194 friend ConstEdgeIterator;
195
196 class NodeIterator
197 {
198 public:
199 NodeIterator(SparseGraph<NodeType, EdgeType> &graph, int node) : m_graph(graph), m_nodeIndex(node)
200 {
201 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
202 }
203
204 NodeType *Begin()
205 {
206 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
207
208 NextValidNode(m_currentNode);
209
210 return &(*m_currentNode);
211 }
212
213 NodeType *Next()
214 {
215 ++m_currentNode;
216 if(End())
217 {
218 return 0;
219 }
220
221 NextValidNode(m_currentNode);
222
223 return &(*m_currentNode);
224 }
225
226 bool End()
227 {
228 return m_currentNode == m_graph.m_nodes.end();
229 }
230 private:
231 //If we remove a node while iterating through the vector
232 //then we need to skip these nodes.
233 void NextValidNode(typename NodeVector::iterator curNode)
234 {
235 if(curNode == m_graph.m_nodes.end() || curNode->GetIndex() != INVALID_NODE_INDEX)
236 return;
237
238 while(curNode->GetIndex() == INVALID_NODE_INDEX)
239 {
240 ++curNode;
241
242 if(curNode == m_graph.m_nodes.end())
243 {
244 break;
245 }
246 }
247 }
248
249 SparseGraph<NodeType, EdgeType> &m_graph;
250 typename NodeVector::iterator m_currentNode;
251 };
252 friend NodeIterator;
253
254 class ConstNodeIterator
255 {
256 public:
257 ConstNodeIterator(const SparseGraph<NodeType, EdgeType> &graph, int node) : m_graph(graph), m_nodeIndex(node)
258 {
259 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
260 }
261
262 const NodeType *Begin()
263 {
264 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
265
266 NextValidNode(m_currentNode);
267
268 return &(*m_currentNode);
269 }
270
271 const NodeType *Next()
272 {
273 ++m_currentNode;
274 if(End())
275 {
276 return 0;
277 }
278
279 NextValidNode(m_currentNode);
280
281 return &(*m_currentNode);
282 }
283
284 bool End()
285 {
286 return m_currentNode == m_graph.m_nodes.end();
287 }
288 private:
289 //If we remove a node while iterating through the vector
290 //then we need to skip these nodes.
291 void NextValidNode(typename NodeVector::const_iterator curNode)
292 {
293 if(curNode == m_graph.m_nodes.end() || curNode->GetIndex() != INVALID_NODE_INDEX)
294 return;
295
296 while(curNode->GetIndex() == INVALID_NODE_INDEX)
297 {
298 ++curNode;
299
300 if(curNode == m_graph.m_nodes.end())
301 {
302 break;
303 }
304 }
305 }
306
307 const SparseGraph<NodeType, EdgeType> &m_graph;
308 typename NodeVector::const_iterator m_currentNode;
309 };
310 friend ConstNodeIterator;
311
312 private:
313 NodeVector m_nodes;
314 EdgeListVector m_edges;
315
316 int m_nextNodeIndex;
317
318 bool m_isDigraph;
319 };
320
321 template<class NODE_TYPE, class EDGE_TYPE>
322 const NODE_TYPE &SparseGraph<NODE_TYPE, EDGE_TYPE>::GetNode(int index) const
323 {
324 Assert(m_nextNodeIndex > index && index != INVALID_NODE_INDEX
325 && "SparseGraph::GetNode() Index is invalid.");
326 return m_nodes.at(index);
327 }
328
329 template<class NODE_TYPE, class EDGE_TYPE>
330 NODE_TYPE &SparseGraph<NODE_TYPE, EDGE_TYPE>::GetNode(int index)
331 {
332 Assert(m_nextNodeIndex > index && index != INVALID_NODE_INDEX
333 && "SparseGraph::GetNode() Index is invalid.");
334 return m_nodes[index];
335 }
336
337 template<class NODE_TYPE, class EDGE_TYPE>
338 EDGE_TYPE &SparseGraph<NODE_TYPE, EDGE_TYPE>::GetEdge(int from, int to)
339 {
340 Assert(m_nextNodeIndex > from && from != INVALID_NODE_INDEX &&
341 "SparseGraph::GetEdge() invalid 'from' node.");
342 Assert(m_nextNodeIndex > to && to != INVALID_NODE_INDEX &&
343 "SparseGraph::GetEdge() invalid 'to' node.");
344
345 EdgeList &edgeList = m_edges[from];
346 for(EdgeList::iterator iter = edgeList.begin();
347 iter != edgeList.end();++iter)
348 {
349 if(iter->To() == to)
350 {
351 return (*iter);
352 }
353 }
354
355 Assert(false && "SparseGraph::GetEdge(): Could not find edge!");
356 }
357
358 template<class NODE_TYPE, class EDGE_TYPE>
359 const EDGE_TYPE &SparseGraph<NODE_TYPE, EDGE_TYPE>::GetEdge(int from, int to) const
360 {
361 Assert(m_nextNodeIndex > from && from != INVALID_NODE_INDEX &&
362 "SparseGraph::GetEdge() invalid 'from' node.");
363 Assert(m_nextNodeIndex > to && to != INVALID_NODE_INDEX &&
364 "SparseGraph::GetEdge() invalid 'to' node.");
365
366 EdgeList &edgeList = m_edges[from];
367 for(EdgeList::const_iterator iter = edgeList.begin();
368 iter != edgeList.end();++iter)
369 {
370 if(iter->To() == to)
371 {
372 return (*iter);
373 }
374 }
375
376 Assert(false && "SparseGraph::GetEdge(): Could not find edge!");
377 }
378
379 template<class NODE_TYPE, class EDGE_TYPE>
380 int SparseGraph<NODE_TYPE, EDGE_TYPE>::GetNextNodeIndex() const
381 {
382 return m_nextNodeIndex;
383 }
384
385 template<class NODE_TYPE, class EDGE_TYPE>
386 int SparseGraph<NODE_TYPE, EDGE_TYPE>::AddNode(const NODE_TYPE &node)
387 {
388 if(node.GetIndex() < m_nextNodeIndex)
389 {
390 Assert(m_nodes[node.GetIndex()].GetIndex() == INVALID_NODE_INDEX
391 && "SparseGraph::AddNode() could not replace the node.");
392
393 m_nodes[node.GetIndex()] = node;
394
395 return m_nextNodeIndex;
396 }
397 else
398 {
399 Assert(node.GetIndex() == m_nextNodeIndex &&
400 "SparseGraph::AddNode() could not add node, since it had an invalid index.");
401
402 m_nodes.push_back(node);
403 m_edges.resize(++m_nextNodeIndex);
404 return m_nextNodeIndex;
405 }
406 }
407
408 template<class NODE_TYPE, class EDGE_TYPE>
409 void SparseGraph<NODE_TYPE, EDGE_TYPE>::RemoveNode(int node)
410 {
411 Assert(node < m_nextNodeIndex && "SparseGraph::RemoveNode() Invalid node index.");
412 m_nodes[node].SetIndex(INVALID_NODE_INDEX);
413
414 if(!m_isDigraph)
415 {
416 //Remove all neighbour edges leading to this node.
417 for(EdgeList::iterator fromEdge = m_edges[node].begin();
418 fromEdge != m_edges[node].end();++fromEdge)
419 {
420 for(EdgeList::iterator toEdge = m_edges[fromEdge->To()].begin();
421 toEdge != m_edges[fromEdge->To()].end();++toEdge)
422 {
423 if(toEdge->To() == node)
424 {
425 m_edges[fromEdge->To()].erase(toEdge);
426
427 break;
428 }
429 }
430 }
431
432 m_edges[node].clear();
433 }
434 else
435 {
436 //Find every invalid node in the edge list and remove the edge.
437 for(EdgeListVector::iterator edgeList = m_edges.begin();
438 edgeList != m_edges.end();++edgeList)
439 {
440 for(EdgeList::iterator edge = edgeList->begin();
441 edge != edgeList->end();++edge)
442 {
443 if(m_nodes[edge->To()].GetIndex() == INVALID_NODE_INDEX ||
444 m_nodes[edge->From()].GetIndex() == INVALID_NODE_INDEX)
445 {
446 edge = edgeList->erase(edge);
447 }
448 }
449 }
450 }
451 }
452
453 template<class NODE_TYPE, class EDGE_TYPE>
454 void SparseGraph<NODE_TYPE, EDGE_TYPE>::AddEdge(const EDGE_TYPE &type)
455 {
456 Assert(type.From() < m_nextNodeIndex && type.From() != INVALID_NODE_INDEX &&
457 "SparseGraph::AddEdge() edge.from is invalid.");
458
459 EdgeList &edgeList = m_edges[type.From()];
460 EdgeList::iterator found = edgeList.end();
461 for(EdgeList::iterator iter = edgeList.begin();
462 iter != edgeList.end();++iter)
463 {
464 if(iter->To() == type.To())
465 {
466 found = iter;
467 break;
468 }
469 }
470
471 if(found == edgeList.end())
472 {
473 m_edges[type.From()].push_back(type);
474 }
475 else
476 {
477 *found = type;
478 }
479
480 //We need to add an extra edge if this is a undirected graph.
481 if(!m_isDigraph)
482 {
483 EdgeList &edgeList = m_edges[type.To()];
484 found = edgeList.end();
485 for(EdgeList::iterator iter = edgeList.begin();
486 iter != edgeList.end();++iter)
487 {
488 if(iter->To() == type.From())
489 {
490 found = iter;
491 break;
492 }
493 }
494
495 EDGE_TYPE edge;
496 edge.SetFrom(type.To());
497 edge.SetTo(type.From());
498 edge.SetCost(type.Cost());
499
500 if(found == edgeList.end())
501 {
502 m_edges[edge.From()].push_back(edge);
503 }
504 else
505 {
506 *found = edge;
507 }
508 }
509 }
510
511 template<class NODE_TYPE, class EDGE_TYPE>
512 void SparseGraph<NODE_TYPE, EDGE_TYPE>::RemoveEdge(int from, int to)
513 {
514 Assert(m_nextNodeIndex > from && from != INVALID_NODE_INDEX &&
515 "SparseGraph::GetEdge() invalid 'from' node.");
516 Assert(m_nextNodeIndex > to && to != INVALID_NODE_INDEX &&
517 "SparseGraph::GetEdge() invalid 'to' node.");
518
519 EdgeList &edgeList = m_edges[from];
520 for(EdgeList::iterator iter = edgeList.begin();
521 iter != edgeList.end();++iter)
522 {
523 if(iter->To() == to)
524 {
525 edgeList.erase(iter);
526 break;
527 }
528 }
529
530 if(!m_isDigraph)
531 {
532 EdgeList &edgeList = m_edges[to];
533 for(EdgeList::iterator iter = edgeList.begin();
534 iter != edgeList.end();++iter)
535 {
536 if(iter->To() == from)
537 {
538 edgeList.erase(iter);
539 return;
540 }
541 }
542 }
543 }
544
545 template<class NODE_TYPE, class EDGE_TYPE>
546 int SparseGraph<NODE_TYPE, EDGE_TYPE>::NumNodes() const
547 {
548 return m_nextNodeIndex;
549 }
550
551 template<class NODE_TYPE, class EDGE_TYPE>
552 int SparseGraph<NODE_TYPE, EDGE_TYPE>::NumActiveNodes() const
553 {
554 int numActiveNodes = 0;
555 for(NodeVector::const_iterator iter = m_nodes.begin();
556 iter != m_nodes.end();++iter)
557 {
558 if(iter->GetIndex() != INVALID_NODE_INDEX)
559 {
560 ++numActiveNodes;
561 }
562 }
563
564 return numActiveNodes;
565 }
566
567 template<class NODE_TYPE, class EDGE_TYPE>
568 int SparseGraph<NODE_TYPE, EDGE_TYPE>::NumEdges() const
569 {
570 int numEdges = 0;
571 for(EdgeListVector::iterator edgeIter = m_edges.begin();
572 edgeIter != m_edges.end();++edgeIter)
573 {
574 numEdges += edgeIter->size();
575 }
576
577 return numEdges;
578 }
579
580 template<class NODE_TYPE, class EDGE_TYPE>
581 void SparseGraph<NODE_TYPE, EDGE_TYPE>::Clear()
582 {
583 m_edges.clear();
584 m_nodes.clear();
585 m_nextNodeIndex = 0;
586 }
587
588 template<class NODE_TYPE, class EDGE_TYPE>
589 bool SparseGraph<NODE_TYPE, EDGE_TYPE>::IsPresent(int node) const
590 {
591 return node < m_nextNodeIndex && node != INVALID_NODE_INDEX;
592 }
593
594 }
595 #endif
OdinAI::SparseGraph::NodeIterator
Definition: SparseGraph.h:196
OdinAI::SparseGraph::NumNodes
int NumNodes() const
Definition: SparseGraph.h:546
OdinAI::SparseGraph
Definition: SparseGraph.h:19
OdinAI::SparseGraph::NumActiveNodes
int NumActiveNodes() const
Definition: SparseGraph.h:552
OdinAI::SparseGraph::RemoveEdge
void RemoveEdge(int from, int to)
Definition: SparseGraph.h:512
OdinAI::SparseGraph::ConstNodeIterator
Definition: SparseGraph.h:254
OdinAI::SparseGraph::AddEdge
void AddEdge(const EdgeType &edge)
Definition: SparseGraph.h:454
OdinAI::SparseGraph::NumEdges
int NumEdges() const
Definition: SparseGraph.h:568
OdinAI::SparseGraph::IsPresent
bool IsPresent(int node) const
Definition: SparseGraph.h:589
OdinAI::SparseGraph::IsEmpty
bool IsEmpty() const
Definition: SparseGraph.h:100
OdinAI::SparseGraph::Clear
void Clear()
Definition: SparseGraph.h:581
OdinAI::SparseGraph::EdgeIterator
Definition: SparseGraph.h:112
OdinAI::SparseGraph::RemoveNode
void RemoveNode(int node)
Definition: SparseGraph.h:409
OdinAI::SparseGraph::AddNode
int AddNode(const NodeType &node)
Definition: SparseGraph.h:386
OdinAI::SparseGraph::IsDigraph
bool IsDigraph() const
Definition: SparseGraph.h:95
OdinAI::SparseGraph::GetNode
const NodeType & GetNode(int index) const
Definition: SparseGraph.h:322
OdinAI::SparseGraph::GetEdge
const EdgeType & GetEdge(int from, int to) const
Definition: SparseGraph.h:359
OdinAI::SparseGraph::ConstEdgeIterator
Definition: SparseGraph.h:154