DSE Graphique avec Java Driver, comment parcourir un graphe (comme un arbre)

Question

J'ai un sous-graphe où je sais comment arriver au sommet racine. Mais alors j'ai besoin de le traverser. Concrètement, "parcourir le sous-graphe" dans mon cas signifie que je dois marcher à toutes les feuilles du sous-graphe (parce que je sais que le sous-graphe est comme un arbre), puis revenir en arrière et faire des calculs entre chaque sommet. Ma question est, comment y parvenir de la manière la plus performante?

Je peux penser à deux solutions. D'abord, je parcours le graphique avec beaucoup de session.executeGraph("g.V().has('id','1')").one() instructions pour obtenir tous les sommets simples et les bords et faire les calculs avec eux. Mais je pense que cette façon est très inefficace.

Ou je travaille avec l'objet chemin que je peux obtenir avec

GraphNode node = session.executeGraph("g.V().has('id','1').repeat(outE().subgraph('sg').otherV()).cap('sg').path()").one(); 
Path path = node.asPath(); 

Je suis tout à fait sûr, la deuxième solution est le préféré un mais je n'ai pas la moindre idée comment utiliser l'objet de chemin de marcher à travers la graphique parce que la seule chose que je peux voir est une carte plate des objets.

Mise à jour # 1

Voici une photo d'un arbre par exemple. Le but, j'ai besoin de la "valeur combinée" pour le noeud A. Les règles sont assez simples. Les noeuds (sauf la racine) ont des valeurs. Les bords ont des pondérations. Je dois additionner toutes les valeurs concernant les poids. Tant qu'un enfant n'a qu'un seul parent, je peux prendre la valeur complète. Dans le cas où un enfant a plusieurs parents, je dois prendre en compte la pondération. Dans l'arborescence exemple, la valeur combinée de B serait 100 + (500 * 50/60) + 1000 et la valeur combinée des A serait combined value of B plus value of C (A == 2156,67). Donc, j'ai besoin de propriétés à partir des sommets et des arêtes pour le calcul.

Mise à jour # 2

Donc, voici ma solution.

J'ai implémenté une classe arborescente abstraite qui effectue le calcul réel (car j'ai également une implémentation fictive).

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; 
    } 
} 

Et j'ai mis en place une classe GraphTree qui est responsable de remplir la carte de l'élément de la super classe (arbre abstrait).

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); 
     } 
    } 
} 

Par souci d'exhaustivité, voici également la classe Item.

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()); 
    } 
} 

Pour obtenir le sous-graphe initial, j'ai utilisé le code suivant.

final String statement = String.format("g.V('%s').repeat(outE().subgraph('sg').otherV()).cap('sg')", rootNodeId); 
    final GraphNode node = session.executeGraph(statement).one(); 

Answer 1

Même après avoir lu les commentaires, encore et encore, je suis confus par la logique lorsque je tente de trouver une solution à l'aide d'une seule requête.Par conséquent, il est probablement préférable de simplement vous dire comment obtenir une représentation arborescente:

g.V().has('id','1').repeat(outE().as("e").inV()).emit(__.not(outE())).tree() 

Si vous avez seulement besoin de certaines informations (par exemple, la propriété value des sommets et la propriété weight des bords), vous pouvez le faire:

g.V().has('id','1'). 
    repeat(outE().as("e").inV()).emit(__.not(outE())). 
    tree().by("value").by("weight") 

Et puisque le sommet A ne semble pas avoir une propriété value, vous aurez besoin d'ajouter une étape coalesce:

g.V().has('id','1'). 
    repeat(outE().as("e").inV()).emit(__.not(outE())). 
    tree().by(coalesce(values("value"), constant(0))).by("weight") 

MISE À JOUR

Dans le cas où je dois jouer avec le graphique de l'échantillon plus tard encore, voici le code pour créer:

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()