Fork me on GitHub
#off-topic
<
2018-11-25
>
dominicm17:11:53

Is it still a depth first search if the parent is queued for processing after its children?

denisgrebennicov17:11:36

parent should not be queued after processing. You have visited set, for visited nodes. It doesnโ€™t make sense to re-visit the parent node again. Or is it your specific use case?

dominicm18:11:56

I have a single thread that can process nodes. Parents need all of their children resolved before they can be processed.

denisgrebennicov18:11:09

Smth like this?

def dfs(source, visited):
    if source in visited: return

    visited.add(source)

    for child in children[source]:
        dfs(child, visited)
    
    # do your logic here with source

dominicm18:11:35

I think order would be wrong for me, the for would need to come before visited.add

dominicm18:11:34

Maybe I need to do something closer to a toposort.

dominicm18:11:56

I don't really have a compsci background, so I'm spear fishing

denisgrebennicov18:11:50

you can not do toposort in a graph with a cycle

denisgrebennicov18:11:58

> the for would need to come before visited.add how come?

denisgrebennicov18:11:41

the visited.add is there in order to prevent calling a node twice or more.

denisgrebennicov19:11:10

My code does exactly what you said. > Parents need all of their children resolved before they can be processed

denisgrebennicov19:11:14

aka post-traversal

dominicm19:11:00

Oh, I would go over visited in reverse?

dominicm19:11:48

My graph doesn't have a cycle, it's a tree

dominicm19:11:33

Which might not be a clear way of describing it. My data is hierarchical.

dominicm19:11:28

wikipedia knows more than I expected, and is rather useful

denisgrebennicov19:11:30

> Oh, I would go over visited in reverse? sure. But this is what you want โ†’ child before parent. It should be this way

dominicm20:11:10

(defn post-order-tree-seq
  [branch? children root]
  (let [walk (fn walk [n]
               (if (branch? n)
                 (concat (mapcat walk (children n)) [n])
                 [n]))]
    (walk root)))
Came up with this, which I'm fairly certain is bad given that I'm using concat in this way ๐Ÿ™‚ Generally seems to work though!

somedude31422:11:54

Clojure is making me smile like an idiot. I was searching for regex to remove consecutive dashes from slugs. It turned out to be as simple as adding (dedupe i) to my (as->...)!!

eggsyntax22:11:33

I've had that experience so many times, until eventually I got used to always double-checking whether there's a function in core that'll immediately solve my problem ๐Ÿ˜‰