| 121 | |
| 122 | |
| 123 | py::object Prim(py::object G, py::object weight) { |
| 124 | std::unordered_map<node_t, std::unordered_map<node_t, weight_t>> res_dict; |
| 125 | py::dict result_dict = py::dict(); |
| 126 | Graph& G_ = G.cast<Graph&>(); |
| 127 | adj_dict_factory adj = G_.adj; |
| 128 | std::vector<node_t> selected; |
| 129 | std::vector<node_t> candidate; |
| 130 | node_dict_factory& node_list = G_.node; |
| 131 | std::string weight_key = weight_to_string(weight); |
| 132 | for (node_dict_factory::iterator i = node_list.begin(); i != node_list.end(); i++) { |
| 133 | node_t node_id = i->first; |
| 134 | result_dict[G_.id_to_node[py::cast(node_id)]] = py::dict(); |
| 135 | if (selected.size() == 0) { |
| 136 | selected.emplace_back(node_id); |
| 137 | } else { |
| 138 | candidate.emplace_back(node_id); |
| 139 | } |
| 140 | } |
| 141 | while (candidate.size() > 0) { |
| 142 | node_t start_id = -1; |
| 143 | node_t end_id = -1; |
| 144 | weight_t min_weight = INFINITY; |
| 145 | int selected_len = selected.size(); |
| 146 | int candidate_len = candidate.size(); |
| 147 | for (int i = 0; i < selected_len; i++) { |
| 148 | for (int j = 0; j < candidate_len; j++) { |
| 149 | adj_attr_dict_factory node_adj = G_.adj[selected[i]]; |
| 150 | edge_attr_dict_factory edge_attr; |
| 151 | weight_t edge_weight = INFINITY; |
| 152 | bool j_exist = false; |
| 153 | if (node_adj.find(candidate[j]) != node_adj.end()) { |
| 154 | edge_attr = node_adj[candidate[j]]; |
| 155 | edge_weight = edge_attr.find(weight_key) != edge_attr.end() ? edge_attr[weight_key] : 1; |
| 156 | j_exist = true; |
| 157 | } |
| 158 | if ((node_list.find(selected[i]) != node_list.end()) && |
| 159 | j_exist && |
| 160 | (edge_weight < min_weight)) { |
| 161 | start_id = selected[i]; |
| 162 | end_id = candidate[j]; |
| 163 | min_weight = edge_weight; |
| 164 | } |
| 165 | } |
| 166 | } |
| 167 | if (start_id != -1 && end_id != -1) { |
| 168 | res_dict[start_id][end_id] = min_weight; |
| 169 | selected.emplace_back(end_id); |
| 170 | std::vector<node_t>::iterator temp_iter; |
| 171 | temp_iter = std::find(candidate.begin(), candidate.end(), end_id); |
| 172 | candidate.erase(temp_iter); |
| 173 | } else { |
| 174 | break; |
| 175 | } |
| 176 | } |
| 177 | for (std::unordered_map<node_t, std::unordered_map<node_t, weight_t>>::iterator k = res_dict.begin(); |
| 178 | k != res_dict.end(); k++) { |
| 179 | py::object res_node = G_.id_to_node[py::cast(k->first)]; |
| 180 | for (std::unordered_map<node_t, weight_t>::iterator z = k->second.begin(); z != k->second.end(); z++) { |
nothing calls this directly
no test coverage detected