@dr2chase

I find "dominates" clearer. I might be rusty on graph theory, but the fact that is a DAG (and not an oriented graph) should conflate the concepts of domination and reachability, as far as I can tell. In the context of this poset, I would say that "n1 dominates n2" means "I can prove n1 < n2", which is the property we are focusing on.

Maybe I didn't fully understand your comment though....

It sounds like you've got my comment right. I totally agree with what you're saying, and admit that my understanding of dominance/reachability is based mostly on wikipedia and Go compiler code.

The difference has become meaningful, for me, when I'm considering the poset and the SSA/CFG in the same sitting. Handling the SSA, dominance, in the strict graph theory sense, is important and requires attention. Then I switch to thinking about the current state of the poset, and I need to switch to a different meaning of the term.

So, I suppose the benefit of the change would be in reducing the cognitive overhead of handling both the SSA and poset at once. The difference is subtle, and the precision in naming would help me, and possibly others. That being said, if both cases are actually expressing dominance (which I'm not sufficiently qualified to judge), then there isn't really more precise terminology available, and I'll have to manage.

I should mention... I'm in awe of the code/logic in poset.go, it's been great to read, use, and think about. Thanks for that!

@rasky As I understand the definition, "X dominates Y" means every path from the root to Y goes through X. So in the DAG in the original comment (assuming n1 is the root), A does not dominate n2 - the path n1 -> B -> n2 does not pass through A. Likewise, B does not dominate n2. But n1 dominates n2 (even if we assume that the root is "further up", as long as it reaches n1 and does not introduce new paths into the diamond). IMO, the definition is fairly clear and pretty clearly not the same as reachability.

I don't quite understand what you mean by a DAG and not an "oriented" graph. Do you mean that it's a DAG and not a general directed graph (i.e. that it's the acyclic nature that means the two are identical)? Because that still doesn't quite work. Confusingly, the "acyclic" in DAG means "there are no directed cycles", which still allows undirected cycles (the diamond is cyclic as an undirected graph, but if the arrows flow from top to bottom, you can't "follow" that cycle).

The two are conflated in (directed) trees and forests though. In an undirected tree, there is exactly one path from any node to any other node. Hence, in a directed tree, if there is one path Root -> … -> A -> … -> B, then every path from the Root to B must pass through A (there is at most one such path, after all). The difference between a DAG and a directed forest is exactly that the DAG allows diamonds as in the original comment.

I'm fairly confident that the two concepts are different and that what you care about in poset.go is reachability, not dominance. If it helps, one of the Wikipedia examples of a partially ordered set is "The vertex set of a directed acyclic graph ordered by reachability" so it stands to reason that if the DAG is supposed to model a partial order, reachability is what you're interested in :)

Also, FWIW, I met @zdjones at GopherCon UK via a discussion about the poset.go stuff and when I read the implementation I got pretty confused :) I am not super familiar with graph theory myself, so I had to consult the definition myself. And couldn't, for the live of me, figure out why dominance is important (and thought that there must be a super clever trick behind this data structure that I'm not seeing). When I figured out that the dominates method actually checks reachability (doing a DFS and aborting once you find the node is a pretty standard way to check for reachability), things clicked and I stopped looking for hidden magic :)

Thanks, I now agree it makes sense to rename it. Feel free to send a CL and assign it to me.

@Merovius, your comment has helped me think about this better. I see now that my original example wasn't great for this discussion. Should have been more like:

root 
|   \
n1   \  
|     B  
A    /
|   /
 n2 

Now, finding that path A exists isn't sufficient to say that n1 dominates n2.

I also see now that if you pretend n1 is a root of an independent DAG, then reachability = dominance for that new DAG (the root dominates all nodes in the DAG). I think the code in poset.go is actually doing that; dominates is calling the depth first search on a DAG rooted at n1, even if n1 isnt the root of one of the DAGS in the forest.

In other words, its a matter of context. In the context of the poset as a whole, dominates is not the right word for n1 -> n2. In the context of a DAG rooted at n1, dominates is correct, as it is the same as reachability. The implicit creation of the DAG rooted at n1 makes it more difficult to reason about, so I'm still for the change

@zdjones I feel that's a bit of a stretch as a justification :) The doc-comment say "Returns true if i1 dominates i2", not "in the subgraph obtained by using i1 as a new root" :) The comment near the top also says "It is implemented as a forest of DAGs; in each DAG, if node A dominates B, it means that A<B", which is not true (I mean, it is true. But IMO anyone would read this as an "if and only if", which is not true). Your observation is that asking if a root dominates another node is equivalent to asking if that other node is reachable, but TBH I'm certain that's not what's meant here :)

Agreed, every time I read it, I read it as you say. CL is enroute.

Change https://golang.org/cl/192617 mentions this issue: cmd/compile: rename poset method dominates to reaches