00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "CouenneDepGraph.hpp"
00013
00014
00015
00016 using namespace Couenne;
00017
00018 static bool visit (std::set <DepNode *, compNode>::iterator &v);
00019
00021
00022 bool DepGraph::checkCycles () {
00023
00024 for (std::set <DepNode *, compNode>::iterator
00025 i = vertices_.begin ();
00026 i != vertices_.end (); ++i)
00027 (*i) -> color () = DepNode::DEP_WHITE;
00028
00029
00030
00031 for (std::set <DepNode *, compNode>::iterator
00032 i = vertices_.begin ();
00033 i != vertices_.end (); ++i)
00034
00035 if (((*i) -> color () == DepNode::DEP_WHITE) &&
00036 (visit (i)))
00037 return true;
00038
00039 return false;
00040 }
00041
00042
00043 bool visit (std::set <DepNode *, compNode>::iterator &v) {
00044
00045
00046 (*v) -> color () = DepNode::DEP_GRAY;
00047 std::set <DepNode *, compNode> *list = (*v) -> DepList ();
00048
00049
00050
00051 for (std::set <DepNode *, compNode>::iterator
00052 j = list -> begin ();
00053 j != list -> end (); ++j)
00054
00055 if ((*j) -> color () == DepNode::DEP_GRAY) {
00056
00057 return true;
00058 }
00059 else {
00060
00061 if ((*j) -> color () == DepNode::DEP_WHITE)
00062
00063
00064 if (((*j) -> color () == DepNode::DEP_WHITE) && (visit (j))) {
00065
00066 return true;
00067 }
00068 }
00069
00070 (*v) -> color () = DepNode::DEP_BLACK;
00071
00072 return false;
00073 }