Graph/DepthFirstSearch/dfs.h

Go to the documentation of this file.
00001 
00010 #ifndef _DFS_H_
00011 #define _DFS_H_
00012 
00013 #include <sstream>
00014 #include "Graph.h"
00015 
00019 class EdgeLabel {
00020  public:
00021   EdgeLabel (int src, int target, edgeType type)
00022     : src_(src), target_(target), type_(type) {}
00023 
00025   int src() { return src_; }
00026 
00028   int target() { return target_; }
00029 
00031   edgeType type() { return type_; }
00032 
00034   string describe() {
00035 
00036     ostringstream oss;
00037     oss << "(" << src_ << "," << target_ << ") [";
00038 
00039     if (type_ == Tree) {
00040       oss << "Tree";
00041     } else if (type_ == Backward) {
00042       oss << "Back";
00043     } else if (type_ == Forward) {
00044       oss << "Forward";
00045     } else if (type_ == Cross) {
00046       oss << "Cross";
00047     }
00048 
00049     oss << "]";
00050     
00051     return oss.str();
00052   }
00053 
00054 
00055  private:
00056   int        src_;
00057   int        target_;
00058   edgeType   type_;
00059 };
00060 
00075 void dfs_search (Graph const &graph, int s,      /* in */
00076          vector<int> &d, vector<int> &f,         /* out */
00077          vector<int> &pred,                      /* out */
00078          list<EdgeLabel> &labels);               /* out */
00079 
00080 #endif  /* _DFS_H_ */
Algorithm Development Kit 1.0