Advanced Search

Question: How to efficiently find the length of some longest path between two nodes in a dag?

Question:How to efficiently find the length of some longest path between two nodes in a dag?

sursumCorda 1239 Maple 2023
graphtheory
July 28 2023
1

The old question "Longest distance in a graph via Maple code" offers some general methods to find longest paths in a given graph, while for directed acyclic graphs, the longest paths can be found much more directly via built-in functions. However, it apprears that even for small dags, Maple cannot solve this in an acceptable time. In the following example, I'd like to count the number of nodes that on longest paths for certain source and target vertexes.
 

> 

restart;
> 

_seed := 1234

Warning, the use of _seed is deprecated.  Please consider using one of the alternatives listed on the _seed help page.

  
> 

G := GraphTheory:-RandomGraphs:-RandomNetwork(200, .2, 'acyclic', 'weights' = 0. .. 2)
> 

G__0 := applyop(`-`, -1, G)``

GRAPHLN(directed, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200], Array(1..200, {(1) = {2, 3, 4}, (2) = {5}, (3) = {4, 5}, (4) = {5}, (5) = {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}, (6) = {11, 12, 13, 14, 15, 17, 18, 19, 21}, (7) = {9, 10, 11, 16, 17, 20, 22}, (8) = {12, 14, 16, 17, 19, 20, 21, 22, 23}, (9) = {11, 14, 21, 23}, (10) = {11, 13, 18, 19, 20, 21, 23}, (11) = {14, 15, 16, 17, 18, 21, 23}, (12) = {13, 15, 18, 19, 20, 22}, (13) = {14, 15, 16, 17, 21}, (14) = {19, 20, 22}, (15) = {19, 20, 22, 23}, (16) = {17, 18, 21}, (17) = {19, 20, 23}, (18) = {19, 20, 21}, (19) = {20, 24, 25}, (20) = {22, 23, 25}, (21) = {23, 24, 25}, (22) = {23, 24, 25}, (23) = {24, 25}, (24) = {26, 27, 29}, (25) = {27, 28, 29}, (26) = {28, 29, 30}, (27) = {28, 29, 31, 32, 33}, (28) = {32, 33}, (29) = {32, 33}, (30) = {34, 35, 38, 39}, (31) = {32, 37, 38, 39}, (32) = {33, 36, 37, 38}, (33) = {35, 36, 39}, (34) = {36, 38, 39}, (35) = {37, 39}, (36) = {37, 39}, (37) = {39, 40}, (38) = {39, 40}, (39) = {40}, (40) = {41, 42}, (41) = {43, 44, 47, 48, 49}, (42) = {44, 45, 46, 47, 48, 49}, (43) = {47, 49, 50, 55, 56, 57}, (44) = {45, 48, 50, 51, 52, 53, 54, 56}, (45) = {46, 47, 49, 50, 52, 56}, (46) = {47, 48, 49, 50, 51, 52, 53, 56, 57}, (47) = {49, 50, 51, 52, 54, 56, 57}, (48) = {49, 51, 52, 53, 54, 55, 56, 57}, (49) = {50, 52, 53, 54, 57}, (50) = {51, 57}, (51) = {53, 54, 57}, (52) = {53, 55, 57}, (53) = {54, 56}, (54) = {56, 58}, (55) = {58}, (56) = {58}, (57) = {58}, (58) = {59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75}, (59) = {60, 61, 66, 68, 70, 71, 74, 75, 76, 77}, (60) = {61, 63, 67, 68, 70, 72, 73, 77}, (61) = {62, 66, 69, 70, 71, 72, 73, 75, 76, 77}, (62) = {65, 68, 75, 76, 77}, (63) = {65, 66, 69, 70, 72, 73, 76, 77}, (64) = {65, 67, 68, 69, 70, 71, 73, 77}, (65) = {66, 70, 72, 73, 74, 76}, (66) = {68, 70, 71, 72, 73, 74, 75, 76, 77}, (67) = {69, 70, 71, 74, 76}, (68) = {73, 74}, (69) = {71, 76, 77}, (70) = {71, 73, 77}, (71) = {72, 76, 77}, (72) = {75}, (73) = {75, 76}, (74) = {76}, (75) = {76}, (76) = {77, 78, 79, 80, 81, 82, 83, 85, 86}, (77) = {79, 80, 82, 84, 85}, (78) = {79, 83, 85, 87}, (79) = {81, 82, 83, 85, 86, 87}, (80) = {83, 86}, (81) = {83, 84, 87}, (82) = {87}, (83) = {85, 86, 87}, (84) = {85, 87}, (85) = {87}, (86) = {87}, (87) = {88, 89}, (88) = {90, 91, 92, 93, 94}, (89) = {90, 91, 93, 94, 95}, (90) = {96, 97, 99, 101, 103, 104, 107, 108, 109, 110, 112, 115, 117, 118, 120}, (91) = {92, 94, 96, 97, 98, 100, 101, 102, 105, 106, 107, 110, 113, 116, 117, 118, 120}, (92) = {95, 97, 98, 99, 101, 103, 106, 107, 108, 111, 112, 113, 115, 117, 119, 120}, (93) = {95, 96, 98, 100, 104, 106, 109, 111, 112, 113, 116, 118, 119, 120}, (94) = {95, 99, 100, 102, 103, 104, 106, 108, 109, 110, 111, 112, 113, 114, 115, 117, 118, 119, 120}, (95) = {97, 98, 99, 100, 102, 103, 104, 105, 107, 108, 109, 111, 112, 113, 114, 115, 116, 117, 118, 120}, (96) = {98, 100, 102, 103, 104, 106, 107, 110, 111, 114, 119, 120, 121}, (97) = {99, 100, 102, 104, 106, 107, 108, 109, 111, 114, 118, 119}, (98) = {102, 103, 107, 110, 111, 112, 113, 114, 116, 117, 119, 120, 121}, (99) = {101, 102, 104, 106, 107, 112, 117, 120}, (100) = {101, 104, 105, 106, 109, 110, 116, 117, 119, 120, 121}, (101) = {102, 105, 109, 110, 111, 112, 113, 114, 115, 117, 118, 119, 120}, (102) = {103, 106, 107, 108, 110, 112, 113, 114, 117, 118, 119}, (103) = {104, 105, 107, 108, 109, 110, 111, 113, 115, 116, 119, 120, 121}, (104) = {105, 106, 109, 110, 114, 115, 116, 118, 119}, (105) = {106, 108, 109, 110, 113, 114, 116, 117}, (106) = {107, 108, 109, 112, 114, 117, 118, 119, 121}, (107) = {110, 114, 116, 119, 120}, (108) = {111, 112, 113, 114, 118, 119, 120, 121}, (109) = {113, 116, 117, 118, 121}, (110) = {111, 113, 117, 119, 120, 121}, (111) = {112, 113, 115, 118, 120}, (112) = {113, 114, 116, 117, 118, 119, 120}, (113) = {116, 117, 119, 121}, (114) = {115, 116, 117, 121}, (115) = {116, 120}, (116) = {119, 121}, (117) = {118, 119, 121}, (118) = {121}, (119) = {121}, (120) = {121}, (121) = {122, 123, 124, 125, 126}, (122) = {123, 124, 125, 126, 127}, (123) = {126}, (124) = {126, 127}, (125) = {127}, (126) = {127}, (127) = {128, 129}, (128) = {130}, (129) = {130}, (130) = {131, 132}, (131) = {132, 133, 135}, (132) = {134, 135}, (133) = {134, 136, 137, 138, 140, 141, 142}, (134) = {135, 136, 139, 140, 141}, (135) = {136, 137, 139, 140, 141, 142}, (136) = {145, 146, 147}, (137) = {139, 141, 143, 145, 147, 148}, (138) = {139, 140, 143, 144, 145, 148}, (139) = {141, 143, 145}, (140) = {143, 145, 146, 147, 148}, (141) = {142, 144, 145, 146, 147}, (142) = {143, 144, 146, 148}, (143) = {145, 146, 147, 148}, (144) = {146, 149}, (145) = {147}, (146) = {149}, (147) = {149}, (148) = {149}, (149) = {150, 151, 152, 153, 154, 155, 156, 157, 158}, (150) = {152, 153, 155, 157, 158}, (151) = {152, 153, 159}, (152) = {154, 158}, (153) = {154, 155, 156}, (154) = {156, 158, 159}, (155) = {158}, (156) = {157, 158, 159}, (157) = {158}, (158) = {159}, (159) = {160, 161, 162, 163}, (160) = {161, 163, 166, 167}, (161) = {165, 166, 167}, (162) = {163, 165}, (163) = {164, 166, 167}, (164) = {166}, (165) = {166, 168, 169}, (166) = {169}, (167) = {168}, (168) = {169, 170, 171, 172, 173, 174, 177, 178, 179, 180, 182}, (169) = {170, 171, 172, 173, 174, 175, 176, 177, 178, 180, 181, 182}, (170) = {172, 173, 174, 175, 176, 180, 182, 183, 185}, (171) = {172, 174, 176, 177, 181, 182, 185}, (172) = {175, 176, 177, 183, 185}, (173) = {175, 176, 178, 183, 185}, (174) = {175, 180, 181, 183, 184, 185}, (175) = {181, 182, 183, 185}, (176) = {177, 178, 179, 182}, (177) = {178, 179, 184, 185}, (178) = {179, 180, 182, 183, 184}, (179) = {180, 182, 185}, (180) = {181, 182}, (181) = {184}, (182) = {185}, (183) = {187, 188, 190}, (184) = {187, 188, 189}, (185) = {186, 188, 190}, (186) = {187, 188, 190, 191, 193, 194, 196}, (187) = {188, 190, 192, 193, 194, 195}, (188) = {189, 190, 191, 192, 194}, (189) = {190, 191, 196}, (190) = {191, 192, 195, 196}, (191) = {193, 196, 199}, (192) = {194, 196, 198, 199}, (193) = {197, 199}, (194) = {195, 196, 197}, (195) = {196, 198, 199}, (196) = {198, 199}, (197) = {198}, (198) = {199, 200}, (199) = {200}, (200) = {}}), `GRAPHLN/table/1`, )

 (1)
