A simple but powerful generalization of path counting in rectangular grid graphs

Nice to know
, ,
1

Edit: 2022/11/04
For just a fun, I selected randomly 100 undirected graphs with source and target in a fixed set of ten nodes, and count paths for each graph. The result is below, in which most of graphs have not a path. I am not sure whether this is normal. For the random selection, I used the builtin arithmetic funciton random/1 and ZDD function pow to enumerate all the possible sets of links.

% ?- open_state(S), K=100, N=10, numlist(1, N, Ns),
%	all_links(Ns, B, S), select_random_paths(B, K, C, S),
%	close_state(S), time(map_solve(C)).
%@ path count = 0
%@ path count = 1
%@ path count = 873
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 344
%@ path count = 42
%@ path count = 1
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 699
%@ path count = 1
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 453
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 261
%@ path count = 2098
%@ path count = 0
%@ path count = 1376
%@ path count = 0
%@ path count = 0
%@ path count = 1
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 2805
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 14
%@ path count = 0
%@ path count = 0
%@ path count = 115
%@ path count = 0
%@ path count = 0
%@ path count = 1
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 255
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 415
%@ path count = 295
%@ path count = 0
%@ path count = 0
%@ path count = 1
%@ path count = 0
%@ path count = 245
%@ path count = 0
%@ path count = 0
%@ path count = 6611
%@ path count = 1
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 398
%@ path count = 0
%@ path count = 131
%@ path count = 565
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 127
%@ path count = 994
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ path count = 127
%@ path count = 0
%@ path count = 154
%@ path count = 0
%@ path count = 0
%@ path count = 0
%@ % 475,685,620 inferences, 30.776 CPU in 30.924 seconds (100% CPU, 15456263 Lips)

End of Edit

I have written a codes which enumerates all paths in a given undirected graph. This codes is a simple generalized version for rectangular grid graphs. I could drop successfully assumptions used
in the rectangular version so that the new version works for arbitrary undirected graphs. I have tested it for the rectangular grid graphs forgetting its concrete structures. Performance is marginally comparative with existing old versions of mine in ZDD. As the new version works for rectangular grid graphs with about 100 links in 30 seconds, I would like to think that a new powerful graph theoretical tool has been obtained on SWI-Prolog. However, I have to take time to test if it is really powerful for arbitrary undirected graphs. I appreciate for some help for this purpose, letting me know persuasive test cases or existing library in SWI-Prolog.

1 Like