Consider allowing `MutableCTree#putEdge` to indirectly change the root of the tree

[jbduncan]

Currently, if one is given a CTree like the following,

MutableCTree tree = TreeBuilder.builder().build();
tree.putEdge("b", "c");

then if one tries to add the following edge,

tree.putEdge("a", "b");

then it throws an IllegalArgumentException, because it tries to implicitly change the root from "b" to "a", and yet the method doesn't allow it.

I personally found this to be surprising behaviour when implementing tests for https://github.com/jrtom/jung/issues/83, as it means when I try to test that the two following pieces of code do the same thing,

tree.putEdge("b", "c");
tree.putEdge("a", "b");

. . .

tree.putEdge("a", "b");
tree.putEdge("b", "c");

it throws an exception, but not for the reason that I expected.

I'd also expect users to be surprised by this behaviour. IMO, if one wants to prevent changing the root of a tree when adding new edges to it, then they should use a function like this:

public static boolean putEdgeUnlessRootWouldChange(MutableCTree<N> tree, N nodeU, N nodeV) {
  if (tree.root().isPresent() && tree.root().get().equals(nodeV)) {
    // do something appropriate here: throw exception, return false, etc.
  } else {
    return tree.putEdge(nodeU, nodeV);
  }
}

[jbduncan]

In other words, if given the following tree:

B -> C -> D

then I would expect tree.putEdge(A, B) to be legal, changing the tree to:

A -> B -> C -> D

and making A the new root.

[tomnelson]

Did you read the javadocs for MutableCTree::putEdge?

On Tue, Dec 26, 2017 at 6:24 PM, Jonathan Bluett-Duncan < [email protected]> wrote:

Currently, if one is given a CTree like the following,

MutableCTree tree = TreeBuilder.builder().build(); tree.putEdge("b", "c");

then if one tries to add the following edge,

tree.putEdge("a", "b");

then it throws an IllegalArgumentException, because it tries to implicitly change the root from "b" to "a", and yet the method doesn't allow it.

I personally found this to be surprising behaviour when implementing tests for #83 https://github.com/jrtom/jung/issues/83, as it means when I try to test that the two following pieces of code do the same thing,

tree.putEdge("b", "c"); tree.putEdge("a", "b"); . . .

tree.putEdge("a", "b"); tree.putEdge("b", "c");

it throws an exception, but not for the reason that I expected.

I'd also expect users to be surprised by this behaviour. IMO, if one wants to prevent changing the root of a tree when adding new edges to it, then they should use a function like this:

