September 16, 2018

Just Juxt #33: Graph Connectivity (4clojure #91)

Graph connectivity

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)
Tags: coding exercises KLIPSE 4clojure Cryogen juxt