Finding the longest path in an equally-weighted tree

Question

Its purpose is to find the longest path in an equally-weighted tree denoted as such:

3
1 2
2 3

The first number denotes both the number of vertices and the number of edges (3 - 1).

(defn farthest [edg current-node entry-node len]
    (let [ 
        farthest-key (atom current-node)
        farthest-val (atom len)
        ]
        (do
            (dorun 
                (map 
                    (fn [n]
                        ; check if theres a way to this node and that we're not going back
                        (if (not= n entry-node)
                            (let [new (farthest edg n current-node (+ len 1))
                                  new-val (second new)
                                  new-key (first new)]
                                (if (> new-val @farthest-val)
                                    (do
                                        (reset! farthest-val new-val)
                                        (reset! farthest-key new-key)
                                    )
                                )
                            )
                        )
                    )
                    (aget edg current-node)
                )
            )

            [@farthest-key @farthest-val]
        )
    )
)

(defn main []
    (let [edge-count (read)
          edges (atom
                    (to-array
                        (repeat edge-count [])
                    )
                )]

        (dotimes [n (- edge-count 1)]
            (let [edge-a (- (read) 1)
                  edge-b (- (read) 1)]
                (aset @edges edge-a
                    (conj (aget @edges edge-a) edge-b)
                )
                (aset @edges edge-b
                    (conj (aget @edges edge-b) edge-a)
                )
            )
        )        

        (let [
            ft (farthest @edges 0 0 0)
            ftv (first ft)
            sol (farthest @edges ftv ftv 0)
            ]
            (println (second sol))
        )
    )
)

(main)

I've taken multiple attempts to optimize it, but I'm still struggling to make it run under the allowed time (1 second for a tree of up to 10000 vertices/connections). The most notable improvement was a change of the data structure from a connection matrix to a bunch of neighbourhood lists.

It is a university assignment, but I'm perfectly fine with disclosing that I got help here. I feel that I've already given it everything that I can and it simply requires more intricate knowledge about Clojure and its performance in particular, rather than a purely algorithmic change. (I know for a fact that one my colleagues managed to fit in the allocated time using the same algorithm on the same grading system).

Answer 1

(defn farthest [edg current-node entry-node len]
    (let [ 
        farthest-key (atom current-node)
        farthest-val (atom len)
        ]
        (do
            (dorun 
                (map
                    (fn [n]
                        ...
                    )
                    (aget edg current-node)
                )
            )

            [@farthest-key @farthest-val]
        )
    )
)

1. Put )s and ] on the same line as the expression they close.
2. Put the first let-binding and [ on the same line.
3. You can use doseq instead of (dorun (map ...))
4. You can drop the do, since let has an implicit do around its body

E.g.,

(defn farthest [edg current-node entry-node len]
  (let [farthest-key (atom current-node)
        farthest-val (atom len)]
    (doseq [n (aget edg current-node)]
      ...)
    [@farthest-key @farthest-val]))

But also, think functional:

1. You don't need atoms (e.g., use reduce to find the maximum path, rather than an imperative loop).
2. Don't use arrays. Use Clojure's persistent data structures instead. For example, represent the tree as a map from node ids to a set connected nodes.

Answer 2

I assume we are dealing with undirected graphs: where connecting x to y implies connecting y to x.

The idea of your algorithm is that the longest path from the current-node is the current-node tacked onto the front of the longest path from anywhere I can reach from here, except the entry-node I got here from.

The trouble is, as @NathanDavis points out, that you have written it using atoms. These are expensive in time: they are designed to resolve attempts to access their contents simultaneously into an orderly sequence. You should be using Clojure's immutable locals and native data structures.

Your function returns the final vertex and the path length. Better and simpler to return the whole path.

An idiomatic way to organise your farthest function is ...

• Start at the current-node.
• Use edg to find the nodes we can get to.
• Use remove to eliminate the entry-node.
• Use (map (fn [n] (farthest ...)) ...) to call the function recursively on the remaining nodes.
• Use (max-by count ...) to select the longest tail (max-by is given below).
• Use (cons current-node ...) to complete the path.

We can write it as follows:

(defn longest-path [gm start]
  ((fn lp [current-node entry-node]
    (->> current-node
         gm
         (remove (partial = entry-node))
         (map #(lp % current-node))
         (max-by count)
         (cons current-node)))
   start nil))

... assuming nil is not a node.

For example,

(longest-path [nil [2 3] [1 4] [1] [2]] 1)
;(1 2 4)

Where ...

(defn max-by [f coll]
  (when (seq coll)
    (reduce (fn [x y] (if (>= (f x) (f y)) x y)) coll)))

For example,

(max-by - [1 3 4]) ;1

---

If this is still too slow, organise the function to return an empty list () when it runs out of road. Lists are counted, which makes (count ...) more or less instant, whereas it has to chase down the lazy sequence that map returns to find out how long it is.

Finally, your approach uses explicit recursion. This is a little hazardous in Clojure, since it runs out of stack typically about ten thousand invocations in. If this is a problem you are inclined to solve, look at an approach based on breadth-first-search.