September 16, 2018
Just Juxt #33: Graph Connectivity (4clojure #91)
Given a graph, determine whether the graph is connected. A connected graph is such that a path exists between any two given nodes.
- Your function must return true if the graph is connected and false otherwise.
- You will be given a set of tuples representing the edges of a graph. Each member of a tuple being a vertex/node in the graph.
- Each edge is undirected (can be traversed either direction).
(ns live.test
(:require [cljs.test :refer-macros [deftest is testing run-tests]]))
(defn graph [g]
(= 1 (count (reduce
(fn [acc pair]
(let [pred (partial some (set pair))
[conn dis] ((juxt filter remove) pred acc)]
(set (cons (set (apply concat pair conn)) dis))))
#{}
g))))
(deftest graph-test
(is (= true (graph #{[:a :a]})))
(is (= true (graph #{[:a :b]})))
(is (= false (graph #{[1 2] [2 3] [3 1]
[4 5] [5 6] [6 4]})))
(is (= true (graph #{[1 2] [2 3] [3 1]
[4 5] [5 6] [6 4] [3 4]})))
(is (= false (graph #{[:a :b] [:b :c] [:c :d]
[:x :y] [:d :a] [:b :e]})))
(is (= true (graph #{[:a :b] [:b :c] [:c :d]
[:x :y] [:d :a] [:b :e] [:x :a]}))))
(run-tests)