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,
00076 vector<int> &d, vector<int> &f,
00077 vector<int> &pred,
00078 list<EdgeLabel> &labels);
00079
00080 #endif
Algorithm Development Kit 1.0