aysylu / loom Goto Github PK

It would be interesting to allow for graph traversal and modification using the zipper idiom that some Clojure developers already employ for working with tree shaped data, e.g.

(clojure.zip/graph-zip g v)

would return a zipper for traversing / updating graph g where vertex v ∈ g is selected as the "root".

Unfortunately, Gephi seems to ignore attribute names in quotes. While I think they should really fix this, it would be nice if either there was an option not to quote, or a if loom intelligently looked to see whether quoting is necessary (presence of spaces or other troublesome characters in attribute name?).

Is this in the cards? I might be able to help if so.

The auto doc generator should be able to support reader conditionals.

Would be cool to be able to filter/remove nodes based on attributes.

I'm currently using core.matrix matrices to represent graphs, and interested in finding out if I would also be able to use these matrices in loom in order to take advantage of the various algorithms. Is there a recommended strategy to incorporate additional graph implementations using matrices?

As far as I can see, it seems like it would be possible to extend the loom protocols to core.matrix matrices without too much difficulty. But I don't want to start hacking on that unless I can confirm that this is a sensible direction. Would you accept a PR that enabled something like this?

I did Day 6 of Advent of Code with the help of loom! Thanks so much!

I did run into an issue when I ran it in clojurescript:

=== Running clojure test aoc.y2018.d07.ClashTheBunny

Running tests in #{"src"}

Testing aoc.y2018.d07.ClashTheBunny
part-2 took 169.12 msecs
part-1 took 39.93 msecs

Ran 2 tests containing 2 assertions.
0 failures, 0 errors.

=== Running cljs test aoc.y2018.d07.ClashTheBunny
WARNING: cljs.core/bit-or, all arguments must be numbers, got [any Long] instead at line 494 cljs-test-runner-out/loom/alg_generic.cljc

Testing aoc.y2018.d07.ClashTheBunny
part-1 took 66.00 msecs

FAIL in (part-2) (cljs_test_runner.gen.js:768:286)
expected: (= (str answer-2) (str (:timer (solve-2 input 5 60))))
  actual: (not (= "891" "732"))
part-2 took 241.00 msecs

Ran 2 tests containing 2 assertions.
1 failures, 0 errors.

It passes fine in CLJ, but in cljs I get the wrong answer. I am using loom very lightly, so I doubt this is an issue with loom, but I saw the warning and figured you may want to know anyhow.

https://circleci.com/gh/borkdude/advent-of-cljc/235

... in the following line of code:
268b21a#diff-6756f782e78604e4ac812dac225d70e3R466

1. into expects a collection but we're giving it a function
2. (partial f) returns f, so partial is useless here

I don't know the logic of this code, but my best guess would be to remove the partial form and keep what's inside.
In any case, this is a bug.

Note: was caught by eastwood

Has anyone tried loom with ClojureScript?

I just looked through the loom source code tonight, enjoyed reading it. A few thoughts:

1. I'm not crazy about how bf-traverse and dijkstra-traverse return very different types of things. The former just returns a seq of nodes, and the latter returns a seq of [node state]. If you pass in an optional function, the function takes different kinds of information for the two types of traversals. Would like to see these be more similar: same interface for both but one uses depth where the other uses distance.
2. A common need is to do a traversal out from some source, returning the final predecessor map and the final depth/distance map. Would like to see this exposed in alg.clj as a convenient function, for example, something like:
   (shortest-path-preds g start) -> [preds-map dist-map] where
   preds-map is a map of the form {node predecessor} and
   dist-map is a map of the form {node depth/distance-from-start}.
3. Your "poor man's priority queue" in alg-generic/dijkstra-traverse is flawed. It is theoretically possible that two different, uncomparable nodes could have equal distance and equal hash. It's an unlikely scenario, but would cause a crash. I suggest using priority-map (similar speed because under the hood it also uses sorted-set, but handles these edge cases correctly) or if you really want maximum speed, a mutable java priority queue.

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

(-> (g/digraph {:a [:b]})
    (ga/add-attr [:a :b] :foo :bar)
    (g/remove-nodes :a)
    (ga/attrs [:a :b]))
=> {:foo :bar}

Is this intentional, or an oversight? I can believe either, though I'd prefer the latter to be the case.

The A* implementation in alg/astar_path applies the heuristic function to the current node and its successors. It should apply the heuristic to the current node and the target node.

The consequence is that this implementation is not optimal, it visits many more nodes than it should, and it really isn't A* at all.

https://github.com/aysylu/loom/blob/master/src/loom/alg.cljc#L638

