You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tinkerpop.apache.org by dalaro <gi...@git.apache.org> on 2016/08/04 05:55:33 UTC
[GitHub] tinkerpop pull request #372: DSP-1397 Fix StarGraph addEdge for self-edges
GitHub user dalaro opened a pull request:
https://github.com/apache/tinkerpop/pull/372
DSP-1397 Fix StarGraph addEdge for self-edges
StarGraph has directionally-specific classes for its edges:
* StarInEdge
* StarOutEdge
StarIn(/Out)Edges belong only in a StarVertex's in(/out)Edges map. We
see this assumption in StarVertex.applyGraphFilter, which invokes
`graphFilter.legalEdges(this)` and then invokes `instanceof
StarOutEdge` on each legal edge to determine its direction.
This assumption was violated by the StarVertex.addEdge method. This
method special-cases self-edge addition. This method first
unconditionally adds a StarOutEdge. Then, it checks to see whether
its parameters indicate that it is adding a self-edge. If this is so,
the method proceeds to add that same StarOutEdge instance to the
inEdges map. This is the problem. Adding a self-edge to a StarVertex
results in one StarOutEdge instance that belongs to both the inEdges
and outEdges map, which later causes the `applyGraphFilter` method's
`instanceof` checks to yield two out edges and no in edges on a
self-loop.
This commit changes StarVertex so that self-edges are represented
by a new class, StarSelfEdge.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/dalaro/incubator-tinkerpop DSP-1397
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/372.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #372
----
commit dddc44369e2c645a854b2a7bed0f4af51acd6fc5
Author: Dan LaRocque <da...@hopcount.org>
Date: 2016-08-04T04:41:44Z
DSP-1397 Fix StarGraph addEdge for self-edges
StarGraph has directionally-specific classes for its edges:
* StarInEdge
* StarOutEdge
StarIn(/Out)Edges belong only in a StarVertex's in(/out)Edges map. We
see this assumption in StarVertex.applyGraphFilter, which invokes
`graphFilter.legalEdges(this)` and then invokes `instanceof
StarOutEdge` on each legal edge to determine its direction.
This assumption was violated by the StarVertex.addEdge method. This
method special-cases self-edge addition. This method first
unconditionally adds a StarOutEdge. Then, it checks to see whether
its parameters indicate that it is adding a self-edge. If this is so,
the method proceeds to add that same StarOutEdge instance to the
inEdges map. This is the problem. Adding a self-edge to a StarVertex
results in one StarOutEdge instance that belongs to both the inEdges
and outEdges map, which later causes the `applyGraphFilter` method's
`instanceof` checks to yield two out edges and no in edges on a
self-loop.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop pull request #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro closed the pull request at:
https://github.com/apache/tinkerpop/pull/372
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/372
@dalaro i assume that this is not a new problem and also has trouble in 3.1.x line of code - if so, could you please retarget your PR at tp31 branch?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro commented on the issue:
https://github.com/apache/tinkerpop/pull/372
I'm closing this not because the conversation is settled and everything's done, but because this PR is superseded by #377. We can keep discussing here if you like. That's probably easier than juggling three PRs.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro commented on the issue:
https://github.com/apache/tinkerpop/pull/372
I opened two PRs, (one for tp31 as Stephen requested, and a new one for master):
* #377 (master)
* #378 (tp31)
As far as I can tell, GraphFilter did not exist in 3.1, and it may not even be possible to induce the buggy traversal behavior describe in #372 (which was all based on master / 3.2). The underlying datastructure corruption -- putting a StarOutEdge into the inEdges map -- does exist on 3.1, and @okram's addEdge fix applies cleanly on 3.1, but without applyGraphFilter, I'm not sure it even matters for correctness on 3.1.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by okram <gi...@git.apache.org>.
Github user okram commented on the issue:
https://github.com/apache/tinkerpop/pull/372
I believe there is an easier solution. However, you don't provide a test case so I don't know if it works.
CHANGE:
```
@Override
public Edge addEdge(final String label, final Vertex inVertex, final Object... keyValues) {
final Edge edge = this.addOutEdge(label, inVertex, keyValues);
if (inVertex.equals(this)) {
if(null == this.inEdges)
this.inEdges = new HashMap<>();
List<Edge> inE = this.inEdges.get(label);
if (null == inE) {
inE = new ArrayList<>();
this.inEdges.put(label, inE);
}
inE.add(edge);
}
return edge;
}
```
TO
```
@Override
public Edge addEdge(final String label, final Vertex inVertex, final Object... keyValues) {
final Edge edge = this.addOutEdge(label, inVertex, keyValues);
if (inVertex.equals(this)) {
if (ElementHelper.getIdValue(keyValues).isPresent())
this.addInEdge(label, this, keyValues);
else {
final Object[] keyValuesWithId = Arrays.copyOf(keyValues,keyValues.length+2);
keyValuesWithId[keyValuesWithId.length - 2] = T.id;
keyValuesWithId[keyValuesWithId.length - 1] = edge.id();
this.addInEdge(label, this, keyValuesWithId);
}
}
return edge;
}
```
Note that when I do this, all the current tests in TinkerPop pass (`StarGraphTest`). Moreover, I added a test case to `StarGraphTest` that uses a `GraphFilter`. I hope it tests what you want it to (when I didn't change the method, the test still passes :| -- thus, you may need to add a test to ensure we get failure without the new method addEdge method).
https://github.com/apache/tinkerpop/tree/TINKERPOP-1397
Finally, I think that you might think that bothE() would only return the edge once, it shouldn't. It should return it twice. If that is the misunderstanding, then this is NOT an issue.
```
gremlin> g.V(0l).bothE()
==>e[1][0-self->0]
==>e[1][0-self->0]
```
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro commented on the issue:
https://github.com/apache/tinkerpop/pull/372
@okram also, thanks for the code; I'll have a closer look at it when I iterate on this PR.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by okram <gi...@git.apache.org>.
Github user okram commented on the issue:
https://github.com/apache/tinkerpop/pull/372
Ah. Gotcha. Yea, please feel free to update my branch source with respect test that does the break and I can work to fix it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro commented on the issue:
https://github.com/apache/tinkerpop/pull/372
Thanks for the replies.
@spmallette I will investigate whether this behavior also exists on 3.1 and retarget if so. I think this will involve making a standalone test instead of just testing TP against my app and stimulating the failure that way.
@okram Yes, I realize that bothE() should return two edges. The problem this PR tried to address was that, after applying an inE graph filter to a self-looped StarVertex, the StarVertex had two edges in its outEdges map and no edges in its inEdges map (should be one each). I think this is not just some obscure internals problem, because I discovered it through a traversal. Maybe I can articulate this better with a test.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] tinkerpop issue #372: DSP-1397 Fix StarGraph addEdge for self-edges
Posted by dalaro <gi...@git.apache.org>.
Github user dalaro commented on the issue:
https://github.com/apache/tinkerpop/pull/372
I pulled master (@ fc79de813c788ee141175bbf1ea6d0cdefa94a0f) and confirmed that the bug still existed. I didn't apply your proposed change right away. Here a `gremlin.sh` session that shows the buggy behavior. I'm also pushing a unit test that I developed first, but it's easier to see what's going wrong in this `gremlin.sh` session than in the source code for a unit test.
```
$ `find gremlin-console/target -name gremlin.sh`
\,,,/
(o o)
-----oOOo-(3)-oOOo-----
plugin activated: tinkerpop.server
plugin activated: tinkerpop.utilities
plugin activated: tinkerpop.tinkergraph
gremlin> sg = org.apache.tinkerpop.gremlin.structure.util.star.StarGraph.open()
==>stargraph[starOf:null]
gremlin> v = sg.addVertex('name', 'foo')
==>v[0]
gremlin> v.addEdge('self', v)
==>e[2][0-self->0]
gremlin> sg.traversal().V().inE('self')
==>e[2][0-self->0]
gremlin> sg.traversal().V().outE('self')
==>e[2][0-self->0]
gremlin> sg.traversal().V().bothE('self')
==>e[2][0-self->0]
==>e[2][0-self->0]
// NOTE: StarOutEdge in the inEdges datastructure
gremlin> v.inEdges.values().iterator().next().get(0).getClass()
==>class org.apache.tinkerpop.gremlin.structure.util.star.StarGraph$StarOutEdge
gremlin> filter = new org.apache.tinkerpop.gremlin.process.computer.GraphFilter()
==>graphfilter[none]
gremlin> filter.setEdgeFilter(__.bothE("self"))
==>null
gremlin> sg.applyGraphFilter(filter)
==>Optional[stargraph[starOf:v[0]]]
// NOTE: no inE results, double outE results after GraphFilter is applied
gremlin> sg.traversal().V().inE('self')
gremlin> sg.traversal().V().outE('self')
==>e[2][0-self->0]
==>e[2][0-self->0]
gremlin> sg.traversal().V().bothE('self')
==>e[2][0-self->0]
==>e[2][0-self->0]
gremlin>
```
There are a couple of things worth noting above:
* the `inEdges` datastructure contains a `StarOutEdge` when we construct the graph this way
* the final post-filtering `inE` and `outE` are incorrect (an indirect consequence of the first point)
These steps produce different behavior depending on whether I invoke `StarGraph.open()` or call `StarGraph.of(<some self-looped tinkervertex>)`. If I do the latter, I get a `StarInEdge` in the `inEdges` map and a `StarOutEdge` in the `outEdges` map, and in turn avoid this particular filtering bug.
**Good news**: your change makes sense and fixes the bug I initially reported (both-filtering).
**Bad news**: I think there are more graph filtering bugs on StarGraph that can create half-edges
When I filter a self-loop star graph for either in or out, I get stuff like this (symmetrical for `.inE`):
```
gremlin> filter = new org.apache.tinkerpop.gremlin.process.computer.GraphFilter()
==>graphfilter[none]
gremlin> filter.setEdgeFilter(__.outE("self"))
==>null
gremlin> sg.applyGraphFilter(filter)
==>Optional[stargraph[starOf:v[0]]]
gremlin> sg.traversal().V()
==>v[0]
gremlin> sg.traversal().V().inE('self')
gremlin> sg.traversal().V().outE('self')
==>e[2][0-self->0]
gremlin> sg.traversal().V().bothE('self')
==>e[2][0-self->0]
gremlin>
```
@okram: This doesn't look correct, but then again, I don't really know what it should do. Should it completely destroy the self-loop, so that inE/bothE/outE all fail to emit anything associated with the self-loop? Should it transform the self-loop into a single-directional edge (which seems like one interpretation for what it does now, in which case it might be correct)?
I noticed that the name of my original branch is nonsense ("DSP-1397"). I don't think that can be changed after a PR is created. So, I'm opening a pair of new PRs: one for tp31 and one for master.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---