8 #include <KrisLibrary/errors.h> 46 template <
class NodeData,
class EdgeData>
53 ~
Graph() { Cleanup(); }
61 int NumNodes()
const {
return (
int)nodes.size(); }
64 int AddNode(
const NodeData&);
70 void DeleteNode(
int n);
77 void DeleteNodes(std::vector<int>& delnodes);
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(); }
90 template <
class Iterator>
91 void Begin(
int n,Iterator&)
const;
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);
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);
121 void WriteDOT(std::ostream& out);
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;
136 template <
class NodeData,
class EdgeData>
139 nodeColor.resize(n,White);
145 template <
class NodeData,
class EdgeData>
148 nodeColor = g.nodeColor;
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);
161 template <
class NodeData,
class EdgeData>
164 nodeColor = g.nodeColor;
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);
178 template <
class NodeData,
class EdgeData>
181 nodeColor.push_back(White);
183 edges.push_back(EdgeList());
184 co_edges.push_back(CoEdgeList());
185 return int(nodes.size())-1;
188 template <
class NodeData,
class EdgeData>
191 Assert(n >= 0 && n < (
int)nodes.size());
192 DeleteOutgoingEdges(n);
193 DeleteIncomingEdges(n);
195 int rep = (int)nodes.size()-1;
197 nodeColor[n] = nodeColor[rep]; nodeColor.resize(nodeColor.size()-1);
198 nodes[n] = nodes[rep]; nodes.resize(nodes.size()-1);
200 EdgeListIterator ebegin=edges[rep].begin(),eend=edges[rep].end();
201 for(EdgeListIterator e=ebegin;e!=eend;e++) {
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;
208 edges[n] = edges[rep]; edges.erase(--edges.end());
211 CoEdgeListIterator cbegin=co_edges[rep].begin(),cend=co_edges[rep].end();
212 for(CoEdgeListIterator e=cbegin;e!=cend;e++) {
214 EdgeListIterator erep=edges[s].find(rep);
215 Assert(erep->second == e->second);
216 edges[s].erase(erep);
217 edges[s][n] = e->second;
219 co_edges[n] = co_edges[rep]; co_edges.erase(--co_edges.end());
222 template <
class NodeData,
class EdgeData>
226 std::vector<int> nodeMap(nodes.size(),-2);
227 std::vector<int> srcMap(nodes.size(),-1);
229 int last=(int)nodes.size()-1;
230 for(std::vector<int>::const_iterator i=delnodes.begin();i!=delnodes.end();i++) {
233 Assert(nodeMap[n] != -1);
239 while(srcMap[src]>=0)
243 nodeMap[n_orig] = -1;
249 Assert(last == (
int)nodes.size()-1);
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());
259 template <
class NodeData,
class EdgeData>
262 return AddEdge(i,j,EdgeData());
265 template <
class NodeData,
class EdgeData>
269 Assert(!HasEdge(i,j));
270 edgeData.push_back(d);
271 EdgeDataPtr ptr = --edgeData.end();
277 template <
class NodeData,
class EdgeData>
280 return (edges[i].count(j) != 0);
283 template <
class NodeData,
class EdgeData>
286 ConstEdgeListIterator e=edges[i].find(j);
287 if(e == edges[i].end())
return NULL;
288 return &(*e->second);
291 template <
class NodeData,
class EdgeData>
294 EdgeListIterator k=edges[i].find(j);
295 if(k == edges[i].end()) {
296 FatalError(
"Graph::DeleteEdge(): Edge doesn't exist");
298 EdgeDataPtr ptr = k->second;
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");
305 Assert(ptr == k_co->second);
306 co_edges[j].erase(k_co);
310 template <
class NodeData,
class EdgeData>
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);
329 template <
class NodeData,
class EdgeData>
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);
345 template<
class NodeData,
class EdgeData>
355 template <
class NodeData,
class EdgeData>
359 if(nodeColor.size() != nodes.size()) {
360 LOG4CXX_ERROR(KrisLibrary::logger(),
"nodeColor.size() doesn't match nodes.size(): "<<nodeColor.size()<<
" vs "<<nodes.size());
363 if(edges.size() != nodes.size()) {
364 LOG4CXX_ERROR(KrisLibrary::logger(),
"edges.size() doesn't match nodes.size(): "<<edges.size()<<
" vs "<<nodes.size());
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());
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++) {
376 if(e->first < 0 || e->first >= (
int)nodes.size()) {
377 LOG4CXX_ERROR(KrisLibrary::logger(),
"Edge ("<<i<<
","<<e->first);
380 else if(e->first == (
int)i) {
381 LOG4CXX_ERROR(KrisLibrary::logger(),
"Edge ("<<i<<
","<<e->first);
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);
391 Assert(f->first == (
int)i);
392 if(e->second != f->second) {
393 LOG4CXX_ERROR(KrisLibrary::logger(),
"Edge ("<<i<<
","<<e->first);
396 else if(e->second == edgeData.end()) {
397 LOG4CXX_ERROR(KrisLibrary::logger(),
"Edge ("<<i<<
","<<e->first);
404 if(numEdges != (
int)edgeData.size()) {
405 LOG4CXX_ERROR(KrisLibrary::logger(),
"Different number of edges vs edge data: "<<numEdges<<
" vs "<<edgeData.size());
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++) {
413 if(e->first < 0 || e->first >= (
int)nodes.size()) {
414 LOG4CXX_ERROR(KrisLibrary::logger(),
"Co-edge ("<<i<<
","<<e->first);
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);
424 Assert(f->first == (
int)i);
425 if(e->second != f->second) {
426 LOG4CXX_ERROR(KrisLibrary::logger(),
"Co-edge ("<<i<<
","<<e->first);
429 else if(e->second == edgeData.end()) {
430 LOG4CXX_ERROR(KrisLibrary::logger(),
"Co-edge ("<<i<<
","<<e->first);
437 if(numCoEdges != (
int)edgeData.size()) {
438 LOG4CXX_ERROR(KrisLibrary::logger(),
"Different number of coedges vs edge data: "<<numCoEdges<<
" vs "<<edgeData.size());
444 template <
class NodeData,
class EdgeData>
445 template <
class Iterator>
448 it.init(edges[n],co_edges[n]);
452 template <
class NodeData,
class EdgeData>
455 std::fill(nodeColor.begin(),nodeColor.end(),White);
458 template <
class NodeData,
class EdgeData>
459 template <
class Iterator>
463 int n = (int)nodeColor.size();
465 if(nodeColor[i] == White) {
467 _DFS(i,f,Iterator());
472 template <
class NodeData,
class EdgeData>
473 template <
class Iterator>
477 int n = (int)nodeColor.size();
479 if(nodeColor[i] == White) {
481 _BFS(i,f,Iterator());
486 template <
class NodeData,
class EdgeData>
487 template <
class Iterator>
493 if(nodeColor[i] == White) {
499 template <
class NodeData,
class EdgeData>
500 template <
class Iterator>
506 if(nodeColor[i] == White) {
512 template <
class NodeData,
class EdgeData>
513 template <
class Iterator>
524 template <
class NodeData,
class EdgeData>
525 template <
class Iterator>
528 int n = (int)nodeColor.size();
538 template <
class NodeData,
class EdgeData>
539 template <
class Iterator>
542 Assert(nodeColor[n] == White);
547 for(Begin(n,it);!it.end();it++) {
549 switch(nodeColor[a]) {
565 nodeColor[n] = Black;
568 template <
class NodeData,
class EdgeData>
569 template <
class Iterator>
572 std::queue<int> queue;
574 queue.push(n); nodeColor[n] = Grey;
575 while(!queue.empty()) {
576 n=queue.front(); queue.pop();
579 for(Begin(n,it);!it.end();it++) {
581 switch(nodeColor[a]){
584 queue.push(a); nodeColor[a] = Grey;
598 nodeColor[n] = Black;
603 template <
class NodeData,
class EdgeData>
604 template <
class Iterator>
607 Assert(nodeColor[n] == White);
611 for(Begin(n,it);!it.end();it++) {
613 if(nodeColor[a] == White) {
619 nodeColor[n] = Black;
622 template <
class NodeData,
class EdgeData>
623 template <
class Iterator>
626 std::queue<int> queue;
628 queue.push(n); nodeColor[n] = Grey;
630 while(!queue.empty()) {
631 n=queue.front(); queue.pop();
633 for(Begin(n,it);!it.end();it++) {
635 if(nodeColor[a] == White) {
636 queue.push(a); nodeColor[a] = Grey;
640 nodeColor[n] = Black;
645 template <
class NodeData,
class EdgeData>
646 template <
class Iterator>
651 for(Begin(n,it);!it.end();it++) {
659 template <
class NodeData,
class EdgeData>
660 template <
class Iterator>
663 std::queue<int> queue;
667 while(!queue.empty()) {
668 n=queue.front(); queue.pop();
670 for(Begin(n,it);!it.end();it++) {
681 template<
class NodeData,
class EdgeData>
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;
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'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