Discontinuous graph in prolog -


i'm struggleing logic programming. have problem , hope of can me it. discontinous graph represented facts way:

h(0,1). h(1,2). h(3,4). h(3,5). 

so there 2 separate graphs. separate components on output represented list. if there 3 separate components in graph, there 3 lists. given example above, expected output [[0,1,2],[3,4,5]].

in answer use ugraphs—a available1 library handling unweighted graphs.

 :- use_module(library(ugraphs)). 

first, need data form compatible library(ugraphs):

 relation2_ugraph(r_2, g) :-    findall(x-y, call(r_2,x,y), es0),    (  ground(es0)    -> sort(es0, es),                      % remove duplicates (if any)       vertices_edges_to_ugraph([], es, g)    ;  throw(error(instantiation_error,_))    ). 

we can utilize reachable/3 , del_vertices/3 finding connected components:

 ugraph_components([]) --> []. ugraph_components([v-es|ves]) -->     { reachable(v, [v-es|ves], vs),      del_vertices([v-es|ves], vs, g) },    [vs],    ugraph_components(g). 

sample query using sicstus prolog 4.3.2:

 | ?- relation2_ugraph(symm(h), g),      phrase(ugraph_components(g), ccs). g   = [0-[1],1-[0,2],2-[1],3-[4,5],4-[3],5-[3]], ccs = [[0,1,2],[3,4,5]] ? ;               % non-determinism?! don't worry2! no 

exactly answer op wanted!


footnote 1: library(ugraphs) offered out-of-the-box sicstus prolog, swi-prolog , yap prolog.
footnote 2: goals do succeed deterministically. this ingenious way utilizes call_cleanup/2 show it.


Comments

Popular posts from this blog

get url and add instance to a model with prefilled foreign key :django admin -

css - Make div keyboard-scrollable in jQuery Mobile? -

ruby on rails - Seeing duplicate requests handled with Unicorn -