Reputation: 199
I have a subgraph where I know how to come to the root vertex. But then I need to walk through it.
Concretely "walk through the subgraph" in my case means that I have to walk to all leafs of the subgraph (because I know that the subgraph is like a tree) and then go the path back and do some calculations between every vertex.
My question is, how to achieve that in the most performant way?
I can think about two solutions.
First, I walk through the graph with plenty of session.executeGraph("g.V().has('id','1')").one()
statements to get all the single vertices and edges and do the calculations with them. But I think this way is very inefficient.
Or I work with the path object that I can get with
GraphNode node = session.executeGraph("g.V().has('id','1').repeat(outE().subgraph('sg').otherV()).cap('sg').path()").one();
Path path = node.asPath();
I am quite sure, the second solution is the preferred one but I have no clue how to use the path object to walk through the graph because the only thing I can see is a flat map of objects.
Here is a picture of an example tree. The goal, I need the "combined value" for node A. The rules are quite simple. The nodes (except the root) has values. The edges has weightings. I have to sum all values regarding the weights. As long as a child has only one parent I can take the complete value. In case a child has multiple parents, I have to take the weighting into account. In the example tree, the combined value of B would be
100 + (500 * 50/60) + 1000
and the combined value of A would be combined value of B plus value of C
(A == 2156.67). So, I need properties from the vertices and the edges for the calculation.
So, here is my solution.
I've implemented an abstract Tree class that is doing the actual calculation (because I also have a mock implementation).
public abstract class Tree {
// String == item id
protected final Map<String, Item> items = new HashMap<>();
private final String rootItemId;
protected Tree(String rootItemId) {
this.rootItemId = rootItemId;
}
public void accumulateExpenses() {
accumulateExpenses(null, null);
}
private double accumulateExpenses(String itemId, String parentItemId) {
final Item item = itemId == null ? items.get(rootItemId) : items.get(itemId);
final double expense = item.getExpense();
double childExpenses = 0;
for (String childId : item.getChildIds()) {
childExpenses += accumulateExpenses(childId, item.getId());
}
// calculate the percentage in case the item has multiple parents
final double percentage = item.getPercentage(parentItemId);
final double accumulatedExpenses = percentage * (expense + childExpenses);
item.setAccumulatedExpense(accumulatedExpenses);
return accumulatedExpenses;
}
}
And I've implemented a GraphTree class that is responsible to fill the item map of the super class (abstract tree).
public class GraphTree extends Tree {
public GraphTree(GraphNode graphNode, String rootNodeId) {
super(rootNodeId);
final GraphNode vertices = graphNode.get("vertices");
final GraphNode edges = graphNode.get("edges");
for (int i = 0; i < vertices.size(); i++) {
final Vertex vertex = vertices.get(i).asVertex();
final Item item = Item.fromVertex(vertex);
super.items.put(item.getId(), item);
}
for (int i = 0; i < edges.size(); i++) {
final Edge edge = edges.get(i).asEdge();
final Relation relation = Relation.fromEdge(edge);
super.items.get(relation.getParentId()).getRelations().add(relation);
}
}
}
For sake of completeness, here is also the Item class.
public class Item {
private String id;
private double accumulatedExpense;
private final List<Relation> relations = new ArrayList<>();
private final Map<String, Expense> expenses = new HashMap<>();
public void setAccumulatedExpense(double accumulatedExpense) {
this.accumulatedExpense = accumulatedExpense;
}
public double getPercentage(String parentId) {
if (parentId == null) {
return 1;
}
double totalWeight = 1;
double weight = 1;
for (Relation relation : relations) {
if (Objects.equals(id, relation.getChildId())) {
totalWeight += relation.getWeight();
if (Objects.equals(parentId, relation.getParentId())) {
weight = relation.getWeight();
}
}
}
return weight / totalWeight;
}
public static Item fromVertex(Vertex vertex) {
final Item item = new Item();
item.setId(IdGenerator.generate(vertex));
return item;
}
public List<String> getChildIds() {
return relations.parallelStream()
.filter(relation -> Objects.equals(relation.getParentId(),id))
.map(Relation::getChildId)
.collect(Collectors.toList());
}
}
To get the initial subgraph, I've used the following code.
final String statement = String.format("g.V('%s').repeat(outE().subgraph('sg').otherV()).cap('sg')", rootNodeId);
final GraphNode node = session.executeGraph(statement).one();
Upvotes: 2
Views: 941
Reputation: 10904
Even after reading the comments over and over again, I'm confused by the logic when I try to find a solution using a single query. Hence it's probably best to just tell you how to get a tree representation:
g.V().has('id','1').repeat(outE().as("e").inV()).emit(__.not(outE())).tree()
If you only need certain information (e.g. the value
property of vertices and the weight
property of edges), you can do this:
g.V().has('id','1').
repeat(outE().as("e").inV()).emit(__.not(outE())).
tree().by("value").by("weight")
And since vertex A
doesn't seem to have a value
property, you'll need to add a coalesce
step:
g.V().has('id','1').
repeat(outE().as("e").inV()).emit(__.not(outE())).
tree().by(coalesce(values("value"), constant(0))).by("weight")
UPDATE
In case I need to play with the sample graph later again, here's the code to create it:
g = TinkerGraph.open().traversal()
g.addV().property(id, "A").as("a").
addV().property(id, "B").property("value", 100).as("b").
addV().property(id, "C").property("value", 200).as("c").
addV().property(id, "D").property("value", 500).as("d").
addV().property(id, "E").property("value", 1000).as("e").
addV().property(id, "Z").property("value", 900).as("z").
addE("link").from("a").to("b").property("weight", 80).
addE("link").from("a").to("c").property("weight", 20).
addE("link").from("b").to("d").property("weight", 50).
addE("link").from("b").to("e").property("weight", 40).
addE("link").from("z").to("d").property("weight", 10).iterate()
Upvotes: 2