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 \}$$

Gossip Operation
(Added edges in red.)

The Gossip Closure of a graph \$G\$ is the fixed point of the Gossip Operation starting from \$G\$.






Larger example

Original graph

After one iteration


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.

  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – isaacg
    Feb 12 '20 at 20:17
  • \$\begingroup\$ I clarified the definition a bit: each vertex implicitly has a loop. I will add an example later. \$\endgroup\$
    – kyrill
    Feb 12 '20 at 20:32
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – xnor
    Feb 13 '20 at 6:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Feb 13 '20 at 7:02
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – kyrill
    Feb 14 '20 at 18:51


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

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

% Read the data.
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 :-
        phrase_from_file(lines(Ls), 'g.txt'),
        maplist(build_graph, G1, Ls)
    limit_gossip(G1, G),

:- initialization(test).
$ cat g.txt

[Complexity]: \$O(V^2\ln V)\$

Where \$V\$ is the number of vertices.

  • \$\begingroup\$ Note, library(dcgs) is not necessary (or even available) in SWI-Prolog. \$\endgroup\$
    – kyrill
    May 15 '20 at 16:10
  • \$\begingroup\$ 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. \$\endgroup\$
    – kyrill
    May 15 '20 at 17:00
  • \$\begingroup\$ Also, for $ cat g.txt you probably meant to include the original graph as given in the task description, not the closure. \$\endgroup\$
    – kyrill
    May 15 '20 at 17:09
  • \$\begingroup\$ 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. \$\endgroup\$ May 15 '20 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.