> 

t, s := combinat:-randcomb(GraphTheory:-Vertices(G__0), 5^2), combinat:-randcomb(GraphTheory:-Vertices(G__0), integermul2exp(5, 2))

[12, 13, 22, 23, 41, 65, 70, 80, 88, 97, 105, 119, 124, 127, 129, 132, 135, 138, 146, 150, 165, 170, 189, 193, 199], [6, 13, 28, 29, 31, 41, 42, 49, 55, 85, 98, 104, 136, 141, 162, 166, 167, 168, 192, 199]

 (2)
> 

"DataFrame((`M__1`:=CodeTools:-Usage(Matrix(numelems(s),numelems(t),(i,j)->numelems((GraphTheory:-BellmanFordAlgorithm(`G__0`,s[i],t[j]))[1]),datatype=integer[2]))),'columns'=t,'rows'=s)"

memory used=7.99GiB, alloc change=0 bytes, cpu time=5.74m, real time=5.63m, gc time=22.55s

  

module DataFrame () description "two-dimensional rich data container"; local columns, rows, data, binder; option object(BaseDataObject); end module

 (3)
> 

"DataFrame((`M__2`:=CodeTools:-Usage(Matrix(numelems(s),numelems(t),proc(i::posint,j::posint,` $`)::nonnegint; uses ListTools,GraphTheory; local ts::list(posint):=TopologicSort(`G__0`,'output'='permutation'),q::posint:=Search(t[j],ts),p::posint:=Search(s[i],ts); if p>q then 0 elif q=p then 1 else numelems(BellmanFordAlgorithm(`G__0`,s[i],t[j])[1]) fi end,datatype=integer))),':-columns'=t,':-rows'=s)"

memory used=4.34GiB, alloc change=32.00MiB, cpu time=3.26m, real time=3.19m, gc time=14.34s

  

module DataFrame () description "two-dimensional rich data container"; local columns, rows, data, binder; option object(BaseDataObject); end module

 (4)
> 

EqualEntries(M__ || (1 .. 2))

true

 (5)
> 

 


 

Download longest_paths_in_a_DAG.mw

Unfortunately, I have to wait for almost four minutes in the above instance. Can this task be done in 0.4s?
Please Wait...