public static boolean putEdgeUnlessRootWouldChange(MutableCTree<N> tree, N nodeU, N nodeV) { if (tree.root().isPresent() && tree.root().get().equals(nodeV)) { // do something appropriate here: throw exception, return false, etc. } else { return tree.putEdge(nodeU, nodeV); } }

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/jrtom/jung/issues/169, or mute the thread https://github.com/notifications/unsubscribe-auth/AAGbB4dn8lZ7aZ5DcSi1gbSIPdWJKmRrks5tEYAZgaJpZM4RNDxX .

[jbduncan]

Did you read the javadocs for MutableCTree::putEdge?

Oh oops, I thought I did, but apparently I didn't read it properly yesterday.

Reading the JavaDoc again, I think I understand why the first requirement is written as it is. Looking at its exact wording,

<li>{@code nodeU} must be already in the tree, or the tree must be empty

I understand that if nodeU is not already in the tree and the tree is not empty, then adding edge nodeU -> nodeV will introduce a new disconnected tree to the overall graph, thus introducing another root to the tree, which is invalid. This explains to me why this requirement is mandatory.

However, looking at the second requirement,

<li>{@code nodeV} must either not be in the tree, or there must be an existing edge
connecting {@code nodeU} to {@code nodeV} (in which case this method is a no-op).

It seems to me that it could be loosened a bit and made to read like this:

<li>{@code nodeV} must either be the root of the tree, or
there must be an existing edge connecting {@code nodeU} to
{@code nodeV} (in which case this method is a no-op).

As far as I can tell, even with this loosened rule, and with an appropriate implementation to match it, one would still always end up with a valid tree.

I suppose I'm wondering why the current incarnation of this requirement doesn't allow nodeV to be equals() to the root, and in turn allow a transformation of a tree from something like this:

        B -> C -> D
        ^
        Old root

to this:

        A -> B -> C -> D
        ^    ^
 New root    Old root

@tomnelson Do you have any further thoughts on this?

[tomnelson]

I don't like the no op if it's already there. I would have expected an exception, especially if Joshua wrote it. :-)

On Dec 27, 2017 12:15 PM, "Jonathan Bluett-Duncan" [email protected] wrote:

Did you read the javadocs for MutableCTree::putEdge?

Oh oops, I thought I did, but apparently I didn't read it properly yesterday.

Reading the JavaDoc again, I think I understand why the first requirement is written as it is. Looking at its exact wording,

{@code nodeU} must be already in the tree, or the tree must be empty

I understand that if nodeU is not already in the tree and the tree is not empty, then adding edge nodeU -> nodeV will introduce a new disconnected tree to the overall graph, thus introducing another root to the tree, which is invalid. This explains to me why this requirement is mandatory.

However, looking at the second requirement,

{@code nodeV} must either not be in the tree, or there must be an existing edge connecting {@code nodeU} to {@code nodeV} (in which case this method is a no-op).

It seems to me that it could be loosened a bit and made to read like this:

{@code nodeV} must either be the root of the tree, or there must be an existing edge connecting {@code nodeU} to {@code nodeV} (in which case this method is a no-op).

As far as I can tell, even with this loosened rule, one would still end up with a valid tree.

I suppose I'm wondering why the current incarnation of this requirement doesn't allow nodeV to be equals() to the root, and in turn allow a transformation of a tree from something like this:

    B -> C -> D
    ^
    Old root

to this:

    A -> B -> C -> D
    ^    ^

New root Old root

@tomnelson https://github.com/tomnelson Do you have any further thoughts on this?

— You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub https://github.com/jrtom/jung/issues/169#issuecomment-354145262, or mute the thread https://github.com/notifications/unsubscribe-auth/AAGbByQ37U0Qh06E7xbz8WveMucBd8TKks5tEnszgaJpZM4RNDxX .

[jbduncan]

@tomnelson I don't believe there's anything in the JavaDocs or wiki for com.google.common.graph to suggest that adding an existing edge to a normal MutableGraph should throw an IllegalArgumentException, so I'm not entirely sure why it should throw an IllegalArgumentException for MutableCTree. :/

[tomnelson]

You're probably right. I was just kidding Joshua about how he usually programs strong defenses against any surprises.

On Dec 27, 2017 2:32 PM, "Jonathan Bluett-Duncan" [email protected] wrote:

@tomnelson https://github.com/tomnelson I don't believe there's anything in the JavaDocs or wiki for com.google.common.graph to suggest that adding an existing edge to a normal MutableGraph should throw an IllegalArgumentException, so I'm not entirely sure why it throw an IllegalArgumentException for MutableCTree. :/

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/jrtom/jung/issues/169#issuecomment-354165946, or mute the thread https://github.com/notifications/unsubscribe-auth/AAGbB0P7ijyRDrZ0ZHJHdxbC83TgkodVks5tEps1gaJpZM4RNDxX .

[jrtom]

CONSTANT VIGILANCE! (channelling Mad-Eye Moody :) )

I am open to reconsidering the semantics of MutableCTree.putEdge(), but there are reasons the way that is as it is. Currently...

(1) ...it's never legal to call tree.putEdge(a, b) if b is already in the tree. This is a nice, simple rule that's easy to communicate, especially versus "it's only legal to call tree.putEdge(a, b) given b is already in the tree if b is the current root and a is not in the tree". I like easily understandable constraints. :)

(2) ...the first node that you add to the tree is always the root, and it always remains the root. This, too, is easy to communicate and understand. (I haven't quite decided whether I want the *Tree*Builder to be the way that the root is specified; note that the API waffles on this point at the moment.)

If there are use cases that would warrant relaxing that constraint, let's talk about it. But it's always easier to relax constraints than to add them later.

[jbduncan]

@jrtom Ah, you make a very good point about how "it's never legal to call tree.putEdge(a, b) if b is already in the tree" is an easy rule to communicate.

I personally don't have a use case that warrants relaxing this constraint, so I'm happy to leave it up to you to decide if this issue is worth keeping open. :)

[jbduncan]

It's not so clear to me if we should say that the first node added to a tree is always the root of the tree, though.

What if the tree is fully cleared of edges through repeated calls to tree#removeEdge, and then the root node is removed with tree.root().ifPresent(tree::removeNode)? Should the removal of the root like this be allowed? I don't necessarily see why it shouldn't be allowed, unless we also want to enforce the constraint that a tree always has a root for simplicity.

[jrtom]

We can edit that to "first node added to an empty tree". :) I'm not actually advocating for disallowing removing the root from a tree; if nothing else, that, too, adds a special case that doesn't seem beneficial.

I'm going to leave this issue open for now so that we don't lose track of the documentation aspects, but I think that the status quo is fine in terms of semantics.