1 #ifndef ODINAI_SPARSE_GRAPH_H_
2 #define ODINAI_SPARSE_GRAPH_H_
8 #include "SharedDefs.h"
18 template<
class NODE_TYPE,
class EDGE_TYPE>
22 typedef NODE_TYPE NodeType;
23 typedef EDGE_TYPE EdgeType;
25 typedef std::vector<NODE_TYPE> NodeVector;
26 typedef std::list<EDGE_TYPE> EdgeList;
27 typedef std::vector<EdgeList> EdgeListVector;
29 SparseGraph(
bool digraph) : m_nextNodeIndex(0), m_isDigraph(digraph) {}
35 const NodeType &
GetNode(
int index)
const;
47 const EdgeType &
GetEdge(
int from,
int to)
const;
53 EdgeType &
GetEdge(
int from,
int to);
55 int GetNextNodeIndex()
const;
60 int AddNode(
const NodeType &node);
70 void AddEdge(
const EdgeType &edge);
100 bool IsEmpty()
const {
return m_nextNodeIndex <= 0;}
117 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
122 if(m_graph.m_edges[m_nodeIndex].size() < 1)
127 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
128 return &(*m_currentEdge);
139 return &(*m_currentEdge);
144 return m_currentEdge == m_graph.m_edges[m_nodeIndex].end();
148 const int m_nodeIndex;
149 typename EdgeList::iterator m_currentEdge;
159 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
162 const EdgeType *Begin()
164 if(m_graph.m_edges[m_nodeIndex].size() < 1)
169 m_currentEdge = m_graph.m_edges[m_nodeIndex].begin();
171 return &(*m_currentEdge);
174 const EdgeType *Next()
182 return &(*m_currentEdge);
187 return m_currentEdge == m_graph.m_edges[m_nodeIndex].end();
191 const int m_nodeIndex;
192 typename EdgeList::const_iterator m_currentEdge;
201 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
206 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
208 NextValidNode(m_currentNode);
210 return &(*m_currentNode);
221 NextValidNode(m_currentNode);
223 return &(*m_currentNode);
228 return m_currentNode == m_graph.m_nodes.end();
233 void NextValidNode(
typename NodeVector::iterator curNode)
235 if(curNode == m_graph.m_nodes.end() || curNode->GetIndex() != INVALID_NODE_INDEX)
238 while(curNode->GetIndex() == INVALID_NODE_INDEX)
242 if(curNode == m_graph.m_nodes.end())
250 typename NodeVector::iterator m_currentNode;
259 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
262 const NodeType *Begin()
264 m_currentNode = m_graph[m_nodeIndex].m_nodes.begin();
266 NextValidNode(m_currentNode);
268 return &(*m_currentNode);
271 const NodeType *Next()
279 NextValidNode(m_currentNode);
281 return &(*m_currentNode);
286 return m_currentNode == m_graph.m_nodes.end();
291 void NextValidNode(
typename NodeVector::const_iterator curNode)
293 if(curNode == m_graph.m_nodes.end() || curNode->GetIndex() != INVALID_NODE_INDEX)
296 while(curNode->GetIndex() == INVALID_NODE_INDEX)
300 if(curNode == m_graph.m_nodes.end())
308 typename NodeVector::const_iterator m_currentNode;
314 EdgeListVector m_edges;
321 template<
class NODE_TYPE,
class EDGE_TYPE>
324 Assert(m_nextNodeIndex > index && index != INVALID_NODE_INDEX
325 &&
"SparseGraph::GetNode() Index is invalid.");
326 return m_nodes.at(index);
329 template<
class NODE_TYPE,
class EDGE_TYPE>
332 Assert(m_nextNodeIndex > index && index != INVALID_NODE_INDEX
333 &&
"SparseGraph::GetNode() Index is invalid.");
334 return m_nodes[index];
337 template<
class NODE_TYPE,
class EDGE_TYPE>
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.");
345 EdgeList &edgeList = m_edges[from];
346 for(EdgeList::iterator iter = edgeList.begin();
347 iter != edgeList.end();++iter)
355 Assert(
false &&
"SparseGraph::GetEdge(): Could not find edge!");
358 template<
class NODE_TYPE,
class EDGE_TYPE>
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.");
366 EdgeList &edgeList = m_edges[from];
367 for(EdgeList::const_iterator iter = edgeList.begin();
368 iter != edgeList.end();++iter)
376 Assert(
false &&
"SparseGraph::GetEdge(): Could not find edge!");
379 template<
class NODE_TYPE,
class EDGE_TYPE>
382 return m_nextNodeIndex;
385 template<
class NODE_TYPE,
class EDGE_TYPE>
388 if(node.GetIndex() < m_nextNodeIndex)
390 Assert(m_nodes[node.GetIndex()].GetIndex() == INVALID_NODE_INDEX
391 &&
"SparseGraph::AddNode() could not replace the node.");
393 m_nodes[node.GetIndex()] = node;
395 return m_nextNodeIndex;
399 Assert(node.GetIndex() == m_nextNodeIndex &&
400 "SparseGraph::AddNode() could not add node, since it had an invalid index.");
402 m_nodes.push_back(node);
403 m_edges.resize(++m_nextNodeIndex);
404 return m_nextNodeIndex;
408 template<
class NODE_TYPE,
class EDGE_TYPE>
411 Assert(node < m_nextNodeIndex &&
"SparseGraph::RemoveNode() Invalid node index.");
412 m_nodes[node].SetIndex(INVALID_NODE_INDEX);
417 for(EdgeList::iterator fromEdge = m_edges[node].begin();
418 fromEdge != m_edges[node].end();++fromEdge)
420 for(EdgeList::iterator toEdge = m_edges[fromEdge->To()].begin();
421 toEdge != m_edges[fromEdge->To()].end();++toEdge)
423 if(toEdge->To() == node)
425 m_edges[fromEdge->To()].erase(toEdge);
432 m_edges[node].clear();
437 for(EdgeListVector::iterator edgeList = m_edges.begin();
438 edgeList != m_edges.end();++edgeList)
440 for(EdgeList::iterator edge = edgeList->begin();
441 edge != edgeList->end();++edge)
443 if(m_nodes[edge->To()].GetIndex() == INVALID_NODE_INDEX ||
444 m_nodes[edge->From()].GetIndex() == INVALID_NODE_INDEX)
446 edge = edgeList->erase(edge);
453 template<
class NODE_TYPE,
class EDGE_TYPE>
456 Assert(type.From() < m_nextNodeIndex && type.From() != INVALID_NODE_INDEX &&
457 "SparseGraph::AddEdge() edge.from is invalid.");
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)
464 if(iter->To() == type.To())
471 if(found == edgeList.end())
473 m_edges[type.From()].push_back(type);
483 EdgeList &edgeList = m_edges[type.To()];
484 found = edgeList.end();
485 for(EdgeList::iterator iter = edgeList.begin();
486 iter != edgeList.end();++iter)
488 if(iter->To() == type.From())
496 edge.SetFrom(type.To());
497 edge.SetTo(type.From());
498 edge.SetCost(type.Cost());
500 if(found == edgeList.end())
502 m_edges[edge.From()].push_back(edge);
511 template<
class NODE_TYPE,
class EDGE_TYPE>
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.");
519 EdgeList &edgeList = m_edges[from];
520 for(EdgeList::iterator iter = edgeList.begin();
521 iter != edgeList.end();++iter)
525 edgeList.erase(iter);
532 EdgeList &edgeList = m_edges[to];
533 for(EdgeList::iterator iter = edgeList.begin();
534 iter != edgeList.end();++iter)
536 if(iter->To() == from)
538 edgeList.erase(iter);
545 template<
class NODE_TYPE,
class EDGE_TYPE>
548 return m_nextNodeIndex;
551 template<
class NODE_TYPE,
class EDGE_TYPE>
554 int numActiveNodes = 0;
555 for(NodeVector::const_iterator iter = m_nodes.begin();
556 iter != m_nodes.end();++iter)
558 if(iter->GetIndex() != INVALID_NODE_INDEX)
564 return numActiveNodes;
567 template<
class NODE_TYPE,
class EDGE_TYPE>
571 for(EdgeListVector::iterator edgeIter = m_edges.begin();
572 edgeIter != m_edges.end();++edgeIter)
574 numEdges += edgeIter->size();
580 template<
class NODE_TYPE,
class EDGE_TYPE>
588 template<
class NODE_TYPE,
class EDGE_TYPE>
591 return node < m_nextNodeIndex && node != INVALID_NODE_INDEX;
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