| 74 | |
| 75 | |
| 76 | py::object _spfa(py::object G, py::object source, py::object weight) { |
| 77 | Graph& G_ = G.cast<Graph&>(); |
| 78 | bool is_directed = G.attr("is_directed")().cast<bool>(); |
| 79 | std::string weight_key = weight_to_string(weight); |
| 80 | Graph_L G_l = graph_to_linkgraph(G_, is_directed,weight_key, false); |
| 81 | int N = G_.node.size(); |
| 82 | |
| 83 | std::vector<int> Q(N+10,0); |
| 84 | std::vector<double> dis(N+1,INFINITY); |
| 85 | std::vector<bool> vis(N+1,false); |
| 86 | |
| 87 | int l = 0, r = 1; |
| 88 | node_t S = G_.node_to_id[source].cast<node_t>(); |
| 89 | Q[0] = S; vis[S] = true; dis[S] = 0; |
| 90 | std::vector<LinkEdge>& E = G_l.edges; |
| 91 | |
| 92 | std::vector<int>& head = G_l.head; |
| 93 | while (l != r) { |
| 94 | if (r != 0 && dis[Q[l]] >= dis[Q[r - 1]]) |
| 95 | std::swap(Q[l], Q[r - 1]); |
| 96 | int u = Q[l++]; |
| 97 | if (l >= N) l -= N; |
| 98 | vis[u] = true; |
| 99 | |
| 100 | for(register int p = head[u]; p != -1; p = E[p].next) { |
| 101 | int v=E[p].to; |
| 102 | if (dis[v]>dis[u]+E[p].w) { |
| 103 | dis[v]=dis[u]+E[p].w; |
| 104 | if (!vis[v]) { |
| 105 | vis[v]=true; |
| 106 | if (l == 0 || dis[v] >= dis[Q[l]]) |
| 107 | Q[r++]=v; |
| 108 | else |
| 109 | Q[--l]=v; |
| 110 | if (r >= N) r -= N; |
| 111 | } |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | py::list pydist = py::list(); |
| 116 | for(int i = 1; i <= N; i++){ |
| 117 | pydist.append(py::cast(dis[i])); |
| 118 | } |
| 119 | return pydist; |
| 120 | } |
| 121 | |
| 122 | |
| 123 | py::object Prim(py::object G, py::object weight) { |
nothing calls this directly
no test coverage detected