/*************************/ /* graph operations */ /* (c) R. Bart‡k */ /* 1996,1997 */ /*************************/ % module that implements graph operations % nodes are in the form c(ID,In,Out,Contents) % graph is stored in PROLOG database % functions: add_node(+,+,+,?),del_node(+,?,?,?),ins_new_node(+,+,+,+,+,?) % ins_node(+,+,+),rm_node(+,+,+),join_nodes(+,+,?,?,?) % connect(+,+),disconnect(+,+),diconnect_out_star(+,+) % connect_out_star(+,+),find_cycles(+,[],+,?) % clear_graph,show_graph % example: ?-clear_graph,add_node([],[],1,ID1),add_node([ID1],[],2,ID2),show_graph. add_node(In,Out,Cont,ID):- gen_id(ID), assert(c(ID,In,Out,Cont)), add_in_edge(Out,ID), add_out_edge(In,ID),!. del_node(ID,In,Out,Cont):- retract(c(ID,In,Out,Cont)), del_in_edge(Out,ID), del_out_edge(In,ID),!. ins_new_node(In,Out,Cont,ID1,ID2,ID):- disconnect(ID1,ID2), add_node(In,Out,Cont,ID),!. ins_node(ID,ID1,ID2):- disconnect(ID1,ID2), connect(ID1,ID), connect(ID,ID2),!. rm_node(ID,ID1,ID2):- disconnect(ID1,ID), disconnect(ID,ID2), connect(ID1,ID2),!. join_nodes(ID,ID,In,Out,Cont):- c(ID,In,Out,Cont),!. join_nodes(ID1,ID2,In,Out,Cont):- del_node(ID2,In2,Out2,Cont2), retract(c(ID1,In1,Out1,Cont1)), join_conts(Cont1,Cont2,Cont), join_ins(In2,In1,In,ID1), join_outs(Out2,Out1,Out,ID1), assert(c(ID1,In,Out,Cont)), findall(a,(v(V,ID2,P),set_var(V,ID1,P)),_). connect(ID1,ID2):- add_in_edge([ID2],ID1), add_out_edge([ID1],ID2). disconnect(ID1,ID2):- del_in_edge([ID2],ID1), del_out_edge([ID1],ID2). disconnect_out_star([H|T],ID):- disconnect(ID,H), disconnect_out_star(T,ID). disconnect_out_star([],_). connect_out_star([H|T],ID):- connect(ID,H), connect_out_star(T,ID). connect_out_star([],_). find_cycles(N,Path,Ends,Cycles):- mem(N,Ends) -> Cycles=[[N|Path]] ; (c(N,_,Out,_), find_cycles_list(Out,[N|Path],Ends,Cycles)),!. find_cycles_list([N|T],Path,Ends,Cycles):- find_cycles(N,Path,Ends,C1), append(C1,C2,Cycles), find_cycles_list(T,Path,Ends,C2). find_cycles_list([],_,_,[]). add_in_edge([H|T],ID):- retract(c(H,In,Out,Cont)), add_to_set(ID,In,NewIn), assert(c(H,NewIn,Out,Cont)), add_in_edge(T,ID). add_in_edge([],_). add_out_edge([H|T],ID):- retract(c(H,In,Out,Cont)), add_to_set(ID,Out,NewOut), assert(c(H,In,NewOut,Cont)), add_out_edge(T,ID). add_out_edge([],_). del_in_edge([H|T],ID):- retract(c(H,In,Out,Cont)), del_mem(ID,In,NewIn), assert(c(H,NewIn,Out,Cont)), del_in_edge(T,ID). del_in_edge([],_). del_out_edge([H|T],ID):- retract(c(H,In,Out,Cont)), del_mem(ID,Out,NewOut), assert(c(H,In,NewOut,Cont)), del_out_edge(T,ID). del_out_edge([],_). join_ins([H|T],OldIns,NewIns,ID):- ((mem(H,OldIns);H=ID) -> AuxIns=OldIns ; (add_out_edge([H],ID),AuxIns=[H|OldIns])), join_ins(T,AuxIns,NewIns,ID). join_ins([],Ins,Ins,_). join_outs([H|T],OldOuts,NewOuts,ID):- ((mem(H,OldOuts);H=ID) -> AuxOuts=OldOuts ; (add_in_edge([H],ID),AuxOuts=[H|OldOuts])), join_outs(T,AuxOuts,NewOuts,ID). join_outs([],Outs,Outs,_). del_mem(H,[H|T],T):-!. del_mem(H,[X|T],[X|NT]):- del_mem(H,T,NT). del_mem(_,[],[]). reset_id:- retract(cn(_)), assert(cn(1)). clear_graph:- retractall(c(_,_,_,_)), retractall(v(_,_,_)), reset_id. show_graph:- listing(c),listing(v). cn(1). gen_id(ID):- retract(cn(ID)), ID1 is ID+1, assert(cn(ID1)). mem(X,[X|T]). mem(X,[_|T]):- mem(X,T). add_to_set(X,[X|Rest],[X|Rest]):-!. add_to_set(X,[Y|Rest],[Y|NewRest]):- add_to_set(X,Rest,NewRest). add_to_set(X,[],[X]). retractall(H):- findall(_,retract(H),_).