KrisLibrary  1.0.0
Graph.h
1 #ifndef GRAPH_GRAPH_H
2 #define GRAPH_GRAPH_H
3 
4 #include <KrisLibrary/Logger.h>
5 #include "Callback.h"
6 #include "Node.h"
7 #include "Edge.h"
8 #include <KrisLibrary/errors.h>
9 #include <vector>
10 #include <queue>
11 #include <iostream>
12 
19 
21 namespace Graph {
22 
46 template <class NodeData, class EdgeData>
47 class Graph
48 {
49 public:
51 
52  Graph() {}
53  ~Graph() { Cleanup(); }
54 
55  void Resize(int n);
56  void Cleanup();
57  bool IsValid() const;
58  void Copy(const Graph<NodeData,EdgeData>& g);
59  void SetTranspose(const Graph<NodeData,EdgeData>& g);
60 
61  int NumNodes() const { return (int)nodes.size(); }
62 
64  int AddNode(const NodeData&);
65 
70  void DeleteNode(int n);
71 
77  void DeleteNodes(std::vector<int>& delnodes);
78 
79  int NumEdges() const { return (int)edgeData.size(); }
80  EdgeData& AddEdge(int i,int j);
81  EdgeData& AddEdge(int i,int j,const EdgeData&);
82  bool HasEdge(int i,int j) const;
83  EdgeData* FindEdge(int i,int j) const;
84  void DeleteEdge(int i,int j);
85  void DeleteOutgoingEdges(int i);
86  void DeleteIncomingEdges(int i);
87  inline size_t OutDegree(int n) const { return edges[n].size(); }
88  inline size_t InDegree(int n) const { return co_edges[n].size(); }
89 
90  template <class Iterator>
91  void Begin(int n,Iterator&) const;
92 
104  void NewTraversal();
105  template <class Iterator> void DFS(Callback&,Iterator);
106  template <class Iterator> void BFS(Callback&,Iterator);
107  template <class Iterator> void SimpleDFS(Callback&,Iterator);
108  template <class Iterator> void SimpleBFS(Callback&,Iterator);
109  template <class Iterator> void GuidedDFS(Callback&,Iterator);
110  template <class Iterator> void GuidedBFS(Callback&,Iterator);
111 
114  template <class Iterator> void _DFS(int node,Callback& f,Iterator);
115  template <class Iterator> void _BFS(int node,Callback& f,Iterator);
116  template <class Iterator> void _SimpleDFS(int node,Callback& f,Iterator);
117  template <class Iterator> void _SimpleBFS(int node,Callback& f,Iterator);
118  template <class Iterator> void _GuidedDFS(int node,Callback& f,Iterator);
119  template <class Iterator> void _GuidedBFS(int node,Callback& f,Iterator);
120 
121  void WriteDOT(std::ostream& out);
122 
123  typedef typename std::list<EdgeData>::iterator EdgeDataPtr;
124  typedef std::map<int,EdgeDataPtr> EdgeList;
125  typedef std::map<int,EdgeDataPtr> CoEdgeList;
126  typedef typename EdgeList::iterator EdgeListIterator;
127  typedef typename CoEdgeList::iterator CoEdgeListIterator;
128  typedef typename EdgeList::const_iterator ConstEdgeListIterator;
129  std::vector<Color> nodeColor;
130  std::vector<NodeData> nodes;
131  std::vector<EdgeList> edges;
132  std::vector<CoEdgeList> co_edges;
133  std::list<EdgeData> edgeData;
134 };
135 
136 template <class NodeData,class EdgeData>
138 {
139  nodeColor.resize(n,White);
140  nodes.resize(n);
141  edges.resize(n);
142  co_edges.resize(n);
143 }
144 
145 template <class NodeData,class EdgeData>
147 {
148  nodeColor = g.nodeColor;
149  nodes = g.nodes;
150  edgeData.clear();
151  edges.resize(g.edges.size());
152  co_edges.resize(g.co_edges.size());
153  for(size_t i=0;i<edges.size();i++) edges[i].clear();
154  for(size_t i=0;i<co_edges.size();i++) co_edges[i].clear();
155  for(size_t i=0;i<edges.size();i++) {
156  for(ConstEdgeListIterator e=g.edges[i].begin();e!=g.edges[i].end();e++)
157  AddEdge(i,e->first,e->second);
158  }
159 }
160 
161 template <class NodeData,class EdgeData>
163 {
164  nodeColor = g.nodeColor;
165  nodes = g.nodes;
166  edgeData.clear();
167  edges.resize(g.edges.size());
168  co_edges.resize(g.co_edges.size());
169  for(size_t i=0;i<edges.size();i++) edges[i].clear();
170  for(size_t i=0;i<co_edges.size();i++) co_edges[i].clear();
171  for(size_t i=0;i<edges.size();i++) {
172  for(ConstEdgeListIterator e=g.edges[i].begin();e!=g.edges[i].end();e++)
173  AddEdge(e->first,i,e->second);
174  }
175 }
176 
177 
178 template <class NodeData,class EdgeData>
179 int Graph<NodeData,EdgeData>::AddNode(const NodeData& n)
180 {
181  nodeColor.push_back(White);
182  nodes.push_back(n);
183  edges.push_back(EdgeList());
184  co_edges.push_back(CoEdgeList());
185  return int(nodes.size())-1;
186 }
187 
188 template <class NodeData,class EdgeData>
190 {
191  Assert(n >= 0 && n < (int)nodes.size());
192  DeleteOutgoingEdges(n);
193  DeleteIncomingEdges(n);
194 
195  int rep = (int)nodes.size()-1;
196  //move all references from rep to n
197  nodeColor[n] = nodeColor[rep]; nodeColor.resize(nodeColor.size()-1);
198  nodes[n] = nodes[rep]; nodes.resize(nodes.size()-1);
199  //here we must move outgoing edges of rep to point to n
200  EdgeListIterator ebegin=edges[rep].begin(),eend=edges[rep].end();
201  for(EdgeListIterator e=ebegin;e!=eend;e++) {
202  int t = e->first;
203  CoEdgeListIterator crep=co_edges[t].find(rep);
204  Assert(crep->second == e->second);
205  co_edges[t].erase(crep);
206  co_edges[t][n] = e->second;
207  }
208  edges[n] = edges[rep]; edges.erase(--edges.end());
209 
210  //here we must move incoming edges of rep to point to n
211  CoEdgeListIterator cbegin=co_edges[rep].begin(),cend=co_edges[rep].end();
212  for(CoEdgeListIterator e=cbegin;e!=cend;e++) {
213  int s = e->first;
214  EdgeListIterator erep=edges[s].find(rep);
215  Assert(erep->second == e->second);
216  edges[s].erase(erep);
217  edges[s][n] = e->second;
218  }
219  co_edges[n] = co_edges[rep]; co_edges.erase(--co_edges.end());
220 }
221 
222 template <class NodeData,class EdgeData>
223 void Graph<NodeData,EdgeData>::DeleteNodes(std::vector<int>& delnodes)
224 {
225  //get the mapping from old to new nodes
226  std::vector<int> nodeMap(nodes.size(),-2);
227  std::vector<int> srcMap(nodes.size(),-1);
228 
229  int last=(int)nodes.size()-1;
230  for(std::vector<int>::const_iterator i=delnodes.begin();i!=delnodes.end();i++) {
231  int n=*i;
232  int n_orig=n;
233  Assert(nodeMap[n] != -1);
234  //n may have been moved around, follow it until it stops
235  while(nodeMap[n]>=0)
236  n=nodeMap[n];
237 
238  int src = last;
239  while(srcMap[src]>=0)
240  src=srcMap[src];
241  //move src to position n
242  nodeMap[src] = n;
243  nodeMap[n_orig] = -1;
244  srcMap[n] = src;
245  srcMap[src] = -1;
246  last--;
247  DeleteNode(n);
248  }
249  Assert(last == (int)nodes.size()-1);
250 
251  //-2 marks unchanged nodes
252  delnodes.resize(nodeMap.size());
253  for(size_t i=0;i<nodeMap.size();i++) {
254  delnodes[i] = (nodeMap[i]==-2?i:nodeMap[i]);
255  Assert(delnodes[i] < (int)nodes.size());
256  }
257 }
258 
259 template <class NodeData,class EdgeData>
260 EdgeData& Graph<NodeData,EdgeData>::AddEdge(int i,int j)
261 {
262  return AddEdge(i,j,EdgeData());
263 }
264 
265 template <class NodeData,class EdgeData>
266 EdgeData& Graph<NodeData,EdgeData>::AddEdge(int i,int j,const EdgeData& d)
267 {
268  Assert(i!=j);
269  Assert(!HasEdge(i,j));
270  edgeData.push_back(d);
271  EdgeDataPtr ptr = --edgeData.end();
272  edges[i][j]=ptr;
273  co_edges[j][i]=ptr;
274  return *ptr;
275 }
276 
277 template <class NodeData,class EdgeData>
278 bool Graph<NodeData,EdgeData>::HasEdge(int i,int j) const
279 {
280  return (edges[i].count(j) != 0);
281 }
282 
283 template <class NodeData,class EdgeData>
284 EdgeData* Graph<NodeData,EdgeData>::FindEdge(int i,int j) const
285 {
286  ConstEdgeListIterator e=edges[i].find(j);
287  if(e == edges[i].end()) return NULL;
288  return &(*e->second);
289 }
290 
291 template <class NodeData,class EdgeData>
292 void Graph<NodeData,EdgeData>::DeleteEdge(int i,int j)
293 {
294  EdgeListIterator k=edges[i].find(j);
295  if(k == edges[i].end()) {
296  FatalError("Graph::DeleteEdge(): Edge doesn't exist");
297  }
298  EdgeDataPtr ptr = k->second;
299  edges[i].erase(k);
300 
301  CoEdgeListIterator k_co = co_edges[j].find(i);
302  if(k_co == co_edges[j].end()) {
303  FatalError("Graph::DeleteEdge(): Co-edge doesn't exist");
304  }
305  Assert(ptr == k_co->second);
306  co_edges[j].erase(k_co);
307  edgeData.erase(ptr);
308 }
309 
310 template <class NodeData,class EdgeData>
312 {
313  //delete co-edges
314  EdgeListIterator k;
315 
316  EdgeListIterator ebegin=edges[i].begin(),eend=edges[i].end();
317  for(k=ebegin;k!=eend;++k) {
318  EdgeListIterator it = co_edges[k->first].find(i);
319  Assert(it != co_edges[k->first].end());
320  Assert(it->second == k->second);
321  edgeData.erase(it->second);
322  co_edges[k->first].erase(it);
323  }
324 
325  //delete edges
326  edges[i].clear();
327 }
328 
329 template <class NodeData,class EdgeData>
331 {
332  //delete edges
333  CoEdgeListIterator k;
334  CoEdgeListIterator cbegin=co_edges[i].begin(),cend=co_edges[i].end();
335  for(k=cbegin;k!=cend;++k) {
336  EdgeListIterator it = edges[k->first].find(i);
337  edgeData.erase(it->second);
338  edges[k->first].erase(it);
339  }
340 
341  //delete co-edges
342  co_edges[i].clear();
343 }
344 
345 template<class NodeData,class EdgeData>
347 {
348  nodeColor.clear();
349  nodes.clear();
350  edges.clear();
351  co_edges.clear();
352  edgeData.clear();
353 }
354 
355 template <class NodeData,class EdgeData>
357 {
358  bool res=true;
359  if(nodeColor.size() != nodes.size()) {
360  LOG4CXX_ERROR(KrisLibrary::logger(),"nodeColor.size() doesn't match nodes.size(): "<<nodeColor.size()<<" vs "<<nodes.size());
361  res=false;
362  }
363  if(edges.size() != nodes.size()) {
364  LOG4CXX_ERROR(KrisLibrary::logger(),"edges.size() doesn't match nodes.size(): "<<edges.size()<<" vs "<<nodes.size());
365  res=false;
366  }
367  if(co_edges.size() != nodes.size()) {
368  LOG4CXX_ERROR(KrisLibrary::logger(),"co_edges.size() doesn't match nodes.size(): "<<co_edges.size()<<" vs "<<nodes.size());
369  res=false;
370  }
371  int numEdges=0;
372  for(size_t i=0;i<edges.size();i++) {
373  ConstEdgeListIterator ebegin=edges[i].begin(),eend=edges[i].end();
374  for(ConstEdgeListIterator e=ebegin;e!=eend;e++) {
375  numEdges++;
376  if(e->first < 0 || e->first >= (int)nodes.size()) {
377  LOG4CXX_ERROR(KrisLibrary::logger(),"Edge ("<<i<<","<<e->first);
378  res=false;
379  }
380  else if(e->first == (int)i) {
381  LOG4CXX_ERROR(KrisLibrary::logger(),"Edge ("<<i<<","<<e->first);
382  res=false;
383  }
384  else if(edges.size() == co_edges.size()) {
385  ConstEdgeListIterator f=co_edges[e->first].find((int)i);
386  if(f == co_edges[e->first].end()) {
387  LOG4CXX_ERROR(KrisLibrary::logger(),"Edge ("<<i<<","<<e->first);
388  res=false;
389  }
390  else {
391  Assert(f->first == (int)i); //STL guarantees this...
392  if(e->second != f->second) {
393  LOG4CXX_ERROR(KrisLibrary::logger(),"Edge ("<<i<<","<<e->first);
394  res=false;
395  }
396  else if(e->second == edgeData.end()) {
397  LOG4CXX_ERROR(KrisLibrary::logger(),"Edge ("<<i<<","<<e->first);
398  res=false;
399  }
400  }
401  }
402  }
403  }
404  if(numEdges != (int)edgeData.size()) {
405  LOG4CXX_ERROR(KrisLibrary::logger(),"Different number of edges vs edge data: "<<numEdges<<" vs "<<edgeData.size());
406  res=false;
407  }
408  int numCoEdges=0;
409  for(size_t i=0;i<co_edges.size();i++) {
410  ConstEdgeListIterator ebegin=co_edges[i].begin(),eend=co_edges[i].end();
411  for(ConstEdgeListIterator e=ebegin;e!=eend;e++) {
412  numCoEdges++;
413  if(e->first < 0 || e->first >= (int)nodes.size()) {
414  LOG4CXX_ERROR(KrisLibrary::logger(),"Co-edge ("<<i<<","<<e->first);
415  res=false;
416  }
417  else if(edges.size() == co_edges.size()) {
418  ConstEdgeListIterator f=edges[e->first].find((int)i);
419  if(f == edges[e->first].end()) {
420  LOG4CXX_ERROR(KrisLibrary::logger(),"Co-edge ("<<i<<","<<e->first);
421  res=false;
422  }
423  else {
424  Assert(f->first == (int)i); //STL guarantees this...
425  if(e->second != f->second) {
426  LOG4CXX_ERROR(KrisLibrary::logger(),"Co-edge ("<<i<<","<<e->first);
427  res=false;
428  }
429  else if(e->second == edgeData.end()) {
430  LOG4CXX_ERROR(KrisLibrary::logger(),"Co-edge ("<<i<<","<<e->first);
431  res=false;
432  }
433  }
434  }
435  }
436  }
437  if(numCoEdges != (int)edgeData.size()) {
438  LOG4CXX_ERROR(KrisLibrary::logger(),"Different number of coedges vs edge data: "<<numCoEdges<<" vs "<<edgeData.size());
439  res=false;
440  }
441  return res;
442 }
443 
444 template <class NodeData,class EdgeData>
445 template <class Iterator>
446 void Graph<NodeData,EdgeData>::Begin(int n,Iterator& it) const {
447  it.n=n;
448  it.init(edges[n],co_edges[n]);
449 }
450 
451 
452 template <class NodeData,class EdgeData>
454 {
455  std::fill(nodeColor.begin(),nodeColor.end(),White);
456 }
457 
458 template <class NodeData,class EdgeData>
459 template <class Iterator>
460 void Graph<NodeData,EdgeData>::DFS(Callback& f,Iterator)
461 {
462  NewTraversal();
463  int n = (int)nodeColor.size();
464  for(int i=0;i<n;i++)
465  if(nodeColor[i] == White) {
466  f.NewComponent(i);
467  _DFS(i,f,Iterator());
468  if(f.Stop()) return;
469  }
470 }
471 
472 template <class NodeData,class EdgeData>
473 template <class Iterator>
474 void Graph<NodeData,EdgeData>::BFS(Callback& f,Iterator it)
475 {
476  NewTraversal();
477  int n = (int)nodeColor.size();
478  for(int i=0;i<n;i++)
479  if(nodeColor[i] == White) {
480  f.NewComponent(i);
481  _BFS(i,f,Iterator());
482  if(f.Stop()) return;
483  }
484 }
485 
486 template <class NodeData,class EdgeData>
487 template <class Iterator>
489 {
490  NewTraversal();
491  int n = NumNodes();
492  for(int i=0;i<n;i++)
493  if(nodeColor[i] == White) {
494  f.NewComponent(i);
495  _SimpleDFS(i,f,it);
496  }
497 }
498 
499 template <class NodeData,class EdgeData>
500 template <class Iterator>
502 {
503  NewTraversal();
504  int n = NumNodes();
505  for(int i=0;i<n;i++)
506  if(nodeColor[i] == White) {
507  f.NewComponent(i);
508  _SimpleBFS(i,f,it);
509  }
510 }
511 
512 template <class NodeData,class EdgeData>
513 template <class Iterator>
515 {
516  int n = NumNodes();
517  for(int i=0;i<n;i++)
518  if(f.Descend(i)) {
519  f.NewComponent(i);
520  _GuidedDFS(i,f,it);
521  }
522 }
523 
524 template <class NodeData,class EdgeData>
525 template <class Iterator>
527 {
528  int n = (int)nodeColor.size();
529  for(int i=0;i<n;i++)
530  if(f.Descend(i)) {
531  f.NewComponent(i);
532  _GuidedDFS(i,f,it);
533  }
534 }
535 
536 
537 
538 template <class NodeData,class EdgeData>
539 template <class Iterator>
540 void Graph<NodeData,EdgeData>::_DFS(int n,Callback& f,Iterator it)
541 {
542  Assert(nodeColor[n] == White);
543  nodeColor[n] = Grey;
544  f.Visit(n);
545  if(f.Stop()) return;
546  if(f.Descend(n)) {
547  for(Begin(n,it);!it.end();it++) {
548  int a=it.target();
549  switch(nodeColor[a]) {
550  case White:
551  if(f.ForwardEdge(n,a))
552  _DFS(a,f,it);
553  break;
554  case Grey:
555  f.BackEdge(n,a);
556  break;
557  case Black:
558  f.CrossEdge(n,a);
559  break;
560  }
561  if(f.Stop()) return;
562  }
563  }
564  f.PostVisit(n);
565  nodeColor[n] = Black;
566 }
567 
568 template <class NodeData,class EdgeData>
569 template <class Iterator>
570 void Graph<NodeData,EdgeData>::_BFS(int s,Callback& f,Iterator it)
571 {
572  std::queue<int> queue;
573  int n=s;
574  queue.push(n); nodeColor[n] = Grey;
575  while(!queue.empty()) {
576  n=queue.front(); queue.pop();
577  f.Visit(n); if(f.Stop()) return;
578  if(f.Descend(n)) {
579  for(Begin(n,it);!it.end();it++) {
580  int a=it.target();
581  switch(nodeColor[a]){
582  case White:
583  if(f.ForwardEdge(n,a)) {
584  queue.push(a); nodeColor[a] = Grey;
585  }
586  break;
587  case Grey:
588  f.CrossEdge(n,a);
589  break;
590  case Black:
591  f.BackEdge(n,a);
592  break;
593  }
594  if(f.Stop()) return;
595  }
596  }
597  f.PostVisit(n);
598  nodeColor[n] = Black;
599  if(f.Stop()) return;
600  }
601 }
602 
603 template <class NodeData,class EdgeData>
604 template <class Iterator>
605 void Graph<NodeData,EdgeData>::_SimpleDFS(int n,Callback& f,Iterator it)
606 {
607  Assert(nodeColor[n] == White);
608  nodeColor[n] = Grey;
609  f.Visit(n);
610  if(f.Stop()) return;
611  for(Begin(n,it);!it.end();it++) {
612  int a=it.target();
613  if(nodeColor[a] == White) {
614  _SimpleDFS(a,f,it);
615  if(f.Stop()) return;
616  }
617  }
618  f.PostVisit(n);
619  nodeColor[n] = Black;
620 }
621 
622 template <class NodeData,class EdgeData>
623 template <class Iterator>
624 void Graph<NodeData,EdgeData>::_SimpleBFS(int s,Callback& f,Iterator it)
625 {
626  std::queue<int> queue;
627  int n=s;
628  queue.push(n); nodeColor[n] = Grey;
629  if(f.Stop()) return;
630  while(!queue.empty()) {
631  n=queue.front(); queue.pop();
632  f.Visit(n); if(f.Stop()) return;
633  for(Begin(n,it);!it.end();it++) {
634  int a=it.target();
635  if(nodeColor[a] == White) {
636  queue.push(a); nodeColor[a] = Grey;
637  }
638  }
639  f.PostVisit(n);
640  nodeColor[n] = Black;
641  if(f.Stop()) return;
642  }
643 }
644 
645 template <class NodeData,class EdgeData>
646 template <class Iterator>
647 void Graph<NodeData,EdgeData>::_GuidedDFS(int n,Callback& f,Iterator it)
648 {
649  Assert(f.Descend(n));
650  f.Visit(n);
651  for(Begin(n,it);!it.end();it++) {
652  int a=it.target();
653  if(f.Descend(a))
654  _GuidedDFS(a,f,it);
655  }
656  f.PostVisit(n);
657 }
658 
659 template <class NodeData,class EdgeData>
660 template <class Iterator>
661 void Graph<NodeData,EdgeData>::_GuidedBFS(int s,Callback& f,Iterator it)
662 {
663  std::queue<int> queue;
664  int n=s;
665  Assert(f.Descend(n));
666  queue.push(n);
667  while(!queue.empty()) {
668  n=queue.front(); queue.pop();
669  f.Visit(n);
670  for(Begin(n,it);!it.end();it++) {
671  int a=it.target();
672  if(f.Descend(a)) {
673  queue.push(a);
674  }
675  }
676  f.PostVisit(n);
677  }
678 }
679 
680 
681 template<class NodeData,class EdgeData>
682 void Graph<NodeData,EdgeData>::WriteDOT(std::ostream& out)
683 {
684  out<<"digraph {"<<std::endl;
685  for(size_t i=0;i<nodeColor.size();i++) {
686  for(EdgeListIterator e=edges[i].begin();e!=edges[i].end();e++)
687  out<<" "<<i<<" -> "<<e->target<<";"<<std::endl;
688  }
689  out<<"}"<<std::endl;
690 }
691 
692 
693 
694 } //namespace Graph
695 
696 #endif
virtual void NewComponent(Node)
Called when a new component is visited.
Definition: Callback.h:39
virtual void PostVisit(Node)
Called after a node has been visited.
Definition: Callback.h:31
virtual void CrossEdge(Node i, Node j)
Called on traversal of edges from i to currently visiting j.
Definition: Callback.h:35
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:25
The logging system used in KrisLibrary.
virtual bool ForwardEdge(Node i, Node j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:33
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7
virtual bool Descend(Node)
Return true to visit the node&#39;s adjacencies.
Definition: Callback.h:29
Basic template graph structure.
Definition: Graph.h:47
virtual void BackEdge(Node i, Node j)
Called on traversal of edges from i to previously visited j.
Definition: Callback.h:37
virtual void Visit(Node)
Called when a node is first visited.
Definition: Callback.h:27