1/*  Part of ClioPatria SeRQL and SPARQL server
   2
   3    Author:        Jan Wielemaker
   4    E-mail:        J.Wielemaker@cs.vu.nl
   5    WWW:           http://www.swi-prolog.org
   6    Copyright (C): 2007-2010, University of Amsterdam,
   7			      VU University Amsterdam
   8
   9    This program is free software; you can redistribute it and/or
  10    modify it under the terms of the GNU General Public License
  11    as published by the Free Software Foundation; either version 2
  12    of the License, or (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public
  20    License along with this library; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22
  23    As a special exception, if you link this library with other files,
  24    compiled with a Free Software compiler, to produce an executable, this
  25    library does not by itself cause the resulting executable to be covered
  26    by the GNU General Public License. This exception does not however
  27    invalidate any other reasons why the executable file might be covered by
  28    the GNU General Public License.
  29*/
  30
  31:- module(rdf_abstract,
  32	  [ merge_sameas_graph/3,	% +GraphIn, -GraphOut, +Options
  33	    bagify_graph/4,		% +GraphIn, -GraphOut, -Bags, +Options
  34	    abstract_graph/3,		% +GraphIn, -GraphOut, +Options
  35	    minimise_graph/2,		% +GraphIn, -GraphOut
  36
  37	    graph_resources/2,		% +Graph, -Resources
  38	    graph_resources/4		% +Graph, -Resources, -Predicates, -Types
  39	  ]).
  40:- use_module(library(semweb/rdf_db)).
  41:- use_module(library(semweb/rdfs)).
  42:- use_module(library(assoc)).
  43:- use_module(library(option)).
  44:- use_module(library(pairs)).
  45:- use_module(library(ordsets)).
  46:- use_module(library(debug)).
  47:- use_module(library(apply)).
  48:- use_module(library(lists)).
  49:- use_module(library(settings)).
  50
  51/** <module> Abstract RDF graphs
  52
  53The task of this module is to do some simple manipulations on RDF graphs
  54represented as lists of rdf(S,P,O).  Supported operations:
  55
  56	* merge_sameas_graph(+GraphIn, -GraphOut, +Options)
  57	Merge nodes by owl:sameAs
  58
  59	* bagify_graph(+GraphIn, -GraphOut, -Bags, +Options)
  60	Bagify a graph, returning a new graph holding bags of resources
  61	playing a similar role in the graph.
  62
  63	* abstract_graph(+GraphIn, -GraphOut, +Options)
  64	Abstract nodes or edges using rdf:type, rdfs:subClassOf and/or
  65	rdfs:subPropertyOf
  66*/
  67
  68%%	merge_sameas_graph(GraphIn, GraphOut, +Options) is det.
  69%
  70%	Collapse nodes in GraphIn that are   related through an identity
  71%	mapping.  By  default,  owl:sameAs  is  the  identity  relation.
  72%	Options defines:
  73%
  74%	    * predicate(-PredOrList)
  75%	    Use an alternate or list of predicates that are to be
  76%	    treated as identity relations.
  77%
  78%	    * sameas_mapped(-Assoc)
  79%	    Assoc from resources to the resource it was mapped to.
  80
  81:- rdf_meta
  82	merge_sameas_graph(+, -, t).
  83
  84merge_sameas_graph(GraphIn, GraphOut, Options) :-
  85	sameas_spec(Options, SameAs),
  86	sameas_map(GraphIn, SameAs, Assoc),		% R->EqSet
  87	(   empty_assoc(Assoc)
  88	->  GraphOut = GraphIn,
  89	    empty_assoc(EqMap)
  90	;   assoc_to_list(Assoc, List),
  91	    pairs_values(List, EqSets),
  92	    sort(EqSets, UniqueEqSets),
  93	    map_list_to_pairs(rdf_representative, UniqueEqSets, Keyed),	% Repr-EqSet
  94	    representer_map(Keyed, EqMap),
  95	    map_graph(GraphIn, EqMap, GraphOut),
  96	    (	debugging(abstract)
  97	    ->	length(GraphIn, Before),
  98		length(GraphOut, After),
  99		debug(abstract, 'owl:sameAs reduction: ~D --> ~D edges', [Before, After])
 100	    ;	true
 101	    )
 102	),
 103	option(sameas_mapped(EqMap), Options, _).
 104
 105sameas_spec(Options, SameAs) :-
 106	rdf_equal(owl:sameAs, OwlSameAs),
 107	option(predicate(SameAs0), Options, OwlSameAs),
 108	(   is_list(SameAs0)
 109	->  SameAs = SameAs0
 110	;   SameAs = [SameAs0]
 111	).
 112
 113%%	sameas_map(+Graph, +SameAs, -Map:assoc) is det.
 114%
 115%	Create an assoc with R->Set, where   Set contains an ordered set
 116%	of resources equivalent to R.
 117
 118sameas_map(Graph, SameAs, Assoc) :-
 119	empty_assoc(Assoc0),
 120	sameas_map(Graph, SameAs, Assoc0, Assoc).
 121
 122sameas_map([], _, Assoc, Assoc).
 123sameas_map([rdf(S, P, O)|T], SameAs, Assoc0, Assoc) :-
 124	same_as(P, SameAs),
 125	S \== O, !,
 126	(   get_assoc(S, Assoc0, SetS)
 127	->  (   get_assoc(O, Assoc0, SetO)
 128	    ->	ord_union(SetO, SetS, Set)
 129	    ;	ord_union([O], SetS, Set)
 130	    )
 131	;   (   get_assoc(O, Assoc0, SetO)
 132	    ->	ord_union([S], SetO, Set)
 133	    ;   sort([S,O], Set)
 134	    )
 135	),
 136	putall(Set, Assoc0, Set, Assoc1),
 137	sameas_map(T, SameAs, Assoc1, Assoc).
 138sameas_map([_|T], SameAs, Assoc0, Assoc) :-
 139	sameas_map(T, SameAs, Assoc0, Assoc).
 140
 141putall([], Assoc, _, Assoc).
 142putall([H|T], Assoc0, Value, Assoc) :-
 143	put_assoc(H, Assoc0, Value, Assoc1),
 144	putall(T, Assoc1, Value, Assoc).
 145
 146
 147%%	same_as(+Predicate:resource, +SameAs:list) is semidet.
 148%
 149%	True if Predicate expresses a same-as mapping.
 150
 151same_as(P, Super) :-
 152	member(S, Super),
 153	rdfs_subproperty_of(P, S), !.
 154
 155
 156%%	representer_map(+List:list(Repr-Set), -Assoc) is det.
 157%
 158%	Assoc maps all elements of Set to its representer.
 159
 160representer_map(Keyed, EqMap) :-
 161	empty_assoc(Assoc0),
 162	representer_map(Keyed, Assoc0, EqMap).
 163
 164representer_map([], Assoc, Assoc).
 165representer_map([R-Set|T], Assoc0, Assoc) :-
 166	putall(Set, Assoc0, R, Assoc1),
 167	representer_map(T, Assoc1, Assoc).
 168
 169
 170		 /*******************************
 171		 *	       BAGIFY		*
 172		 *******************************/
 173
 174%%	bagify_graph(+GraphIn, -GraphOut, -Bags, +Options) is det.
 175%
 176%	If a graph contains multiple objects of the same type (class) in
 177%	the same location in the graph (i.e.   all  links are the same),
 178%	create a *bag*. The bag is   represented by a generated resource
 179%	of type rdf:Bag and the RDF for the   bags  is put in Bags. I.e.
 180%	appending GraphOut and Bags provides a proper RDF model. Options
 181%	provides additional abstraction properties.  In particular:
 182%
 183%	    * class(+Class)
 184%	    Try to bundle objects under Class rather than their
 185%	    rdf:type.  Multiple of these options may be defined
 186%
 187%	    * property(+Property)
 188%	    Consider predicates that are an rdfs:subPropertyOf
 189%	    Property the same relations.
 190%
 191%	    * bagify_literals(+Bool)
 192%	    If =true= (default), also try to put literals into a
 193%	    bag.  Works well to collapse non-preferred labels.
 194%
 195%	@tbd Handle the property option
 196
 197:- rdf_meta
 198	bagify_graph(+, -, -, t).
 199
 200bagify_graph(GraphIn, GraphOut, Bags, Options) :-
 201	canonise_options(Options, Options1),
 202	partition_options(class, Options1, ClassOptions, Options2),
 203	graph_node_edges(GraphIn, AssocNodesToEdges, Options2),
 204	assoc_to_list(AssocNodesToEdges, NodesToEdges),
 205	pairs_keys(NodesToEdges, Nodes),
 206	group_resources_by_class(Nodes, ByClass, ClassOptions),
 207	resource_bags(ByClass, NodesToEdges, RawBags),
 208	(   debugging(abstract)
 209	->  length(RawBags, Len),
 210	    maplist(length, RawBags, BagLens),
 211	    sumlist(BagLens, ObjCount),
 212	    debug(abstract, 'Created ~D bags holding ~D objects', [Len, ObjCount])
 213	;   true
 214	),
 215	assign_bagids(RawBags, IDBags),
 216	representer_map(IDBags, Assoc),
 217	map_graph(GraphIn, Assoc, GraphOut0),
 218	merge_properties(GraphOut0, GraphOut, Options2),
 219	make_rdf_graphs(IDBags, Bags).
 220
 221partition_options(Name, Options, WithName, WithoutName) :-
 222	partition(option_name(Name), Options, WithName, WithoutName).
 223
 224option_name(Name, Option) :-
 225	functor(Option, Name, 1).
 226
 227%%	canonise_options(+OptionsIn, -OptionsOut) is det.
 228%
 229%	Rewrite option list from possible Name=Value to Name(Value)
 230
 231canonise_options(In, Out) :-
 232	memberchk(_=_, In), !,		% speedup a bit if already ok.
 233	canonise_options2(In, Out).
 234canonise_options(Options, Options).
 235
 236canonise_options2([], []).
 237canonise_options2([Name=Value|T0], [H|T]) :- !,
 238	H =.. [Name,Value],
 239	canonise_options2(T0, T).
 240canonise_options2([H|T0], [H|T]) :- !,
 241	canonise_options2(T0, T).
 242
 243
 244
 245
 246%%	group_resources_by_class(+Resources, -ByClass, +Options) is det.
 247%
 248%	ByClass is a list of lists of  resources that belong to the same
 249%	class. First step we process the classes specified in Options.
 250
 251group_resources_by_class([], [], _) :- !.
 252group_resources_by_class(Resources, ByClass, Options) :-
 253	select_option(class(Class), Options, Options1), !,
 254	(   partition(has_class(sub_class, Class), Resources, InClass, NotInClass),
 255	    InClass \== []
 256	->  ByClass = [InClass|ByClass1],
 257	    group_resources_by_class(NotInClass, ByClass1, Options1)
 258	;   group_resources_by_class(Resources, ByClass, Options1)
 259	).
 260group_resources_by_class([H|T0], [[H|S]|T], Options) :-
 261	class_of(H, exact, Class),
 262	partition(has_class(exact, Class), T0, S, T1),
 263	group_resources_by_class(T1, T, Options).
 264
 265%%	has_class(+Match, +Class, +Node) is semidet.
 266
 267has_class(Match, Class, Node) :-
 268	class_of(Node, Match, Class).
 269
 270%%	class_of(+Node, +Match, -Class) is det.
 271%%	class_of(+Node, +Match, +Class) is semidet.
 272
 273class_of(Node, sub_class, Class) :- !,
 274	rdfs_individual_of(Node, Class), !.
 275class_of(literal(_), exact, Literal) :- !,
 276	rdf_equal(Literal, rdfs:'Literal').
 277class_of(R, exact, Class) :-
 278	rdf_has(R, rdf:type, Class), !.
 279class_of(_, exact, Class) :-
 280	rdf_equal(Class, rdfs:'Resource').
 281
 282
 283%%	resource_bags(+ByClass:list(list(resource)),
 284%%		      +NodeToEdges:list(node-list(edges)),
 285%%		      -RawBags:list(list(resource))) is det.
 286%
 287%	Find bags of resources that have the same connections.
 288
 289resource_bags(ByClass, NodeToEdges, Bags) :-
 290	phrase(resource_bags(ByClass, NodeToEdges), Bags).
 291
 292resource_bags([], _) -->
 293	[].
 294resource_bags([ByClassH|ByClassT], NodeToEdges) -->
 295	{ sort(ByClassH, SortedNodes),
 296	  ord_subkeys(SortedNodes, NodeToEdges, SubNodeToEdges),
 297	  same_edges(SubNodeToEdges, Bags)
 298	},
 299	Bags,
 300	resource_bags(ByClassT, NodeToEdges).
 301
 302%%	ord_subkeys(+Keys, +Pairs, -SubPairs) is det.
 303%
 304%	SubPairs is the sublist of Pairs with a key in Keys.
 305%
 306%	@param Keys	Sorted list of keys
 307%	@param Pairs	Key-sorted pair-list
 308%	@param SubPairs	Key-sorted pair-list
 309
 310ord_subkeys([], _, []).
 311ord_subkeys([K|KT], [P|PT], Pairs) :-
 312	P = PK-_,
 313	compare(Diff, K, PK),
 314	ord_subkeys(Diff, K, KT, P, PT, Pairs).
 315
 316ord_subkeys(=, _, KT, P, PT, [P|Pairs]) :- !,
 317	ord_subkeys(KT, PT, Pairs).
 318ord_subkeys(<, _, [K|KT], P, PT, Pairs) :-
 319	P = PK-_,
 320	compare(Diff, K, PK),
 321	ord_subkeys(Diff, K, KT, P, PT, Pairs).
 322ord_subkeys(>, K, KT, _, [P|PT], Pairs) :-
 323	P = PK-_,
 324	compare(Diff, K, PK),
 325	ord_subkeys(Diff, K, KT, P, PT, Pairs).
 326
 327
 328%%	same_edges(+NodeToEdges:list(node-edges), -Bags:list(list)) is det.
 329%
 330%	Bags is a list of lists of resources (nodes) that share the same
 331%	(abstracted) edges with the rest of the graph.
 332
 333same_edges(NodeToEdges, Bags) :-
 334	transpose_pairs(NodeToEdges, ByEdges),		% list(edges-node)
 335	keysort(ByEdges, Sorted),
 336	group_pairs_by_key(Sorted, Grouped),
 337	pairs_values(Grouped, AllBySameEdge),
 338	include(longer_than_one, AllBySameEdge, Bags).
 339
 340longer_than_one([_,_|_]).
 341
 342%%	graph_node_edges(+Graph, -NodeEdges:assoc, +Options) is det.
 343%
 344%	NodeEdges is an assoc from resource to a sorted list of involved
 345%	triples. Only subject and objects are considered.
 346%
 347%	Processes =bagify_literals= and =property= options
 348
 349graph_node_edges(Graph, Assoc, Options) :-
 350	option(bagify_literals(LitToo), Options, true),
 351	property_map(Options, Map0),
 352	empty_assoc(Assoc0),
 353	graph_node_edges(Graph, LitToo, Map0, Assoc0, Assoc1),
 354	map_assoc(sort, Assoc1, Assoc).
 355
 356graph_node_edges([], _, _, Assoc, Assoc).
 357graph_node_edges([rdf(S,P,O)|T], LitToo, Map, Assoc0, Assoc) :-
 358	abstract_property(P, Map, SP, Map1),
 359	add_assoc(S, Assoc0, rdf(-, SP, O), Assoc1),
 360	(   (atom(O) ; LitToo == true )
 361	->  add_assoc(O, Assoc1, rdf(S, SP, -), Assoc2)
 362	;   Assoc2 = Assoc1
 363	),
 364	graph_node_edges(T, LitToo, Map1, Assoc2, Assoc).
 365
 366add_assoc(Key, Assoc0, Value, Assoc) :-
 367	get_assoc(Key, Assoc0, Old, Assoc, [Value|Old]), !.
 368add_assoc(Key, Assoc0, Value, Assoc) :-
 369	put_assoc(Key, Assoc0, [Value], Assoc).
 370
 371
 372%%	property_map(+Options, -Map:assoc(P-Super))
 373%
 374%	Process the options, creating a map that replaces a property by
 375%	its registered super.
 376
 377property_map(Options, Map) :-
 378	empty_assoc(Map0),
 379	property_map(Options, Map0, Map).
 380
 381property_map([], Map, Map).
 382property_map([property(P)|T], Map0, Map) :- !,
 383	(   rdfs_subproperty_of(P, Super),
 384	    get_assoc(Super, Map0, Root)
 385	->  put_assoc(P, Map0, Root, Map1)
 386	;   put_assoc(P, Map0, P, Map1)
 387	),
 388	property_map(T, Map1, Map).
 389property_map([_|T], Map0, Map) :-
 390	property_map(T, Map0, Map).
 391
 392%%	abstract_property(+P0, +Map0, -P, -Map) is det.
 393%
 394%	Find the abstract property for some property P.
 395
 396abstract_property(P0, Map0, P, Map) :-
 397	get_assoc(P0, Map0, P), !,
 398	Map = Map0.
 399abstract_property(P, Map0, Root, Map) :-
 400	rdfs_subproperty_of(P, Super),
 401	get_assoc(Super, Map0, Root), !,
 402	debug(abstract(property), 'Mapped ~p --> ~p', [P, Root]),
 403	put_assoc(P, Map0, Root, Map).
 404abstract_property(P, Map, P, Map).
 405
 406
 407%%	assign_bagids(+Bags:list(bag), -IDBags:list(id-bag)).
 408%
 409%	Assign bag identifiers to the each bag in Bags.
 410
 411assign_bagids(Bags, IDBags) :-
 412	assign_bagids(Bags, 1, IDBags).
 413
 414assign_bagids([], _, []).
 415assign_bagids([H|T0], I, [Id-H|T]) :-
 416	atom_concat('_:bag_', I, Id),
 417	I2 is I + 1,
 418	assign_bagids(T0, I2, T).
 419
 420
 421%%	make_rdf_graphs(+IDBags, -RDFBags) is det.
 422%
 423%	Translate BagID-Members into an RDF graph.
 424
 425:- rdf_meta
 426	statement(r,r,o,?,?).			% statement//3
 427
 428make_rdf_graphs(IDBags, RDFBags) :-
 429	phrase(make_rdf_graphs(IDBags), RDFBags).
 430
 431make_rdf_graphs([]) -->
 432	[].
 433make_rdf_graphs([ID-Members|T]) -->
 434	statement(ID, rdf:type, rdf:'Bag'),
 435	bag_members(Members, 0, ID),
 436	make_rdf_graphs(T).
 437
 438bag_members([], _, _) -->
 439	[].
 440bag_members([H|T], I, ID) -->
 441	{ I2 is I + 1,
 442	  atom_concat('_:', I, P)
 443	},
 444	statement(ID, P, H),
 445	bag_members(T, I2, ID).
 446
 447statement(S, P, O) -->
 448	[ rdf(S, P, O) ].
 449
 450
 451
 452		 /*******************************
 453		 *	 MERGE PROPERTIES	*
 454		 *******************************/
 455
 456%%	merge_properties(+GraphIn, -GraphOut, +Options) is det.
 457%
 458%	Merge equivalent properties joining the same nodes.  They are
 459%	replaced by their common ancestors.
 460%
 461%	@param GraphIn	List of rdf(S,P,O)
 462%	@param GraphOut List of rdf(S,P,O)
 463%	@param Options  Option list (unused)
 464
 465merge_properties([], [], _).
 466merge_properties([rdf(S,P,O)|GraphIn], GraphOut, Options) :-
 467	memberchk(rdf(S,_,O), GraphIn), !,
 468	partition(same_so(S,O), GraphIn, Same, Rest),
 469	maplist(pred, Same, Preds),
 470	sort([P|Preds], UniquePreds),
 471	common_ancestor_forest(sub_property_of, UniquePreds, Forest),
 472	pairs_keys(Forest, Roots),
 473	debug(abstract, 'Merged ~p --> ~p', [UniquePreds, Roots]),
 474	mk_p_triples(Roots, S, O, GraphOut, Out2),
 475	merge_properties(Rest, Out2, Options).
 476merge_properties([Triple|GraphIn], [Triple|GraphOut], Options) :-
 477	merge_properties(GraphIn, GraphOut, Options).
 478
 479same_so(S, O, rdf(S, _, O)).
 480pred(rdf(_,P,_), P).
 481
 482mk_p_triples([], _, _) --> [].
 483mk_p_triples([P|T], S, O) -->
 484	[rdf(S,P,O)],
 485	mk_p_triples(T, S, O).
 486
 487sub_property_of(P, Super) :-
 488	rdf_has(P, rdfs:subPropertyOf, Super).
 489
 490
 491%%	common_ancestor_forest(:Pred, +Objects, -Forest) is det.
 492%
 493%	Forest is a minimal set  of   minimal  spanning  trees with real
 494%	branching (more than one child per   node) covering all Objects.
 495%	The partial ordering is defined   by  the non-deterministic goal
 496%	call(Pred, +Node, -Parent).
 497%
 498%		* Build up a graph represented as Node->Children and
 499%		a list of roots.  The initial list of roots is Objects.
 500%		The graph is built using breath-first search to minimize
 501%		depth.
 502%
 503%		* Once we have all roots, we delete all branches that
 504%		have only a single child.
 505%
 506%	@param	Forest	is a list of trees.  Each tree is represented
 507%		as Root-Children, where Children is a possibly
 508%		empty list if sub-trees.
 509%
 510%	@tbd	First prune dead-ends?
 511%
 512%		==
 513%		rdf_db:rdf_global_term([ulan:assisted_by, ulan:cousin_of], In),
 514%		gtrace,
 515%		rdf_abstract:common_ancestor_forest(sub_property_of, In, Out).
 516%		==
 517
 518:- meta_predicate
 519	common_ancestor_forest(2, +, -).
 520
 521common_ancestor_forest(Pred, Objects, Forest) :-
 522	strip_module(Pred, M, P),
 523	sort(Objects, Objects1),
 524	keys_to_assoc(Objects1, target*[], Nodes0),
 525	ancestor_tree(Objects1, M:P, Nodes0, Nodes, Roots),
 526	prune_forest(Nodes, Roots, Forest),
 527	debug(common_ancestor, 'Ancestors of ~p: ~p', [Objects1, Forest]).
 528
 529%%	keys_to_assoc(+Keys:list, +Value, -Assoc) is det.
 530%
 531%	True if Assoc is an assoc where each Key maps to Value.
 532
 533keys_to_assoc(Keys, Value, Assoc) :-
 534	empty_assoc(Assoc0),
 535	keys_to_assoc(Keys, Assoc0, Value, Assoc).
 536
 537keys_to_assoc([], Assoc, _, Assoc).
 538keys_to_assoc([H|T], Assoc0, Value, Assoc) :-
 539	put_assoc(H, Assoc0, Value, Assoc1),
 540	keys_to_assoc(T, Assoc1, Value, Assoc).
 541
 542
 543ancestor_tree(Objects, Pred, Nodes0, Nodes, Roots) :-
 544	ancestor_tree(Objects, [], Objects, Pred, Nodes0, Nodes, Roots).
 545
 546%%	ancestor_tree(+Open, +Closed, +Targets, :Pred, +NodesIn,
 547%%		      -NodesOut, -Roots) is det.
 548%
 549%	Explore the ancestor graph one more step. This is the main loop
 550%	looking for a spanning tree.  We are done if
 551%
 552%		* There is only one open node left and no closed ones.
 553%		We found the single common root.
 554%
 555%		* No open nodes are left.  We have a set of closed roots
 556%		which form our starting points.  We still have to figure
 557%		out the minimal set of these, as some of the trees may
 558%		overlap others.
 559%
 560%		* We have an open node covering all targets. This is the
 561%		lowest one as we used breath-first expansion.  This step
 562%		is too expensive.
 563
 564ancestor_tree([One], [], _, _, Nodes, Nodes, [One]) :- !.
 565ancestor_tree([], Closed, _, _, Nodes, Nodes, Closed) :- !.
 566ancestor_tree(Open, _, Objects, _, Nodes, Nodes, [One]) :-
 567	member(One, Open),
 568	tree_covers(One, Nodes, Objects), !.
 569ancestor_tree(Open, Closed, Objects, Pred, Nodes0, Nodes, Roots) :-
 570	expand_ancestor_tree(Open, NewOpen, NewClosed, Closed, Nodes0, Nodes1, Pred),
 571	ancestor_tree(NewOpen, NewClosed, Objects, Pred, Nodes1, Nodes, Roots).
 572
 573
 574%%	expand_ancestor_tree(+Open0, -Open,
 575%%			     +Closed0, -Closed,
 576%%			     +Nodes0, -Nodes,
 577%%			     :Pred)
 578%
 579%	Expand the explored graph with one level. Open are the currently
 580%	open nodes. Closed  are  the  nodes   that  have  no  parent and
 581%	therefore are roots.
 582%
 583%	@param Nodes	is an assoc R->(State*list(Child))
 584
 585expand_ancestor_tree([], [], Closed, Closed, Nodes, Nodes, _).
 586expand_ancestor_tree([H|T], Open, Closed0, Closed, Nodes0, Nodes, Pred) :-
 587	setof(Parent, call(Pred, H, Parent), Parents), !,
 588	add_parents(Parents, H, Open, OpenT, Nodes0, Nodes1),
 589	expand_ancestor_tree(T, OpenT, Closed0, Closed, Nodes1, Nodes, Pred).
 590expand_ancestor_tree([H|T], Open, [H|ClosedT], Closed, Nodes0, Nodes, Pred) :-
 591	expand_ancestor_tree(T, Open, ClosedT, Closed, Nodes0, Nodes, Pred).
 592
 593
 594%%	add_parents(+Parents:list, +Child, -NR, +NRT, +Nodes0, -Nodes)
 595%
 596%	Add links Parent->Child to the tree  Nodes0. The difference list
 597%	NR\NRT contains Parents added new to the tree.
 598
 599add_parents([], _, NP, NP, Nodes, Nodes).
 600add_parents([H|T], Child, NP, NPT, Nodes0, Nodes) :-
 601	in_tree(Child, H, Nodes0), !,
 602	add_parents(T, Child, NP, NPT, Nodes0, Nodes).
 603add_parents([H|T], Child, NP, NPT, Nodes0, Nodes) :-
 604	get_assoc(H,
 605		  Nodes0, State*Children,
 606		  Nodes1, State*[Child|Children]), !,
 607	add_parents(T, Child, NP, NPT, Nodes1, Nodes).
 608add_parents([H|T], Child, [H|NP], NPT, Nodes0, Nodes) :-
 609	put_assoc(H, Nodes0, node*[Child], Nodes1),
 610	add_parents(T, Child, NP, NPT, Nodes1, Nodes).
 611
 612
 613%%	in_tree(?Node, +Root, +Nodes) is nondet.
 614%
 615%	True if Node appears in the tree below Root.
 616
 617in_tree(Node, Node, _).
 618in_tree(Node, Root, Nodes) :-
 619	get_assoc(Root, Nodes, _State*Children),
 620	member(Child, Children),
 621	in_tree(Node, Child, Nodes).
 622
 623
 624%%	prune_forest(+Nodes, +Roots, -MinimalForest) is det.
 625%
 626%	MinimalForest is the minimal forest overlapping all targets.
 627%
 628%	@tbd Currently doesn't remove unnecessary trees.
 629
 630prune_forest(Nodes, Roots, Forest) :-
 631	maplist(prune_root(Nodes), Roots, Roots1),
 632	sort(Roots1, Roots2),
 633	maplist(prune_ancestor_tree(Nodes), Roots2, Forest0),
 634	sort(Forest0, Forest).
 635
 636%%	prune_root(+Nodes, +Root0, -Root) is det.
 637%
 638%	Prune the parts of the search tree   that  ended up nowhere. The
 639%	first real branch is where  we  find   a  solution  or there are
 640%	multiple parents. This avoids  doing   double  work  pruning the
 641%	trees itself.
 642
 643prune_root(Nodes, Root0, Root) :-
 644	get_assoc(Root0, Nodes, node*[One]), !,
 645	prune_root(Nodes, One, Root).
 646prune_root(_, Root, Root).
 647
 648%%	prune_ancestor_tree(Nodes, Root, Tree) is det.
 649%
 650%	Tree is a pruned hierarchy from Root using the branching paths of
 651%	Nodes.
 652
 653prune_ancestor_tree(Nodes, Root, Tree) :-
 654	get_assoc(Root, Nodes, Value),
 655	(   Value = node*[One]
 656	->  prune_ancestor_tree(Nodes, One, Tree)
 657	;   Tree = (Root-Children),
 658	    Value = _*Children0,
 659	    maplist(prune_ancestor_tree(Nodes), Children0, Children)
 660	).
 661
 662%%	tree_covers(+Root, +Nodes, -Targets:list) is det.
 663%
 664%	True if Targets is the sorted  list   of  targets covered by the
 665%	tree for which Root is the root.
 666
 667tree_covers(Root, Nodes, Targets) :-
 668	phrase(tree_covers(Root, Nodes), Targets0),
 669	sort(Targets0, Targets).
 670
 671tree_covers(Root, Nodes) -->
 672	{ get_assoc(Root, Nodes, State*Children) },
 673	(   {State == target}
 674	->  [Root]
 675	;   []
 676	),
 677	tree_covers_list(Children, Nodes).
 678
 679tree_covers_list([], _) -->
 680	[].
 681tree_covers_list([H|T], Nodes) -->
 682	tree_covers(H, Nodes),
 683	tree_covers_list(T, Nodes).
 684
 685
 686		 /*******************************
 687		 *	    PRIMITIVES		*
 688		 *******************************/
 689
 690%%	map_graph(+GraphIn, +Map:assoc, -GraphOut) is det.
 691%
 692%	Map a graph to a new graph  by   mapping  all  fields of the RDF
 693%	statements over Map. Then delete   duplicates from the resulting
 694%	graph as well as rdf(S,P,S) links that did not appear before the
 695%	mapping.
 696%
 697%	@tbd	Should we look inside literals for mapped types?  That
 698%		would be consistent with abstract_graph/3.
 699
 700map_graph(GraphIn, Map, GraphOut) :-
 701	phrase(map_triples(GraphIn, Map), Graph2),
 702	sort(Graph2, GraphOut).
 703
 704map_triples([], _) -->
 705	[].
 706map_triples([H0|T0], Map) -->
 707	map_triple(H0, Map),
 708	map_triples(T0, Map).
 709
 710map_triple(rdf(S0,P0,O0), Map) -->
 711	{ map_resource(S0, Map, S),
 712	  map_resource(P0, Map, P),
 713	  map_object(O0, Map, O)
 714	},
 715	(   { S == O, S0 \== O0 }
 716	->  []
 717	;   [ rdf(S,P,O) ]
 718	).
 719
 720map_resource(N0, Map, N) :-
 721	get_assoc(N0, Map, N), !.
 722map_resource(N, _, N).
 723
 724map_object(O0, Map, O) :-
 725	get_assoc(O0, Map, O), !.
 726map_object(literal(type(T0, V)), Map, L) :-
 727	get_assoc(T0, Map, T), !,
 728	L = literal(type(T, V)).
 729map_object(O, _, O).
 730
 731
 732%%	map_graph(+GraphIn, +Map:assoc, -GraphOut, -AbstractMap) is det.
 733%
 734%	Map a graph to a new graph  by   mapping  all  fields of the RDF
 735%	statements over Map. The nodes in these  graphs are terms of the
 736%	form Abstract-list(concrete).
 737%
 738%	@param AbstractMap assoc Abstract -> ordset(concrete)
 739
 740map_graph(GraphIn, Map, GraphOut, AbstractMap) :-
 741	map_graph(GraphIn, Map, GraphOut),
 742	assoc_to_list(Map, ConcAbstr),	% Concrete->Abstract
 743	graph_nodes(GraphIn, AllConcrete),
 744	pairs_keys_intersection(ConcAbstr, AllConcrete, UsedConcAbstr),
 745	transpose_pairs(UsedConcAbstr, AbstrConc),
 746	group_pairs_by_key(AbstrConc, Grouped),
 747	list_to_assoc(Grouped, AbstractMap).
 748
 749
 750%%	pairs_keys_intersection(+Pairs, +Keys, -PairsInKeys) is det.
 751%
 752%	True if PairsInKeys is a subset  of   Pairs  whose key appear in
 753%	Keys. Pairs must be key-sorted and Keys must be sorted.  E.g.
 754%
 755%	==
 756%	?- pairs_keys_intersection([a-1,b-2,c-3], [a,c], X).
 757%	X = [a-1,c-3]
 758%	==
 759
 760pairs_keys_intersection(Pairs, [K], Int) :- !,	% One key: happens quite often
 761	find_one_key(Pairs, K, Int).
 762pairs_keys_intersection([P1|TP], [K1|TK], Int) :- !,
 763	compare_pair_key(Diff, P1, K1),
 764	pairs_keys_isect(Diff, P1, TP, K1, TK, Int).
 765pairs_keys_intersection(_, _, []).
 766
 767pairs_keys_isect(<, _, [P1|TP], K1, TK, Int) :- !,
 768	compare_pair_key(Diff, P1, K1),
 769	pairs_keys_isect(Diff, P1, TP, K1, TK, Int).
 770pairs_keys_isect(=, P, [P1|TP], K1, TK, [P|Int]) :- !,
 771	compare_pair_key(Diff, P1, K1),
 772	pairs_keys_isect(Diff, P1, TP, K1, TK, Int).
 773pairs_keys_isect(>, P1, TP, _, [K1|TK], Int) :- !,
 774	compare_pair_key(Diff, P1, K1),
 775	pairs_keys_isect(Diff, P1, TP, K1, TK, Int).
 776pairs_keys_isect(=, P, _, _, _, [P]) :- !.
 777pairs_keys_isect(_, _, _, _, _, []).
 778
 779compare_pair_key(Order, K1-_, K2) :- !,
 780	compare(Order, K1, K2).
 781
 782find_one_key([], _, []).
 783find_one_key([K0-V|T0], K, List) :-
 784	(   K0 == K
 785	->  List = [k0-V|T],
 786	    find_one_key(T0, K, T)
 787	;   find_one_key(T0, K, List)
 788	).
 789
 790
 791%%	map_to_bagged_graph(+GraphIn, +Map, -GraphOut, -Bags) is det.
 792%
 793%	GraphOut is a graph between  objects   and  bags, using the most
 794%	specific common ancestor for representing properties.
 795
 796map_to_bagged_graph(GraphIn, Map, GraphOut, Bags) :-
 797	map_graph(GraphIn, Map, AbstractGraph, AbstractMap),
 798%	assertion(map_assoc(is_ordset, AbstractMap)),
 799	empty_assoc(Nodes),
 800	rdf_to_paired_graph(GraphIn, PairGraph),
 801	phrase(bagify_triples(AbstractGraph, PairGraph, AbstractMap,
 802			      Nodes, Bags, []),
 803	       GraphOut).
 804
 805bagify_triples([], _, _, _, Bags, Bags) --> [].
 806bagify_triples([rdf(S0,_P,O0)|T], PairGraph, Map, Nodes, Bags, BagsT) -->
 807	{ bagify_resource(S0, S, Map, Nodes, Nodes1, Bags, BagsT0),
 808	  bagify_object(O0, O, Map, Nodes1, Nodes2, BagsT0, BagsT1),
 809
 810					% normal properties
 811	  used_properties(S0, O0, PairGraph, Map, PList),
 812	  common_ancestor_forest(sub_property_of, PList, Forest),
 813	  debug(used_properties, 'Forest = ~p', [Forest]),
 814	  pairs_keys(Forest, PRoots),
 815					% inverse properties
 816	  used_properties(O0, S0, PairGraph, Map, IPList),
 817	  common_ancestor_forest(sub_property_of, IPList, IForest),
 818	  debug(used_properties, 'IForest = ~p', [IForest]),
 819	  pairs_keys(IForest, IPRoots)
 820	},
 821	mk_p_triples(PRoots, S, O),
 822	mk_p_triples(IPRoots, O, S),
 823	bagify_triples(T, PairGraph, Map, Nodes2, BagsT1, BagsT).
 824
 825
 826bagify_resource(R0, R, _Map, Nodes, Nodes) -->
 827	{ get_assoc(R0, Nodes, R) }, !.
 828bagify_resource(R0, BagID, Map, Nodes0, Nodes) -->
 829	{ get_assoc(R0, Map, Set), Set = [_,_|_], !,
 830	  atom_concat('_:rbag_', R0, BagID),
 831	  put_assoc(R0, Nodes0, BagID, Nodes)
 832	},
 833	make_rdf_graphs([BagID-Set]).
 834bagify_resource(R0, One, Map, Nodes, Nodes) -->
 835	{ get_assoc(R0, Map, [One]) }, !.
 836bagify_resource(R, R, _, Nodes, Nodes) --> [].
 837
 838bagify_object(R0, R, Map, Nodes0, Nodes) -->
 839	bagify_resource(R0, R, Map, Nodes0, Nodes).
 840
 841
 842%%	rdf_to_paired_graph(+GraphIn, -PairedGraph) is det.
 843%
 844%	@param GraphIn		Graph as list(rdf(S,P,O))
 845%	@param PairedGraph	Graph as list(S-list(O-P)), where the
 846%				pair lists are key-sorted,
 847
 848rdf_to_paired_graph(Triples, Pairs) :-
 849	subject_pairs(Triples, Pairs0),
 850	keysort(Pairs0, Pairs1),
 851	group_pairs_by_key(Pairs1, Pairs2),
 852	maplist(keysort_values, Pairs2, Pairs).
 853
 854subject_pairs([], []).
 855subject_pairs([rdf(S,P,O)|T0], [S-(O-P)|T]) :-
 856	subject_pairs(T0, T).
 857
 858keysort_values(K-V0, K-V) :-
 859	keysort(V0, V).
 860
 861
 862%%	used_properties(+S0, +O0, +GraphIn, +AbstractMap, -PredList) is det.
 863%
 864%	Find properties actually used between two   bags.  S0 and O0 are
 865%	the subject and object from the   abstract graph.
 866%
 867%	@param GraphIn	original concrete graph represented as pairs.
 868%			See rdf_to_paired_graph/2.
 869%	@param AbstractMap Assoc Abstract->Concrete, where Concrete is
 870%			an ordset of resources.
 871
 872used_properties(S0, O0, GraphIn, Map, PList) :-
 873	get_assoc(S0, Map, SList),
 874	get_assoc(O0, Map, OList),
 875	pairs_keys_intersection(GraphIn, SList, Intersection),
 876	pairs_values(Intersection, OPList0),
 877	append(OPList0, OPList1),
 878	keysort(OPList1, OPList),
 879	pairs_keys_intersection(OPList, OList, IntPList),
 880	pairs_values(IntPList, PListDupl),
 881	sort(PListDupl, PList),
 882	debug(used_properties, '  --> ~p', [PList]).
 883
 884
 885%%	graph_resources(+Graph, -Resources:list(atom)) is det.
 886%
 887%	Resources is a sorted list  of   unique  resources  appearing in
 888%	Graph. All resources are in Resources,   regardless  of the role
 889%	played in the graph: node, edge (predicate)  or type for a typed
 890%	literal.
 891%
 892%	@see graph_resources/4 distinguishes the role of the resources.
 893
 894graph_resources(Graph, Resources) :-
 895	graph_resources(Graph, R, P, P, T, T, [], _, _),
 896	sort(R, Resources).
 897
 898%%	graph_nodes(+Graph, -Nodes) is det.
 899%
 900%	Nodes is a sorted list of   all resources and literals appearing
 901%	in Graph.
 902%
 903%	@tbd	Better name
 904
 905graph_nodes(Graph, Nodes) :-
 906	graph_resources(Graph, Nodes0, P, P, L, _, _, L, []),
 907	sort(Nodes0, Nodes).
 908
 909
 910%%	graph_resources(+Graph,
 911%%			-Resources:list(atom),
 912%%			-Predicates:list(atom),
 913%%			-Types:list(atom)) is det.
 914%
 915%	Resources is a sorted list  of   unique  resources  appearing in
 916%	Graph as subject or object of a  triple. Predicates is a list of
 917%	all unique predicates in Graph and Types is a list of all unique
 918%	literal types in Graph.
 919
 920graph_resources(Graph, Resources, Preds, Types) :-
 921	graph_resources(Graph, R, [], P, [], T, [], _, _),
 922	sort(R, Resources),
 923	sort(P, Preds),
 924	sort(T, Types).
 925
 926graph_resources([], R, R, P, P, T, T, L, L).
 927graph_resources([rdf(S,P,O)|T], [S|RT0], RT, [P|PTl0], PTl, Tl0, Tl, L0, L) :-
 928	object_resources(O, RT0, RT1, Tl0, Tl1, L0, L1),
 929	graph_resources(T, RT1, RT, PTl0, PTl, Tl1, Tl, L1, L).
 930
 931
 932object_resources(O, R0, R, T0, T, L0, L) :-
 933	(   atom(O)
 934	->  R0 = [O|R], T0 = T, L0 = L
 935	;   O = literal(Val)
 936	->  R0 = R, L0 = [O|L],
 937	    (	Val = type(Type, _)
 938	    ->	T0 = [Type|T]
 939	    ;	T0 = T
 940	    )
 941	;   assertion(fail)
 942	).
 943
 944
 945		 /*******************************
 946		 *	      ABSTRACT		*
 947		 *******************************/
 948
 949%%	abstract_graph(+GraphIn, -GraphOut, +Options) is det.
 950%
 951%	Unify GraphOut with  an  abstracted   version  of  GraphIn.  The
 952%	abstraction is carried out triple-by-triple.   Note  there is no
 953%	need to abstract all triples to the   same  level. We do however
 954%	need to map nodes in the graph consistently. I.e. if we abstract
 955%	the object of rdf(s,p,o), we must abstract the subject of rdf(o,
 956%	p2, o2) to the same resource.
 957%
 958%	If we want to do incremental growing   we  must keep track which
 959%	nodes where mapped to which resources.  Option?
 960%
 961%	We must also decide on the abstraction   level  for a node. This
 962%	can be based on the weight  in   the  search graph, the involved
 963%	properties and focus such  as  location   and  time.  Should  we
 964%	express this focus in the weight?
 965%
 966%	Options:
 967%
 968%	    * map_in(?Map)
 969%	    If present, this is the initial resource abstraction map.
 970%	    * map_out(-Map)
 971%	    Provide access to the final resource abstraction map.
 972%	    * bags(-Bags)
 973%	    If provided, _bagify_ the graph, returning the triples that
 974%	    define the bags in Bags. The full graph is created by
 975%	    appending Bags to GraphOut.
 976%	    * merge_concepts_with_super(+Boolean)
 977%	    If =true= (default), merge nodes of one is a super-concept
 978%	    of another.
 979
 980abstract_graph(GraphIn, GraphOut, Options) :-
 981	map_in(Options, MapIn),
 982	graph_resources(GraphIn, Nodes, NT, Edges, [], _T0, _TT, NT, []),
 983	node_map(Nodes, MapIn, Map2, Options),
 984	edge_map(Edges, Map2, MapOut),
 985	map_out(Options, MapOut),
 986	(   option(bags(Bags), Options)
 987	->  map_to_bagged_graph(GraphIn, MapOut, GraphOut, Bags)
 988	;   map_graph(GraphIn, MapOut, GraphOut)
 989	).
 990
 991map_in(Options, Map) :-
 992	option(map_in(Map), Options, Map),
 993	(var(Map) -> empty_assoc(Map) ; true).
 994
 995map_out(Options, Map) :-
 996	option(map_out(Map), Options, _).
 997
 998%%	node_map(+Nodes, +Map0, -Map, +Options) is det.
 999%
