7 #include <unordered_set>
8 #include <unordered_map>
11 #include <boost/range/algorithm/max_element.hpp>
26 template <
typename Aut>
27 std::vector<weight_t_of<Aut>>
33 auto ws = *aut->weightset();
34 auto d = std::vector<weight_t>(aut->all_states().back() + 1, ws.zero());
38 auto todo = std::deque<state_t>{s0};
41 auto s = todo.front();
45 for (
auto t : aut->all_out(s))
47 auto dst = aut->dst_of(t);
48 auto w1 = ws.
mul(r1, aut->weight_of(t));
49 auto w = ws.add(d[dst], w1);
50 if (!ws.equal(d[dst], w))
53 r[dst] = ws.add(
r[dst], w1);
55 todo.emplace_back(dst);
63 template <
typename Aut,
typename WeightSet>
73 using pair_t = std::pair<state_t, weight_t>;
83 auto& ws = *
aut_->weightset();
86 auto stack = std::vector<pair_t>{{s0, ws.one()}};
91 while (!stack.empty())
99 for (
auto t :
aut_->all_out(src))
105 res = ws.add(res, new_weight);
108 pair_t np(dst, new_weight);
109 stack.emplace_back(dst, new_weight);
121 template <
typename Aut>
131 using pair_t = std::pair<state_t, weight_t>;
141 auto& ws = *
aut_->weightset();
143 auto stack = std::vector<pair_t>{{s0, ws.one()}};
150 while (!stack.empty())
158 if (w < min_weight[src])
162 for (
auto t :
aut_->all_out(src))
167 if (new_weight < min_weight[dst] &&
168 new_weight < min_weight[s1])
169 stack.emplace_back(dst, new_weight);
173 return min_weight[s1];
186 template<
typename Aut>
187 std::unordered_map<state_t_of<Aut>,
197 std::queue<state_t> todo;
198 std::unordered_set<state_t> marked;
199 std::unordered_map<state_t, std::pair<unsigned, transition_t>> parent;
204 while (!todo.empty())
206 state_t p = todo.front();
209 for (
auto t : aut->all_in(p))
211 auto s = aut->src_of(t);
212 if (marked.find(s) == marked.end())
215 auto cur_p = parent.find(p);
217 = cur_p == parent.end() ? 1
218 : cur_p->second.first + 1;
219 parent[s] = {cur_d, t};
231 template<
typename Aut>
232 std::vector<transition_t_of<Aut>>
241 std::queue<state_t> todo;
242 std::unordered_set<state_t> marked;
243 std::unordered_map<state_t, std::pair<state_t, transition_t>> parent;
246 while (!todo.empty())
248 state_t p = todo.front();
253 std::vector<transition_t> rpath;
254 state_t bt_curr = end;
255 while (bt_curr != start)
258 std::tie(bt_curr, t) = parent.find(bt_curr)->second;
261 std::reverse(rpath.begin(), rpath.end());
265 for (
auto t : aut->all_out(p))
267 auto s = aut->dst_of(t);
268 if (marked.find(s) == marked.end())
276 return std::vector<transition_t>();
279 template <
typename Aut>
280 std::vector<std::vector<weight_t_of<Aut>>>
283 using automaton_t = Aut;
286 auto ws = aut->weightset();
287 auto n = aut->all_states().back() + 1;
288 std::vector<std::vector<weight_t>> res(
289 n, std::vector<weight_t>(n, ws->zero()));
291 for (
auto t : aut->all_transitions())
292 res[aut->src_of(t)][aut->dst_of(t)] = aut->weight_of(t);
293 for (
auto k : aut->all_states())
294 for (
auto i : aut->all_states())
295 for (
auto j : aut->all_states())
296 res[i][j] = ws->add(res[i][j], ws->mul(res[i][k], res[k][j]));
value_t mul(const Ts &...ts) const
A variadic multiplication.
std::vector< std::vector< weight_t_of< Aut > > > all_distances(const Aut &aut)
state_distancer(const Aut &aut)
std::vector< transition_t_of< Aut > > path_bfs(const Aut &aut, state_t_of< Aut > start, state_t_of< Aut > end)
A shortest path between two states.
Container::value_type back(const Container &container)
The last member of this Container.
weight_t_of< automaton_t > weight_t
std::pair< state_t, weight_t > pair_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
weight_t_of< automaton_t > weight_t
std::unordered_map< state_t_of< Aut >, std::pair< unsigned, transition_t_of< Aut > > > paths_ibfs(const Aut &aut, const std::vector< state_t_of< Aut >> &start)
Find the shortest paths from some states to all the states.
state_t_of< automaton_t > state_t
Provide a variadic mul on top of a binary mul(), and one().
std::pair< state_t, weight_t > pair_t
std::vector< weight_t_of< Aut > > ss_shortest_distance(const Aut &aut, state_t_of< Aut > s0)
Single source shortest distance.
weight_t operator()(state_t s0, state_t s1) const
State distance Find weighted distance between state s0 and state s1 using a dfs.
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
state_t_of< automaton_t > state_t
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
ATTRIBUTE_PURE bool has(const std::deque< T, Allocator > &s, const T &e)
Whether e is member of s.
state_distancer(const Aut &aut)
Wrapper struct to provide the state distance function.
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of