:- module relation. :- use_module assoc_list, bimap, builtin, int, list, map, private_builtin, queue, require, set, set_bbbtree, stack, std_util. :- type (relation:relation_key) == int. :- type (relation:relation(T)) ---> relation(int, (bimap:bimap(T, int)), (tree234:tree234(int, (set:set(int)))), (tree234:tree234(int, (set:set(int))))) . :- pred relation:to_assoc_list_2((tree234:tree234(int, (set:set(int)))), (list:list(int)), (bimap:bimap(T_1, int)), (list:list((std_util:pair(T_1, T_1))))). :- mode relation:to_assoc_list_2((builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det. :- pred relation:to_key_assoc_list_2((tree234:tree234(int, (set:set(int)))), (list:list(int)), (list:list((std_util:pair(int, int))))). :- mode relation:to_key_assoc_list_2((builtin:in), (builtin:in), (builtin:out)) is det. :- pred relation:domain_sorted_list((relation:relation(T_1)), (list:list(int))). :- mode relation:domain_sorted_list((builtin:in), (builtin:out)) is det. :- pred relation:dfs_2((list:list(int)), (relation:relation(T_1)), (set_bbbtree:set_bbbtree(int)), (list:list(int)), (list:list(int))). :- mode relation:dfs_2((builtin:in), (builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det. :- pred relation:dfs_3((list:list(int)), (relation:relation(T_1)), (set_bbbtree:set_bbbtree(int)), (list:list(int)), (set_bbbtree:set_bbbtree(int)), (list:list(int))). :- mode relation:dfs_3((builtin:in), (builtin:in), (builtin:in), (builtin:in), (builtin:out), (builtin:out)) is det. :- pred relation:is_dag_2((list:list(int)), (relation:relation(T_1)), (set_bbbtree:set_bbbtree(int)), (set_bbbtree:set_bbbtree(int))). :- mode relation:is_dag_2((builtin:in), (builtin:in), (builtin:in), (builtin:in)) is semidet. :- pred relation:components_2((relation:relation(T_1)), (list:list(int)), (set:set((set:set(int)))), (set:set((set:set(int))))). :- mode relation:components_2((builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det. :- pred relation:tsort_2((relation:relation(T_1)), (list:list(int))). :- mode relation:tsort_2((builtin:in), (builtin:out)) is semidet. :- pred relation:traverse_nodes((list:list(K_1)), (relation:relation(K_1)), pred(K_1, T_2, T_2), pred(K_1, K_1, T_2, T_2), T_2, T_2). :- mode relation:traverse_nodes((builtin:in), (builtin:in), (pred((builtin:in), (builtin:di), (builtin:uo)) is det), (pred((builtin:in), (builtin:in), (builtin:di), (builtin:uo)) is det), (builtin:di), (builtin:uo)) is det. :- mode relation:traverse_nodes((builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (pred((builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det), (builtin:in), (builtin:out)) is det. :- pred relation:traverse_children((list:list(int)), K_1, (relation:relation(K_1)), pred(K_1, K_1, T_2, T_2), T_2, T_2). :- mode relation:traverse_children((builtin:in), (builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:di), (builtin:uo)) is det), (builtin:di), (builtin:uo)) is det. :- mode relation:traverse_children((builtin:in), (builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det), (builtin:in), (builtin:out)) is det. relation:init((relation:relation(V_5, ElMap_2, FwdMap_3, BwdMap_4))) :- V_5 = 0, bimap:init(ElMap_2), map:init(FwdMap_3), map:init(BwdMap_4). relation:init = R_2 :- relation:init(R_2). relation:search_element((relation:relation(_Key_4, ElMap_5, _Fwd_6, _Rev_7)), Elem_8, Key_9) :- bimap:search(ElMap_5, Elem_8, Key_9). relation:lookup_element(R_4, X_5) = K_6 :- relation:lookup_element(R_4, X_5, K_6). relation:search_key((relation:relation(_Key_4, ElMap_5, _Fwd_6, _Rev_7)), Key_8, Elem_9) :- bimap:search(ElMap_5, Elem_9, Key_8). relation:lookup_key(R_4, K_5) = X_6 :- relation:lookup_key(R_4, K_5, X_6). relation:add(R1_5, K1_6, K2_7) = R2_8 :- relation:add(R1_5, K1_6, K2_7, R2_8). relation:add_values(R0_5, X_6, Y_7, R_8) :- relation:add_element(R0_5, X_6, XKey_9, R1_10), relation:add_element(R1_10, Y_7, YKey_11, R2_12), relation:add(R2_12, XKey_9, YKey_11, R_8). relation:add_values(R1_5, X_6, Y_7) = R2_8 :- relation:add_values(R1_5, X_6, Y_7, R2_8). relation:add_assoc_list(R1_4, AL_5) = R2_6 :- relation:add_assoc_list(R1_4, AL_5, R2_6). relation:remove(R1_5, K1_6, K2_7) = R2_8 :- relation:remove(R1_5, K1_6, K2_7, R2_8). relation:remove_assoc_list(R1_4, AL_5) = R2_6 :- relation:remove_assoc_list(R1_4, AL_5, R2_6). relation:lookup((relation:relation(_Key_4, _ElMap_5, Fwd_6, _Bwd_7)), U_8, V_9) :- map:search(Fwd_6, U_8, VSet_10), set:member(V_9, VSet_10). relation:reverse_lookup((relation:relation(_Key_4, _ElMap_5, _Fwd_6, Bwd_7)), U_8, V_9) :- map:search(Bwd_7, V_9, USet_10), set:member(U_8, USet_10). relation:lookup_from((relation:relation(_Key_4, _ElMap_5, Fwd_6, _Bwd_7)), U_8, Vs_9) :- (if map:search(Fwd_6, U_8, Vs0_10) then Vs_9 = Vs0_10 else set:init(Vs_9) ). relation:lookup_from(R_4, K_5) = S_6 :- relation:lookup_from(R_4, K_5, S_6). relation:lookup_to((relation:relation(_Key_4, _ElMap_5, _Fwd_6, Bwd_7)), V_8, Us_9) :- (if map:search(Bwd_7, V_8, Us0_10) then Us_9 = Us0_10 else set:init(Us_9) ). relation:lookup_to(R_4, K_5) = S_6 :- relation:lookup_to(R_4, K_5, S_6). relation:to_assoc_list((relation:relation(_Key_3, ElMap_4, Fwd_5, _Bwd_6)), List_7) :- map:keys(Fwd_5, FwdKeys_8), relation:to_assoc_list_2(Fwd_5, FwdKeys_8, ElMap_4, List_7). relation:to_assoc_list(R_3) = AL_4 :- relation:to_assoc_list(R_3, AL_4). relation:to_key_assoc_list((relation:relation(_Key_3, _ElMap_4, Fwd_5, _Bwd_6)), List_7) :- map:keys(Fwd_5, FwdKeys_8), relation:to_key_assoc_list_2(Fwd_5, FwdKeys_8, List_7). relation:to_key_assoc_list(R_3) = AL_4 :- relation:to_key_assoc_list(R_3, AL_4). relation:from_assoc_list(AL_3) = R_4 :- relation:from_assoc_list(AL_3, R_4). relation:domain((relation:relation(_Key_3, ElMap_4, _Fwd_5, _Bwd_6)), Dom_7) :- bimap:ordinates(ElMap_4, DomList_8), set:sorted_list_to_set(DomList_8, Dom_7). relation:domain(R_3) = S_4 :- relation:domain(R_3, S_4). relation:inverse((relation:relation(Key_3, ElMap_4, Fwd_5, Bwd_6)), (relation:relation(Key_3, ElMap_4, Bwd_6, Fwd_5))). relation:inverse(R1_3) = R2_4 :- relation:inverse(R1_3, R2_4). relation:compose(R1_4, R2_5) = R3_6 :- relation:compose(R1_4, R2_5, R3_6). relation:dfs(Rel_4, X_5, Dfs_6) :- relation:dfsrev(Rel_4, X_5, DfsRev_7), list:reverse(DfsRev_7, Dfs_6). relation:dfs(R_4, K_5) = Ks_6 :- relation:dfs(R_4, K_5, Ks_6). relation:dfsrev(R_4, K_5) = Ks_6 :- relation:dfsrev(R_4, K_5, Ks_6). relation:dfs(Rel_3, Dfs_4) :- relation:dfsrev(Rel_3, DfsRev_5), list:reverse(DfsRev_5, Dfs_4). relation:dfs(R_3) = Ks_4 :- relation:dfs(R_3, Ks_4). relation:dfsrev(Rel_3, DfsRev_4) :- relation:domain_sorted_list(Rel_3, DomList_5), set_bbbtree:init(Visit_6), V_7 = list:[], relation:dfs_2(DomList_5, Rel_3, Visit_6, V_7, DfsRev_4). relation:dfsrev(R_3) = Ks_4 :- relation:dfsrev(R_3, Ks_4). relation:dfs(Rel_6, X_7, Visited0_8, Visited_9, Dfs_10) :- relation:dfsrev(Rel_6, X_7, Visited0_8, Visited_9, DfsRev_11), list:reverse(DfsRev_11, Dfs_10). relation:dfsrev(Rel_6, X_7, Visited0_8, Visited_9, DfsRev_10) :- V_11 = list:[X_7 | V_13], V_13 = list:[], V_12 = list:[], relation:dfs_3(V_11, Rel_6, Visited0_8, V_12, Visited_9, DfsRev_10). relation:is_dag(R_2) :- relation:domain_sorted_list(R_2, DomList_3), set_bbbtree:init(Visit_4), set_bbbtree:init(AllVisit_5), relation:is_dag_2(DomList_3, R_2, Visit_4, AllVisit_5). relation:components(Rel_3, Set_4) :- relation:domain_sorted_list(Rel_3, DomList_5), set:init(Comp0_6), relation:components_2(Rel_3, DomList_5, Comp0_6, Set_4). relation:components(R_3) = KSS_4 :- relation:components(R_3, KSS_4). relation:cliques(R_3) = KSS_4 :- relation:cliques(R_3, KSS_4). relation:reduced(R1_3) = R2_4 :- relation:reduced(R1_3, R2_4). relation:tsort(Rel_3, Tsort_4) :- relation:tsort_2(Rel_3, Tsort0_5), V_6 = relation:lookup_key(Rel_3), list:map(V_6, Tsort0_5, Tsort_4). relation:atsort(R_3) = Ss_4 :- relation:atsort(R_3, Ss_4). relation:sc(Rel_3, Sc_4) :- relation:inverse(Rel_3, Inv_5), relation:to_key_assoc_list(Inv_5, InvList_6), relation:add_assoc_list(Rel_3, InvList_6, Sc_4). relation:sc(R1_3) = R2_4 :- relation:sc(R1_3, R2_4). relation:tc(R1_3) = R2_4 :- relation:tc(R1_3, R2_4). relation:rtc(R1_3) = R2_4 :- relation:rtc(R1_3, R2_4). relation:traverse(Relation_6, ProcessNode_7, ProcessEdge_8, DCG_0_10, DCG_1_11) :- Domain_9 = set:to_sorted_list(V_12), V_12 = relation:domain(Relation_6), relation:traverse_nodes(Domain_9, Relation_6, ProcessNode_7, ProcessEdge_8, DCG_0_10, DCG_1_11). relation:domain_sorted_list((relation:relation(_Key_3, ElMap_4, _Fwd_5, _Bwd_6)), Dom_7) :- bimap:coordinates(ElMap_4, Dom_7). relation:traverse_nodes((list:[]), V_7, V_8, V_9, DCG_0_10, DCG_1_11) :- DCG_0_10 = DCG_1_11. relation:traverse_nodes((list:[Node_12 | Nodes_13]), Relation_14, ProcessNode_15, ProcessEdge_16, DCG_0_18, DCG_3_21) :- Children_17 = set:to_sorted_list(V_22), V_22 = relation:lookup_from(Relation_14, V_23), V_23 = relation:lookup_element(Relation_14, Node_12), call(ProcessNode_15, Node_12, DCG_0_18, DCG_1_19), relation:traverse_children(Children_17, Node_12, Relation_14, ProcessEdge_16, DCG_1_19, DCG_2_20), relation:traverse_nodes(Nodes_13, Relation_14, ProcessNode_15, ProcessEdge_16, DCG_2_20, DCG_3_21). relation:traverse_children((list:[]), V_7, V_8, V_9, DCG_0_10, DCG_1_11) :- DCG_0_10 = DCG_1_11. relation:traverse_children((list:[ChildKey_12 | Children_13]), Parent_14, Relation_15, ProcessEdge_16, DCG_0_18, DCG_2_20) :- Child_17 = relation:lookup_key(Relation_15, ChildKey_12), call(ProcessEdge_16, Parent_14, Child_17, DCG_0_18, DCG_1_19), relation:traverse_children(Children_13, Parent_14, Relation_15, ProcessEdge_16, DCG_1_19, DCG_2_20). :- pragma termination_info(relation:init((builtin:out)), infinite, can_loop). :- pragma termination_info((relation:init) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:add_element((builtin:in), (builtin:in), (builtin:out), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:search_element((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_element((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_element((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:search_key((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_key((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_key((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:add((builtin:in), (builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:add((builtin:in), (builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:add_values((builtin:in), (builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:add_values((builtin:in), (builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:add_assoc_list((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:add_assoc_list((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:remove((builtin:in), (builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:remove((builtin:in), (builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:remove_assoc_list((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:remove_assoc_list((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:lookup((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup((builtin:in), (builtin:in), (builtin:in)), finite(0, [no, no, no, no]), can_loop). :- pragma termination_info(relation:reverse_lookup((builtin:in), (builtin:out), (builtin:in)), infinite, can_loop). :- pragma termination_info(relation:reverse_lookup((builtin:in), (builtin:in), (builtin:in)), finite(0, [no, no, no, no]), can_loop). :- pragma termination_info(relation:lookup_from((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_from((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:lookup_to((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:lookup_to((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:to_assoc_list((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:to_assoc_list((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:to_key_assoc_list((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:to_key_assoc_list((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:from_assoc_list((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:from_assoc_list((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:domain((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:domain((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:inverse((builtin:in), (builtin:out)), finite(0, [no, yes, no]), cannot_loop). :- pragma termination_info(relation:inverse((builtin:in)) = (builtin:out), finite(0, [no, yes, no]), cannot_loop). :- pragma termination_info(relation:compose((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:compose((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:dfs((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:dfs((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:dfsrev((builtin:in), (builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:dfsrev((builtin:in), (builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:dfs((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:dfs((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:dfsrev((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:dfsrev((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:dfs((builtin:in), (builtin:in), (builtin:in), (builtin:out), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:dfsrev((builtin:in), (builtin:in), (builtin:in), (builtin:out), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:is_dag((builtin:in)), finite(0, [no, no]), can_loop). :- pragma termination_info(relation:components((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:components((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:cliques((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:cliques((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:reduced((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:reduced((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:tsort((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:atsort((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:atsort((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:sc((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:sc((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:tc((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:tc((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:rtc((builtin:in), (builtin:out)), infinite, can_loop). :- pragma termination_info(relation:rtc((builtin:in)) = (builtin:out), infinite, can_loop). :- pragma termination_info(relation:traverse((builtin:in), (pred((builtin:in), (builtin:di), (builtin:uo)) is det), (pred((builtin:in), (builtin:in), (builtin:di), (builtin:uo)) is det), (builtin:di), (builtin:uo)), infinite, can_loop). :- pragma termination_info(relation:traverse((builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (pred((builtin:in), (builtin:in), (builtin:in), (builtin:out)) is det), (builtin:in), (builtin:out)), infinite, can_loop).