## Problem description

Vertices $$\V\$$ of directed graph $$\G=(V,E)\$$ represent gossipping ladies; edge $$\(u,v) \in E\$$ signifies that lady $$\u\$$ knows of lady $$\v\$$ (which does not imply that lady $$\v\$$ knows of lady $$\u\$$). Assume that each lady knows of herself.

Intuitively, lady $$\a\$$ gossips about every lady $$\b\$$ she knows about, except herself, to every other lady $$\c\$$ whom $$\a\$$ knows about (other than $$\b\$$ herself). Lady $$\c\$$, upon hearing gossip from lady $$\a\$$ about lady $$\b\$$, will learn about $$\b\$$ but not about $$\a\$$. For $$\c\$$, this then means two things:

• $$\c\$$ will from now on gossip about $$\b\$$ to all other ladies she knows about, and
• $$\c\$$ will from now on gossip to $$\b\$$ about all other ladies she knows about, except about her own self.

Formally, the Gossip Operation $$\g(G)\$$ produces a graph $$\G' = (V, E')\$$, where $$E' = E \ \cup\ \{(c,b) \ \vert\ \exists\ (a,b) \in E : a \neq b \ \land\ \exists\ (a,c) \in E: c \neq b \}$$ The Gossip Closure of a graph $$\G\$$ is the fixed point of the Gossip Operation starting from $$\G\$$.

## Example

Input:

a:{a,b,c,d}
b:{b,e}
c:{c,d}
d:{d}
e:{e}
f:{f,a}
g:{g}


Output:

a:{a,b,c,d}
b:{b,e,c,d}
c:{c,d,b,e}
d:{d,b,c,e}
e:{e,b,c,d}
f:{f,a}
g:{g}


### Larger example

Original graph

After one iteration

Closure

Loops not shown in graphs.

Implement an algorithm of lowest possible time complexity, which given an directed unweighted graph* $$\G\$$ in any suitable format (viz. any format supporting directed unweighted graphs), outputs its Gossip Closure.

* You may impose certain limits on the input, eg. an upper bound on graph density if your solution is better suited for sparse graphs.

• Thanks for the challenge! Could you give an example of a graph and its Gossip Closure, to clarify the definition? Also, are self- loops allowed? Can b=c? Feb 12 '20 at 20:17
• I clarified the definition a bit: each vertex implicitly has a loop. I will add an example later. Feb 12 '20 at 20:32
• Regarding "lowest possible time complexity", graph algorithm time complexities are often stated in terms of the number of edges and number of vertices. Algorithms may do differently on sparse graphs or dense graphs, or depending on the input representation (edge lists, adjacency matrix, etc). Could you clarify this?
– xnor
Feb 13 '20 at 6:49
• I think the math notation in the problem statement is too much and makes it intimidating, despite the good explanation in terms of gossip. Would it not work to say that the gossip closure of a graph G is the smallest graph G' that contains all the edges of G, and that whenever (a,b) and (a,c) are edges of G', so is (b,c)? Though now having written that, it seems like all edges between pairs of a,b,c end up in the closure this way.
– xnor
Feb 13 '20 at 7:02
• @DonThousand Firstly, "just taking combinations of nodes that are pointed to by one node, and adding bidirectional edges between these" will accomplish one step of the operation; I am interested in the closure. Secondly, the challenge I am posing here is not to "plug and chug" into some combinatorial library and arrive at a short but inefficient solution. The challenge is to come up with an efficient algorithm; the key words being "come up with" and "efficient". If that is uninteresting for you then leave it. Feb 14 '20 at 18:51

# Prolog

:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(pio)).

:- op(950, fx, *). *_.

space --> " ", space.
space --> "".

seq([]) --> [].
seq([S|Ss]) --> [S], seq(Ss).

lines([L|Ls]) --> seq(L), "\n", lines(Ls),
{ \+ member('\n', L) }.
lines([]) --> [].

graph(S1-S2) --> space, seq(S1), space, ":", space, vertices(S2), space.

vertices([]) --> [].
vertices([V|Vs]) --> seq(V), space, ",", space, vertices(Vs).
vertices([V]) --> seq(V).

% Solve.

merge_vertices(Vs, Ws, Xs) :-
append(Vs, Ws, Xs0),
sort(Xs0, Xs).

merge_edges(As, Bs) :-
merge_edges_(As, [], Bs1),
keysort(Bs1, Bs).

merge_edges_([], Cs, Cs).
merge_edges_([A|As0], Bs0, Cs) :-
U-Vs = A,
(   select(U-Ws, As0, As1)
->  merge_vertices(Vs, Ws, Xs),
append([U-Xs], As1, As),
Bs = Bs0
;   append([A], Bs0, Bs),
As = As0
),
merge_edges_(As, Bs, Cs).

create_edges([], []).
create_edges([_], []).
create_edges(Vs0, Es) :-
Vs0 = [_,_|_],
findall(V-Vs, select(V, Vs0, Vs), Es).

gossip(G0, G) :-
gossip_(G0, [], G).

gossip_([], G, G).
gossip_([E|Es], G0, G) :-
U-Vs1 = E,
(   select(U, Vs1, Vs)
->  true
;   Vs = Vs1
),
create_edges(Vs, G1),
append([E|G0], G1, G2),
merge_edges(G2, G3),
gossip_(Es, G3, G).

limit_gossip(G, G) :-
gossip(G, G).
limit_gossip(G0, G) :-
gossip(G0, G1),
limit_gossip(G1, G).

build_graph(G, L) :- phrase(graph(G), L).

writeln(X) :-
writeq(X), nl.

output(G) :-
maplist(writeln, G).

test :-
once((
phrase_from_file(lines(Ls), 'g.txt'),
maplist(build_graph, G1, Ls)
)),
limit_gossip(G1, G),
output(G),
halt.

:- initialization(test).

$cat g.txt a:a,b,c,d b:b,e c:c,d d:d e:e f:f,a g:g  # [Complexity]: $$\O(V^2\ln V)\$$ Where $$\V\$$ is the number of vertices. • Note, library(dcgs) is not necessary (or even available) in SWI-Prolog. May 15 '20 at 16:10 • Could limit_gossip be defined like this while preserving the original functionality and complexity? I think it could but I'm not sure, since I'm not exactly well-versed in Prolog. May 15 '20 at 17:00 • Also, for $ cat g.txt you probably meant to include the original graph as given in the task description, not the closure. May 15 '20 at 17:09
• Thanks, for limit_gossip and cat g.txt. The library(dcgs) is for reading the data from a file, it's a bit different from SWI-Prolog but I'm using Scryer-Prolog. May 15 '20 at 19:17