Guide to Prolog Programming 
© Roman Barták, 1998 
Home 

Generalized
Algorithm for Graph Search

In this subsection we present a general schema of algorithm for searching graphs. This schema is based on notions of open and closed vertices. The open vertex was visited by the algorithm but it has not been explored/processed yet, while the closed vertex has already been visited and explored.
The algorithm takes some open vertex V and expands it, i.e., the algorithm process the vertex V, finds its neigbourhood, joins this neigbourhood with the rest of open vertices and add this vertex V to the set of closed vertices. Note, that closed vertices are removed from the neigbourhood before joining with open vertices. The algorithm stops as soon as the set of open vertices is empty.
% open_close_search(+Graph,+Open,+Closed,Result) open_close_search(Graph,[],Closed,Result): tune_result(Graph,Closed,Result). open_close_search(Graph,[VertexOpen],Closed,Result): explore(Vertex,Graph,Neighbourhood,ClosedVertex), diff(Neighbourhood,Closed,OpenNB), % remove closed vertices merge(OpenNB,Open,NewOpen), % join with rest open vertices open_close_search(Graph,NewOpen,[ClosedVertexClosed],Result).
The above program contains "hooks", e.g., tune_result or explore, which have to be programed to get a particular algorithm. We show such extensions now (procedures for hooks are labeled by bold text).
First, we program the graph coloring algorithm using the above presented general schema. This algorithm corresponds to the well known algorithm that colors one vertex and, then, it colors the vertex's neighbourhood and so on. Note, that after coloring one graph segment, we have to restart the search in tune_result procedure if there remains other components.
% open_close_coloring(+Graph,+Colors,Coloring) open_close_coloring(Graph,Colors,Coloring): vertices(Graph,[VVertices]), open_close_search(GraphColors,[VColors],[],Coloring). explore(VCs,GraphColors,Neighbourhood,VC): member(C,Cs), % assign color to the vertex neighbourhood(Graph,V,NB), % find neigbourhood delete(C,Colors,NBColors), % prepare possible colors for neighbourhood add_colors(NB,NBColors,Neigbourhood). % assign colors to neighbourhood add_colors([],_,[]). add_colors([VVs],Cs,[VCsCVc]): add_colors(Vs,Cs,CVs). diff([],_,[]). diff([VCsCVs],Closed,NonClosed): (member(V_,Closed) > NonClosed=[VCsRest] ; NonClosed=Rest), diff(CVs,Closed,Rest). merge([],Open,[]). merge([VCsCVs],Open,[VNCsRest]): (member(VOCs,Open) > intersection(Cs,OCs,NCs) % classical set intersection ; NCs=Cs), NCs\=[], % it is possible to assign color merge(CVs,Open,Rest). tune_result(GraphColors,Closed,Result): vertices(Graph,Vertices), add_colors(Vertices,Colors,CVertices), diff(CVertices,Closed,NonClosed), (NonClosed=[CV_] % is there other graph component? > open_close_search(GraphColors,[CV],Closed,Result) ; Result=Closed).
Now, we program the extension of the above open/closed schema that behaves like Dijkstra's algorithm which uses sets of open and closed vertices naturally. Remind, that Dijkstra's algorithm finds minimal distance to all vertices in the graph from given vertex.
% open_close_dijkstra(+Graph,+Start,MinDist) open_close_dijkstra(Graph,Start,MinDist): open_close_search(Graph,[Start0],[],MinDist). explore(VD,Graph,Neigbourhood,VD): neighbourhood(Graph,V,NB), add_dist(NB,D,Neighbourhood). add_dist([],_,[]). add_dist([VD1Vs],D,[VVDRest]): VD is D+D1, add_dist(Vs,D,Rest). diff([],_,[]). diff([VDVDs],Closed,NotClosed): (member(V_,Closed) > NotClosed=[VDRest] ; NotClosed=Rest), diff(VDs,Closed,Rest). merge([],Open,Open). merge([VD1VDs],Open,NewOpen): (del(VD2,Open,RestOpen) > min(D1,D2,D),ins(VD,RestOpen,SOpen) ; ins(VD1,Open,SOpen), merge(VDs,SOpen,NewOpen). del(X,[XT],T). del(X,[YT],Rest):X\=Y,del(X,T,Rest). ins(VD,[],[VD]). ins(VD,[UD1T],[VD,UD1T]):D<=D1. ins(VD,[UD1T],[UD1Rest]):D>D1,ins(VD,T,Rest). tune_result(_,Closed,Closed).


Designed and maintained by Roman Barták 