I have generalized a little bit my codes on counting paths in rectangular grid graphs. Now, input graph is arbitrary, and so is end points of paths. More over for each node, “frontier” information is preprocessed, which is used later for pruning state consisting of trees of mates (by D. Knuth) on the way of processing. Efficiency seems more than I expected. I am now polishing codes to upload. Before doing so, I would like to know whether such path counting package for SWI-Prolog already exists.
Here is some doc and queries on the generalized path counting codes.
%! udg_path_count(+A, +B, +Ls, -C) is det. % C is unified with the number of paths which connects A an B % in a given undirected graph Ls in the form of a list of % unordered links. % ?- udg_path_count(a, b, [a-b], C). %@ C = 1. % ?- udg_path_count(a, b, [a-b,b-c,a-c], C). %@ C = 2. % ?- udg_path_count(a, d, [a-b,c-d], C). %@ C = 0. % ?- W=3, H=3, rect_grid_graph(W, H, _L), % time(udg_path_count(p(0,0), p(W, H), _L, C)). %@ % 926,679 inferences, 0.055 CPU in 0.059 seconds (93% CPU, 16898791 Lips) %@ W = H, H = 3, %@ C = 184. % ?- W=7, H=7, rect_grid_graph(W, H, _L), % time(udg_path_count(p(0,0), p(W, H), _L, C)). %@ % 605,826,852 inferences, 55.159 CPU in 56.573 seconds (98% CPU, 10983321 Lips) %@ W = H, H = 7, %@ C = 789360053252. % ?- _W=3, _H=3, rect_grid_graph(_W, _H, _L), % remove_links(_L, [p(1,1),p(2,2)], _L0), % udg_path_count(p(0,0), p(_W, _H), _L0, C). %@ C = 4.