Implement Edge fully

[dpsutton]

I love the idea of the Edge protocol in graph.clj. However, it seems like you don't honor it when your add-edges* functions destructure edges as [n1 n2]. I wish it would be along the lines of

(add-edges g edge
    (let [n1 (src edge)
           n2 (dest edge)]
.....

since you defined and extended the Edge protocol to PersistenVectors.

[Engelberg]

This kind of thing is precisely why I've advocated for several years that people who write loom algorithms should ideally test their algorithms against the ubergraph implementation of loom protocols. Too many loom algorithms inadvertently rely on implementation details of loom's concrete data structure, defeating the purpose of using protocols. A quick check against an alternative implementation is a great way to double-check that you've adhered to the protocols.

That said, this kind of destructuring of edges as vectors is so common place in loom that when developing ubergraph, I made sure that ubergraph's concrete edge implementations would destructure properly as vectors. So as long as you use vectors as your edges, or Ubergraph's edges as your edges, the vector destructuring will work fine. However, it looks like loom also allows you to use plain maps with a :src and :dest as your edges, (note how the Edge protocol is extended to cover maps), which would likely cause problems with vector destructuring.

[dpsutton]

I'm not sure I follow how the maps with :src and :dest could cause problems with vector destructuring. Could you explain that a bit more?

My coworker was making an employee graph to just play around at work and is learning Clojure. I saw that protocol in loom and thought that would be a great way to show him how concise some Clojure could could be.

(def employee_records
  (j/query db-conn query :row-fn (fn [row] (Employee. (:first_name row) (:last_name row) (:manager_id row)
                                                      (:id row)))))

(extend-protocol g/Edge
  Employee
  (src [this] this)
  (dest [this] (first (filter #(= (:manager this) (:emp_number %)) employee_records))))

(def graph-85 (g/add-edges (g/digraph) employee_records))

I made sure that ubergraph's concrete edge implementations would destructure properly as vectors.

It seems like destructuring from the vector is convenient in defining the algorithms but it only saves two lines of code. But you can easily use them from the consumer side since the vector (the consumer users) will destructure since that protocol was extended. By "would destructure properly as vectors" do you mean that you made your edges implement the methods required for nth?

[Engelberg]

On Jul 11, 2017 12:19 PM, "dpsutton" notifications@github.com wrote:

I'm not sure I follow how the maps with :src and :dest could cause problems with vector destructuring. Could you explain that a bit more?

(let [[x y] {:src 1, :dest 2}] ...) isn't going to work even though maps are extended to the edge protocol so such maps work with src and dest functions.

It seems like destructuring from the vector is convenient in defining the algorithms but it only saves two lines of code. But you can easily use them from the consumer side since the vector will destructure since that protocol was extended. By "would destructure properly as vectors" do you mean that you made your edges implement the methods required for nth?

—

Precisely.

[Folcon]

I might be hitting this as well, the fact that the edge protocols exist means that I was just expecting this to work:

(let [graph {:edges [{ :target "mammal" :source "dog" :strength 0.7}
                     { :target "mammal" :source "cat" :strength 0.7}
                     { :target "mammal" :source "fox" :strength 0.7}
                     { :target "mammal" :source "elk" :strength 0.7}
                     { :target "insect" :source "ant" :strength 0.7}
                     { :target "insect" :source "bee" :strength 0.7}
                     { :target "fish" :source "carp" :strength 0.7}
                     { :target "fish" :source "pike" :strength 0.7}
                     { :target "cat" :source "elk" :strength 0.1}
                     { :target "carp" :source "ant" :strength 0.1}
                     { :target "elk" :source "bee" :strength 0.1}
                     { :target "dog" :source "cat" :strength 0.1}
                     { :target "fox" :source "ant" :strength 0.1}
                     { :target "pike" :source "cat" :strength 0.1}]
             :nodes [{ :id "mammal" :group 0 :label "Mammals" :level 1}
                     { :id "dog" :group 0 :label "Dogs" :level 2}
                     { :id "cat" :group 0 :label "Cats" :level 2}
                     { :id "fox" :group 0 :label "Foxes" :level 2}
                     { :id "elk" :group 0 :label "Elk" :level 2}
                     { :id "insect" :group 1 :label "Insects" :level 1}
                     { :id "ant" :group 1 :label "Ants" :level 2}
                     { :id "bee" :group 1 :label "Bees" :level 2}
                     { :id "fish" :group 2 :label "Fish" :level 1}
                     { :id "carp" :group 2 :label "Carp" :level 2}
                     { :id "pike" :group 2 :label "Pikes" :level 2}]}
      transform-edges (fn [edges] (map #(clojure.set/rename-keys % {:source :src :target :dest}) edges))]
  (-> (loom/digraph)
      (loom/add-nodes* (:nodes graph))
      (loom/add-edges* (transform-edges (:edges graph)))))

This does give the nth not supported on this type cljs.core/PersistentArrayMap, as it's clear EditableGraph's implementation assumes vectors though I can see the protocol definitions above:

:add-edges*
   (fn [g edges]
     (reduce
      (fn [g [n1 n2]]
        (-> g
            (update-in [:nodeset] conj n1 n2)
            (update-in [:adj n1] (fnil conj #{}) n2)
            (update-in [:in n2] (fnil conj #{}) n1)))
      g edges))

Is this for performance?

PS: Part of the reason for doing this is seeing how hard it would be to pull in a d3 wrapper so that cljs can also visualise graphs :)...

[Folcon]

Ok, that wasn't the case for me it seems, I just didn't clearly understand how to use loom's graphs. The code below should work for the graph I defined in my prior comment, without the edge transformation.

(require '[loom.graph :as loom])
(require '[loom.attr :as attr])

(defn make-graph [graph-type {:keys [nodes edges] :as graph}]
  (let [node-map (into {} (map (fn [node] [(:id node) node])) nodes)
        edge-map (into {} (map (fn [edge] [[(:source edge) (:target edge)] edge])) edges)
        add-attrs-to-node-or-edge (fn [g node-or-edge-map]
                                    (reduce
                                      (fn [g [n-or-e-id n-or-e-map]]
                                        (reduce (fn [inner-g [k v]]
                                                  (attr/add-attr inner-g n-or-e-id k v))
                                                g n-or-e-map))
                                      g node-or-edge-map))]
    (-> (apply graph-type (keys edge-map))
      (add-attrs-to-node-or-edge node-map)
      (add-attrs-to-node-or-edge edge-map))))

(def make-weighted-digraph #(make-graph loom/weighted-digraph %))

It might be helpful to add an illustrative example to the docs? I've only just wrote this, so there may be improvements I can do here, but I thought it best to add the info, hopefully it helps someone in the future.