I created a pull request that adds a test to demonstrate this deficiency: #81

"View source" links at aysy.lu/loom/ link to .clj files, not cljc files.

Since there are no .clj files anymore, GitHub returns 404.

Example doc: bf-path - http://aysy.lu/loom/loom.alg.html#var-bf-path

Example link: bf-path view source - https://github.com/aysylu/loom/blob/master/src/loom/alg.clj#L121

Should be: corrected link - https://github.com/aysylu/loom/blob/master/src/loom/alg.cljc#L121

P.S. Great library! Thanks much. :)

I haven't tracked down exactly where the issue is yet. It appears there is a recursive call somewhere that is not in a tail recursive form. This was the backtrace (with Clojure 1.5.1 and Loom 0.3.1), but it's not very helpful:

Exception in thread "main" java.lang.StackOverflowError
    at clojure.lang.ASeq.more(ASeq.java:130)
    at clojure.lang.RT.more(RT.java:607)
    at clojure.core$rest.invoke(core.clj:73)
    at clojure.core$filter$fn__4226.invoke(core.clj:2532)
    at clojure.lang.LazySeq.sval(LazySeq.java:42)
    at clojure.lang.LazySeq.seq(LazySeq.java:60)
    at clojure.lang.RT.seq(RT.java:484)
    at clojure.core$seq.invoke(core.clj:133)
    at clojure.core$filter$fn__4226.invoke(core.clj:2523)
    at clojure.lang.LazySeq.sval(LazySeq.java:42)
    at clojure.lang.LazySeq.seq(LazySeq.java:60)
    at clojure.lang.RT.seq(RT.java:484)
    at clojure.core$seq.invoke(core.clj:133)
    at clojure.core$filter$fn__4226.invoke(core.clj:2523)
        [elided... this repeats on and on]

f720bf1 laid the groundwork.

Now, the following namespaces need to be ported to Clojurescript:

• alg
• alg-generic
• attr
• dataflow
• flow
• gen
• graph
• io
• label

Also, we'll need to add:

• testing framework to run the tests in Clojure and ClojureScript

----------------------------ORIGINAL POST BELOW-------------------------------------------
Hey

is there a plan on supporting clojurescript?

Recently I heard about the project called cljx which is a simple preprocessor for different host platforms for clojure. I went ahead and created a branch here https://github.com/fluke777/loom/tree/cljx . It does include the layer of cljx. The test seem to be passing as the were if you run

lein do clean, cljx once, test

I did not do any work on clojurescript support per se but I think this is a prerequisite. If this would be interesting for others I could give it a try. I am not a cljx nor clojurescript master but yeah why not.

Found by running Eastwood linter on loom. Effect: No run-time behavior bug, but doing (doc fn-name) will not get any doc string for the function. Some other tools for extracting Clojure documentation rely on that.

Namespace: loom.alg
Functions: degeneracy-ordering bk maximal-cliques

Correct order is (defn fn-name "doc string" [arg vector] body)

Hi all,

Every method I've tried for labelling distinct nodes with the same string makes dot-str return them as merged!

It may be that I've misunderstood terms and have hence implemented wrongly, but here is a simple way to reproduce the issue:

(def g (digraph [2 1] [3 1])) ;; graph looks like this 2 -> 1 <- 3
(def g-labelled (-> g
                    (add-label 2 "label")
                    (add-label 3 "label")))
(dot-str g-labelled)
(view g-labelled)

This produces the very strange DOT text:

digraph "graph" {
"mylabel" -> "1"
"mylabel" -> "1"
"1"
"mylabel" ["label"="mylabel"]
"mylabel" ["label"="mylabel"]
}

Please let me know if I'm doing something wrong; otherwise I'll dip into the source and see if I can fix this.

Cheers

Hello,
it would be nice to have a 1.0.1 so that we could have a fix for #95 :-)

At least with (loom.graph/digraph g1 g2), any attribute data present in g1 and g2 fails to be preserved in the combined graph. This would be a nice feature.

Hi @aysylu, I was taking a stab at writing an alternative implementation of a weighted, undirected graph and have brushed up to a few points where we might consider tightening the API. I'm not sure how to fix them but figured I'd share in case you have suggestions.

A few things I've encountered:

• multiple definitions for functions
• lack of edge types
• test are specific to current implementations

These are sometimes inefficient (loom.graph/graph) or inconsistent based on the particular implementation (EditableGraph/add-edges* defining edges to be [n1 n2] if unweighted or [n1 n2 w] if weighted). The add-edges* and edge definition is a little interesting since it really depends on whether a graph also implements WeightedGraph.

