aysylu / loom

Graph library for Clojure. Mailing list https://groups.google.com/forum/#!forum/loom-clj
http://aysy.lu/loom/
886 stars 108 forks source link

maximal-cliques silently breaks on digraphs #128

Open flodiebold opened 4 years ago

flodiebold commented 4 years ago

E.g.

user> (graph-alg/maximal-cliques (graph/digraph ["a" "b"] ["b" "c"]))
(#{"a" "b"} #{"c"})
user> (graph-alg/maximal-cliques (graph/digraph ["c" "b"] ["b" "a"]))
(#{"a"})

(these graphs are isomorphic.)

Of course Bron-Kerbosch only works on undirected graphs, but silently giving wrong results doesn't seem like the right thing to do here :smile: It'd be nice if it could either work on only the edges that go in both directions (which was what I assumed it would do), or loudly fail, or at least say in the documentation that it won't work.

(Or maybe I have some fundamental misunderstanding here?)