1000%	Create the abstraction map  for  the   nodes  of  the  graph. It
1001%	consists of two steps:
1002%
1003%	    1. Map all instances to their class, except for concepts
1004%	    2. If some instances are mapped to class A and others to
1005%	       class B, where A is a super-class of B, map all instances
1006%	       to class A.
1007
1008node_map(Nodes, Map0, Map, Options) :-
1009	concepts_of(Nodes, Map0, Map1, _NewConcepts),
1010	(   option(merge_concepts_with_super(true), Options, true)
1011	->  assoc_to_values(Map1, Concepts),
1012	    sort(Concepts, Unique),
1013	    identity_map(Unique, SuperMap0),
1014	    find_broaders(Unique, SuperMap0, SuperMap1),
1015	    deref_map(SuperMap1, SuperMap),
1016	    map_assoc(map_over(SuperMap), Map1, Map)
1017	;   Map = Map1
1018	).
1019
1020map_over(Map, V0, V) :-
1021	(   get_assoc(V0, Map, V1)
1022	->  V = V1
1023	;   V = V0
1024	).
1025
1026concepts_of([], Map, Map, []).
1027concepts_of([R|T], Map0, Map, New) :-
1028	get_assoc(R, Map0, _), !,
1029	concepts_of(T, Map0, Map, New).
1030concepts_of([R|T], Map0, Map, [C|New]) :-
1031	concept_of(R, C),
1032	put_assoc(R, Map0, C, Map1),
1033	concepts_of(T, Map1, Map, New).
1034
1035%%	identity_map(+List, -Map) is det.
1036%%	find_broaders(+List, +Map0, -Map) is det.
1037%%	deref_map(+Map0, -Map) is det.
1038
1039identity_map(List, Map) :-
1040	map_list_to_pairs(=, List, Pairs),
1041	list_to_assoc(Pairs, Map).
1042
1043find_broaders([], Map, Map).
1044find_broaders([C|T], Map0, Map) :-
1045	broader(C, Super),
1046	get_assoc(Super, Map0, SuperSuper), !,
1047	debug(rdf_abstract, 'Mapped ~p to super concept ~p', [C, SuperSuper]),
1048	put_assoc(C, Map0, SuperSuper, Map1),
1049	find_broaders(T, Map1, Map).
1050find_broaders([_|T], Map0, Map) :-
1051	find_broaders(T, Map0, Map).
1052
1053
1054deref_map(Map0, Map) :-
1055	findall(KV, mapped_kv(KV, Map0), Pairs),
1056	deref(Pairs, NewPairs),
1057	list_to_assoc(NewPairs, Map).
1058
1059mapped_kv(K-V, Assoc) :-
1060	gen_assoc(K, Assoc, V),
1061	K \== V.
1062
1063%%	deref(+Pairs0, NewPairs) is det.
1064%
1065%	Dereference chains V1-V2, V2-V3  into   V1-V3,  V2-V3. Note that
1066%	Pairs0 may contain cycles, in which case  all the members of the
1067%	cycle  are  replaced  by  the    representative  as  defined  by
1068%	rdf_representative/2.
1069
1070deref(Pairs, NewPairs) :-
1071	list_to_assoc(Pairs, Assoc),
1072	deref(Pairs, Assoc, NewPairs).
1073
1074deref([], _, []).
1075deref([K-V0|T0], Map, [K-V|T]) :-
1076	deref2(V0, Map, [V0], EqSet, V),
1077	(   EqSet == []
1078	->  deref(T0, Map, T)
1079	;   rdf_representative(EqSet, V),
1080	    deref_cycle(T0, EqSet, V, Cycle, T1),
1081	    append(Cycle, T2, T),
1082	    deref(T1, Map, T2)
1083	).
1084
1085deref2(V0, Map, Visited, EqSet, V) :-
1086	get_assoc(V0, Map, V1), !,
1087	(   memberchk(V1, Visited)
1088	->  EqSet = Visited
1089	;   deref2(V1, Map, [V1|Visited], EqSet, V)
1090	).
1091deref2(V, _, _, [], V).
1092
1093deref_cycle([], _, _, [], []).
1094deref_cycle([K-V0|T0], EqSet, V, [K-V|CT], Rest) :-
1095	memberchk(V0, EqSet), !,
1096	deref_cycle(T0, EqSet, V, CT, Rest).
1097deref_cycle([H|T0], EqSet, V, CT, [H|RT]) :-
1098	deref_cycle(T0, EqSet, V, CT, RT).
1099
1100
1101%%	edge_map(+Edges, +MapIn, -MapOut) is det.
1102
1103edge_map([], Map, Map).
1104edge_map([R|T], Map0, Map) :-
1105	get_assoc(R, Map0, _), !,
1106	edge_map(T, Map0, Map).
1107%edge_map([R|T], Map0, Map) :-
1108%	iface_abstract_predicate(R, C),
1109%	put_assoc(R, Map0, C, Map1),
1110%	edge_map(T, Map1, Map).
1111
1112%%	concept_of(+Resource, -Concept) is det.
1113%
1114%	True if Concept is the concept Resource belongs to.  If Resource
1115%	is a concept itself, Concept is Resource.
1116%
1117%	@tbd	Make thesaurus concept classes a subclass of skos:Class.
1118%	@tbd	Put in a reusable place, merge with kwd_search.pl
1119
1120concept_of(O, O) :-
1121	rdfs_individual_of(O, skos:'Concept'), !.
1122concept_of(O, C) :-
1123	rdf_has(O, rdf:type, C), !.
1124concept_of(O, O).
1125
1126%%	broader(+Term, -Broader) is nondet.
1127%
1128%	True if Broader is a broader term according to the SKOS schema.
1129%
1130%	@tbd Deal with owl:sameAs (and skos:exactMatch)
1131
1132broader(Term, Broader) :-
1133	rdf_reachable(Term, skos:broader, Broader),
1134	Broader \== Term.
1135
1136%%	rdf_representative(+Resources:list, -Representative:atom) is det.
1137%
1138%	Representative is the most popular   resource from the non-empty
1139%	list  Resources.  The  preferred   representative  is  currently
1140%	defined as the resource with the   highest  number of associated
1141%	edges.
1142%
1143%	@tbd	Think about the function.  Use sum of logs or sum of sqrt?
1144
1145rdf_representative(List, Representative) :-
1146	(   exclude(rdf_is_bnode, List, NonBNodes),
1147	    NonBNodes \== []
1148	->  representative(NonBNodes, Representative)
1149	;   representative(List, Representative)
1150	).
1151
1152representative([H], Representative) :- !,
1153	Representative = H.
1154representative([H|T], Representative) :-
1155	fan_in_out(H, Fan0),
1156	best(T, Fan0, H, Representative).
1157
1158best([], _, R, R).
1159best([H|T], S0, R0, R) :-
1160	fan_in_out(H, S1),
1161	(   S1 > S0
1162	->  best(T, S1, H, R)
1163	;   best(T, S0, R0, R)
1164	).
1165
1166fan_in_out(R, Fan) :-
1167	count(rdf(R, _, _), 100, FanOut),
1168	count(rdf(_, _, R), 100, FanIn),
1169	Fan is FanOut + FanIn.
1170
1171
1172		 /*******************************
1173		 *	      SIMPLIFY		*
1174		 *******************************/
1175
1176%%	minimise_graph(+GraphIn, -GraphOut) is det.
1177%
1178%	Remove redudant triples from  a   graph.  Redundant  triples are
1179%	defined as:
1180%
1181%		* Super-properties of another property
1182%		* Inverse
1183%		* Symetric
1184%		* Entailed transitive
1185%
1186%	@tbd Implement entailed transitive
1187
1188minimise_graph(RDF0, RDF) :-
1189	partition(object_triple, RDF0, ObjRDF, LitRDF),
1190	map_list_to_pairs(os_rdf, ObjRDF, Pairs),
1191	group_pairs_by_key(Pairs, Grouped),
1192	maplist(key_remove_reduntant_relations, Grouped, MinGroups),
1193	append([LitRDF|MinGroups], RDF).
1194
1195object_triple(rdf(_,_,O)) :-
1196	atom(O).
1197
1198os_rdf(rdf(S,_,O), (A+B)) :-
1199	(   S @< O
1200	->  A = S, B = O
1201	;   A = O, B = S
1202	).
1203
1204key_remove_reduntant_relations(_-Rs0, Rs) :-
1205	remove_reduntant_relations(Rs0, Rs).
1206
1207remove_reduntant_relations([R], [R]) :- !.
1208remove_reduntant_relations(List0, List) :-
1209	select(rdf(S,P1,O), List0, List1),
1210	select(rdf(S,P2,O), List1, List2),
1211	rdfs_subproperty_of(P1, P2), !,
1212	remove_reduntant_relations([rdf(S,P1,O)|List2], List).
1213remove_reduntant_relations(List0, List) :-
1214	select(rdf(S,P,O), List0, List1),
1215	select(rdf(O,P,S), List1, List2),
1216	rdfs_individual_of(P, owl:'SymmetricProperty'), !,
1217	remove_reduntant_relations([rdf(S,P,O)|List2], List).
1218remove_reduntant_relations(List0, List) :-
1219	select(rdf(S,P1,O), List0, List1),
1220	select(rdf(O,P2,S), List1, List2),
1221	rdf_has(P1, owl:inverseOf, P2), !,
1222	remove_reduntant_relations([rdf(S,P2,O)|List2], List).
1223remove_reduntant_relations(List, List).
1224
1225
1226		 /*******************************
1227		 *		UTIL		*
1228		 *******************************/
1229
1230:- meta_predicate
1231	count(:, +, -).
1232
1233count(G, Max, Count) :-
1234        C = c(0),
1235        (   G,
1236            arg(1, C, C0),
1237            C1 is C0+1,
1238            nb_setarg(1, C, C1),
1239            C1 == Max
1240        ->  Count = Max
1241        ;   arg(1, C, Count)
1242        ).