OdinAI
 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>
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 
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:
148  const int m_nodeIndex;
149  typename EdgeList::iterator m_currentEdge;
150  };
151 
152  friend EdgeIterator;
153 
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 
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 
250  typename NodeVector::iterator m_currentNode;
251  };
252  friend NodeIterator;
253 
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>
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>
381 {
382  return m_nextNodeIndex;
383 }
384 
385 template<class NODE_TYPE, class EDGE_TYPE>
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>
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>
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>
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>
547 {
548  return m_nextNodeIndex;
549 }
550 
551 template<class NODE_TYPE, class EDGE_TYPE>
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>
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>
582 {
583  m_edges.clear();
584  m_nodes.clear();
585  m_nextNodeIndex = 0;
586 }
587 
588 template<class NODE_TYPE, class EDGE_TYPE>
590 {
591  return node < m_nextNodeIndex && node != INVALID_NODE_INDEX;
592 }
593 
594 }
595 #endif
Definition: SparseGraph.h:196
int NumNodes() const
Definition: SparseGraph.h:546
Definition: SparseGraph.h:19
int NumActiveNodes() const
Definition: SparseGraph.h:552
void RemoveEdge(int from, int to)
Definition: SparseGraph.h:512
Definition: SparseGraph.h:254
void AddEdge(const EdgeType &edge)
Definition: SparseGraph.h:454
int NumEdges() const
Definition: SparseGraph.h:568
bool IsPresent(int node) const
Definition: SparseGraph.h:589
bool IsEmpty() const
Definition: SparseGraph.h:100
void Clear()
Definition: SparseGraph.h:581
Definition: SparseGraph.h:112
void RemoveNode(int node)
Definition: SparseGraph.h:409
int AddNode(const NodeType &node)
Definition: SparseGraph.h:386
bool IsDigraph() const
Definition: SparseGraph.h:95
const NodeType & GetNode(int index) const
Definition: SparseGraph.h:322
const EdgeType & GetEdge(int from, int to) const
Definition: SparseGraph.h:359
Definition: SparseGraph.h:154