The lack of edge types is not necessarily an appropriate solution for the add-edges* inconsistency, but the default implementations of the undirected graphs could be improved with an UndirectedEdge type with tests for equality based on both incident nodes rather than leaking implementation details and resulting in an undirected graph really being a directed graph with double the edges–an edge for each direction. I've taken such an approach with the basic implementation I wrote.

It'd be handy if Loom offered a test suite for general classes of graphs rather than use hardcoded references to the default implementations. I'm thinking of something similar to the test suite provided by core.matrix. There would be a set a tests for directed graphs, undirected graphs, weighted graphs, etc.

I have time to help with these minor issues, but want to coordinate with you and others using and developing Loom first.

Support for multigraphs was added in PR #19, which allows us to represent graphs that have more than 1 edge between two vertices. However, algorithms in loom.alg still operate on the assumption that a node is uniquely defined by its two vertices.

I managed to whittle this down to a test case that fails to compute the correct components, but haven't gotten to the point where I understand what it broken just yet. Here's the test case:

(defn scc-is-busted []
  (let [g (digraph [1 5] [2 4] [3 1] [3 2] [3 6]
                   [4 10] [5 3] [6 1] [6 10] [7 8]
                   [8 9] [8 11] [9 3] [9 5] [9 7]
                   [10 2] [11 2] [11 4])
        components (set (map set (scc g)))
        expected   #{ #{2 4 10} #{1 3 5 6} #{11} #{7 8 9}}]
    (prn components)
    (if (not= expected components)
      (throw (RuntimeException. "scc did not compute the correct components")))))

There should be 4 strongly connected components, but scc is only returning 2, and they're wrong.

The API docs hosted at http://aysy.lu/loom/ cover version 0.4.2 instead of the current 0.5.0. I think it would be useful to update them, especially if they can be automatically generated from source.
For example, I came to the Loom project while looking for a graph library in Clojure supporting Johnson's all-pairs shortest-path algorithm. From the API docs I got the impression that such algo was not available in Loom, and only after looking (by chance) into the source I discovered it was there.

I've found couple of old issues (like this one #44), but maybe now it's supported? I've found and loom.io/dot-str accept bunch of parameters and actually reads additional attributes attached to the nodes, but still could not figure out how to use.

If it's not supported, what would be the right approach to implement it?

Hi there. Wondering how to set a graph attribute? I have a weighted-digraph that I'd like rankdir = "LR", but I can't seem to figure it out. Thanks!

That release had some API changes that broke cljs-priority-map, which is tracked here:

tailrecursion/cljs-priority-map#10

Once that's settled and included in a release, then a simple dependency bump release here seems warranted.

While working out making loom Clojure[Script]-portable, I came across this:

:in-edges (get-in default-digraph-impl [:all :in-edges])

default-digraph-impl has no value at [:all :in-edges]. I presume this should be (get default-digraph-impl :in-edges).

I'm not going to make this change, though: the tests are passing as-is, so flygraph digraphs are apparently not covered, and I have no use for flygraphs currently, so I'm not in a position to write those tests.

Trivial repro:

(lio/view (lgraph/graph) :fmt :pdf)

... should create a PDF and open it. However, instead:

1. Unhandled java.lang.IllegalArgumentException
   No value supplied for key: [:fmt :pdf]

Inspecting the code:

(defn render-to-bytes
  "Renders the graph g in the image format using GraphViz and returns data
  as a byte array.
  Requires GraphViz's 'dot' (or a specified algorithm) to be installed in
  the shell's path. Possible algorithms include :dot, :neato, :fdp, :sfdp,
  :twopi, and :circo. Possible formats include :png, :ps, :pdf, and :svg."
  [g & {:keys [alg fmt] :or {alg "dot" fmt :png} :as opts}]
  (let [dot (apply dot-str g (apply concat opts))
        {:keys [out]} (sh (name alg) (str "-T" (name fmt)) :in dot :out-enc :bytes)]
    out))

(defn view
  "Converts graph g to a temporary image file using GraphViz and opens it
  in the current desktop environment's default viewer for said files.
  Requires GraphViz's 'dot' (or a specified algorithm) to be installed in
  the shell's path. Possible algorithms include :dot, :neato, :fdp, :sfdp,
  :twopi, and :circo. Possible formats include :png, :ps, :pdf, and :svg."
  [g & {:keys [fmt] :or {fmt :png} :as opts}]
    (open-data (apply render-to-bytes g opts) fmt))

On the last line, (apply ... opts) -- opts should presumably be (apply concat opts). (This is why I don't like positional keyword arguments very much :))

Could easily support anything GraphViz does.

Is it possible to visualize a graph in the browser?

Address common questions that have been asked (and answered) in the past.

The problem happens when an attribute key or value is a collection and has items requiring escaping. Here is small snippet to reproduce it:

(gv/view (-> (gg/graph [1 2]) (ga/add-attr-to-edges :a ["AA."bb""] [[1 2]])))

The problem is in dot-attrs function. str on collection escapes it:
user> (str ["AA."bb""])
"["AA.\"bb\""]"

I guess dot-attrs should be fully reworked somehow

(def g (graph [1 2] [2 3] {3 [4] 5 [6 7]} 7 8 9))
(def ga (add-attr-to-nodes g :foo "bar" [1]))
(def ga2 (add-attr-to-edges ga :bar "baz" [[1 2]]))

(attrs ga2 1)
{:foo "bar"}

(attrs ga2 2)
{}

(attrs ga2 3)
nil

Seems like attrs should return nil in all cases where there are no attributes...

This will pave the way for enabling Clojurescript (#45).

I would like to specify the shape of nodes (square vs round, for instance), the size of the graph, etc. Is this possible? If not, could it be added?

I have hacked in support for weighted nodes into Prim's algorithm, where the weight is accounted for if a node is supposed to be added. This allows to extend a one-tree towards a TSP approximation.

Sometimes weighted nodes can be achieved by graph transformations into weighted edges as for flow algorithms, but this is not always possible (e.g. for Prim where I do not see this possibility). I would like to know if there is interest in weighted node support? I can add it properly and open a PR, but I thought somebody might have further insight into this...

They are the same in functionality, but attributes are a more general way to represent labels in graphs.

there are several functions in protocols in loom.graph defined like:

(successors [g] [g node]
    "Return direct successors of node, or (partial successors g)")

given that all implementations must include the partial support, it doesn't belong behind the dispatch of a protocol, it is a constant, so a better implementation would be:

;; ... some protocol def
(-successors [g node]
    "Return direct successors of node")
;;

(defn successors
  ([g]
    (partial successors g))
  ([g node]
    (-successors g node)))

Particularly, show how to add and retrieve attributes on nodes and edges.

This is due to https://github.com/aysylu/loom/blob/master/src/loom/gen.clj#L15 where Random.nextInt is called with 0 if the default min-weight and max-weight are used.

I can see a few ways to avoid this exception:

1. A pre-condition asserting (if (weighted? g) (< min-weight max-weight))
2. Setting the default weights to some other sensible values (1 and 100?)
3. Changing rand-w to
   #(if (< min-weight max-weight) (+ (.nextInt rnd (- max-weight min-weight)) min-weight) min-weight)

Of the three I think I like some variation of the third best. I'm happy to put together a pull request if you think this is a good change.

... at this line:
14f4fc3#diff-7a732072b067c6279f50cab433eb4c05R126

This probably needs some fixing.

Note: was caught by eastwood

Can loom build a new graph from a .dot file? How should I save/load my graphs?

Put this together after wanting to build a grid (multi-dimensional array) and find shortest path between nodes using loom. Wasn't sure grids could be converted within loom's graph function, I couldn't get it to work directly.

https://gist.github.com/viperscape/d7a4298477be74feee2c

I am planning to update the tests so that graph creation functions may be provided to create graphs which adhere to Loom graph protocols. This facilitates testing third-party (not included in Loom) graph implementations.

The core.matrix library does something similar, but also includes a mechanism to specify a global implementation. I do not believe Loom benefits from this global setting, but tests should still be organized to provide easy coverage for all Loom graph implementations.

I will do a quick review of how other projects have tackled this problem and then either use test functions which take extra parameters (the graph creation functions) or dynamic binding in order to expose graph creation fns to tests.

If someone is opposed or has additional recommendations, please comment!

I'm working on a clj/cljs port of NetworkX's network simplex implementation, which can be cleaned up and added as a PR if wanted as part of loom?

Hey guys,

When I try to AOT a namespace that includes loom, I get the following error:

Caused by: java.lang.IllegalArgumentException: No implementation of method: :add-nodes* of protocol: #'loom.graph/EditableGraph found for class: loom.graph.BasicEditableDigraph
    at clojure.

Any idea what's going on? Have you guys seen this before?

Thanks!

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.