Allow arbitrary additional keys in a graph?

[yuhan0]

An Ubergraph exposes the hash map interface, however the implementation of clojure.core map functions only allows for a closed set of keys and turns everything else into a no-op: https://github.com/Engelberg/ubergraph/blob/45553acb8d6ff6c0f1dbde4b27eec874b9b3a7bc/src/ubergraph/core.clj#L228

This seems to go against the Clojure design philosophy of having open data structures – I should be able to assoc extra information to the graph and have it be "ignored" by any function that doesn't request for it.

(-> (uber/digraph)
  (uber/add-edges [1 2])
  (assoc
    :extra/info "foo"
    :date-created "2019-10-02")
  (keys))
;; => (:node-map :allow-parallel? :undirected? :attrs :cached-hash)

What's the rationale for this behavior? Loom graphs for instance allow for it by default since they are plain records. Is there some other API for adding attributes to the graph as a whole?

[Engelberg]

Ubergraphs have their own equality semantics, which in turn requires custom hashing. This makes it necessary to implement ubergraph with deftype, not defrecord. Therefore, it is best to think of it as a closed datatype, and only supporting the behavior explicitly coded.

I hadn't considered attributes on graph itself. You are maybe the second person who has asked for it. It's possible to add, but that functionality does not currently exist. Adding support for metadata would be slightly easier, but also does not currently exist.

As a workaround, you could try adding a metadata map either to the nodes map or the attrs map inside the data structure, and store your graph attributes there. This won't affect equality but if the attributes are metadata about the graph like your example, maybe that's what you want anyway.

On Tue, Oct 1, 2019, 7:21 PM yuhan0 [email protected] wrote:

An Ubergraph exposes the hash map interface, however the implementation of clojure.core map functions only allows for a closed set of keys and turns everything else into a no-op:

https://github.com/Engelberg/ubergraph/blob/45553acb8d6ff6c0f1dbde4b27eec874b9b3a7bc/src/ubergraph/core.clj#L228

This seems to go against the Clojure design philosophy of having open data structures – I should be able to assoc extra information to the graph and have it be "ignored" by any function that doesn't request for it.

(-> (uber/digraph)

(uber/add-edges [1 2])

(assoc

:extra/info "foo"

:date-created "2019-10-02")

(keys))

;; => (:node-map :allow-parallel? :undirected? :attrs :cached-hash)

What's the rationale for this behavior? Loom graphs for instance allow for it by default since they are plain records. Is there some other API for adding attributes to the graph as a whole?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Engelberg/ubergraph/issues/53?email_source=notifications&email_token=AABB2SZSWPDLDKNGBOGSXL3QMQAT5A5CNFSM4I4Q55Z2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HPAJTSA, or mute the thread https://github.com/notifications/unsubscribe-auth/AABB2S6RZNC26TKTJ5GZQXLQMQAT5ANCNFSM4I4Q55ZQ .

[yuhan0]

Thanks for the reply! I got what I needed by directly adding a namespaced key to the attrs map of the ubergraph - not sure what the practical difference is versus using metadata, and equality semantics stays the same.

(defn add-graph-attr
  [g k v]
  (assoc-in g [:attrs ::uber/graph-attrs k] v))

(defn graph-attr
  [g attr]
  (get-in g [:attrs ::uber/graph-attrs attr]))

(let [g (uber/graph)
      h (add-graph-attr g :date-created "2019-10-02")]

  (:attrs h)
  ;; => #:ubergraph.core{:graph-attrs {:date-created "2019-10-02"}}

  (graph-attr h :date-created)
  ;; => "2019-10-02"

  (= g h)
  ;; => true
  )

My use case is doing graph rewriting and transformation, where I have to add certain flags to the entire graph to store additional information like "deleted nodes"

Would something like this be useful in Ubergraph core? I could open a PR.

[Engelberg]

I think you've correctly identified that Ubergraph would benefit from graph attributes, and I'm glad you were able to find a reasonable workaround for your specific use case.

I would like to incorporate support for graph attributes, but am interested in making sure it is done with care. In my mind, here's the kind of solution I'm looking for:

There are two types of graph attributes: those that affect graph equality and those that don't. The graph attributes that don't affect equality would be stored in the metadata and set and accessed using Clojure's standard metadata facilities. Coding this would require adding a metadata map to the deftype and implementing the corresponding interfaces (which currently are stubbed out to do nothing).

Then, I'd want full implementation of graph attributes which do affect hashing and equality. I would be inclined to store this info in the existing attrs part of the data structure under a custom key like :ubergraph/graph-attrs, or another viable option would be to have a separate map in the data structure just devoted to graph attributes. In either case, the hashing and equality would need to know to look there.

Then, a protocol would need to be defined and implemented to access, add, and remove graph attributes.

If you are motivated to do all that, I'd be enthused for the contribution. Now that we've discussed it, this is something I will likely add in the future, but realistically I only am able to devote significant development time to ubergraph once a year or so, and I just did a fairly big series of improvements, so it will be a while before I can get back to it and make those changes.

[dcj]

Just chiming in here: I agree that "Ubergraph would benefit from graph attributes". I am currently working on a project that builds graphs from aircraft flight procedure datasets, the graph itself represents the procedure, and there is a need to place attributes on the procedure/graph, in addition to the nodes and edges. Currently I am using Loom, and putting the graph attibutes into the metadata. I'm planning to experiment with Ubergraph instead of Loom as this work progresses. If I ever get that far, I will take a look at the proposed design above...