## [1991be]: / src / lib / graph / Graph.cc  Maximize  Restore  History

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161``` ```#include #include #include #include #include #include #include #include #include #include using std::vector; using std::set; using std::invalid_argument; using std::logic_error; using std::reverse; namespace jags { Graph::Graph() {} bool Graph::contains(Node const *node) const { Graph::iterator p = find(const_cast(node)); if (p != end() && *p != node) throw logic_error("Node not uniquely defined by its index in Graph"); return p != end(); //return find(const_cast(node)) != end(); } bool Graph::isClosed() const { //Determine whether any nodes in the graph have children or //parents outside the graph for (iterator i = begin(); i != end(); i++) { // Check parents vector const &parents = (*i)->parents(); for (vector::const_iterator j = parents.begin(); j != parents.end(); j++) { if (!contains(*j)) return false; } // Check children set const *sch = (*i)->stochasticChildren(); for (set::iterator k = sch->begin(); k != sch->end(); k++) { if (!contains(*k)) return false; } set const *dch = (*i)->deterministicChildren(); for (set::iterator k = dch->begin(); k != dch->end(); k++) { if (!contains(*k)) return false; } } return true; } /* Helper function for Graph::getSortedNodes. Returns true if node has any children in set S */ static bool childInSet(Node *node, set const &S) { for (set::const_iterator j = node->stochasticChildren()->begin(); j != node->stochasticChildren()->end(); ++j) { if (S.count(*j)) { return true; } } for (set::const_iterator j = node->deterministicChildren()->begin(); j != node->deterministicChildren()->end(); ++j) { if (S.count(*j)) { return true; } } return false; } void Graph::getSortedNodes(set &S, vector &sortednodes) { //Return a vector of nodes whose ordering follows the partial //ordering of the set. If a is after b then there is never a //path from a to b. if (!sortednodes.empty()) { throw logic_error("vector not empty in getSortedNodes"); } sortednodes.reserve(S.size()); while (!S.empty()) { bool loopcheck = false; set::iterator i = S.begin(); while (i != S.end()) { if (childInSet(*i, S)) { ++i; } else { loopcheck = true; sortednodes.push_back(*i); set::iterator j = i; ++i; S.erase(j); } } if (!loopcheck) { //We did not add any nodes to sortednodes on this pass throw logic_error("Failure in Graph::getSortedNodes. Directed cycle in graph"); } } reverse(sortednodes.begin(), sortednodes.end()); } /* //Recursively search for path between two nodes in a set static bool pathTo(Node *node1, Node *node2, set const &S) { if (node1 == node2) return true; for (set::const_iterator j = node1->stochasticChildren()->begin(); j != node1->stochasticChildren()->end(); ++j) { set::const_iterator p = S.find(*j); if (p != S.end()) { if (pathTo(*p, node2, S)) return true; } } for (set::const_iterator j = node1->deterministicChildren()->begin(); j != node1->deterministicChildren()->end(); ++j) { set::const_iterator p = S.find(*j); if (p != S.end()) { if (pathTo(*p, node2, S)) return true; } } return false; } */ //FIXME: This should be redundant now void Graph::getSortedNodes(vector &sortednodes) const { set S = *this; getSortedNodes(S, sortednodes); } } ```