java - 创建图形查询语言(节点/边缘/超边缘)

Question

我正在创建一个封装 JPA 的 API具有附加属性和助手的对象。我不希望用户访问数据库，因为我必须为 API 的使用者提供某些查询功能。

我有以下内容:

Node1(w/ attributes) -- > Edge1(w/ attr.) -- > Node2(w/ attr.)

和

Node1(w/ attributes) -- > |
Node2(w/ attributes) -- > |  -- > HyperEdge1(w/ attr.)
Node3(w/ attributes) -- > |

基本上，节点 可以是特定的类型，这将决定可用属性的种类。所以我需要能够根据不同的类型和属性查询这些“路径”。

例如:从一个Node开始，找到一条路径typeA > typeB & attr1 > typeC。

所以我需要做一些简单的事情，并且能够将查询编写为字符串，或者可能是构建器模式样式。

到目前为止，我已经设置了一个访问者模式来遍历 Nodes/Edges/HyperEdges，这允许进行某种查询，但这不是很简单，因为您必须为新类型创建一个新访问者的查询。

到目前为止，这是我的实现:

    ConditionImpl hasMass = ConditionFactory.createHasMass( 2.5 );
    ConditionImpl noAttributes = ConditionFactory.createNoAttributes();

    List<ConditionImpl> conditions = new ArrayList<ConditionImpl>();
    conditions.add( hasMass );
    conditions.add( noAttributes );

    ConditionVisitor conditionVisitor = new ConditionVisitor( conditions );
    node.accept( conditionVisitor );

    List<Set<Node>> validPaths = conditionVisitor.getValidPaths();

上面的代码执行一个查询，检查起始节点的质量是否为 2.5 并且链接节点(子节点)是否没有属性。访问者执行 condition.check( Node ) 并返回一个 boolean 值。

---

我从哪里开始为更简单的图形创建查询语言？注意:我没有使用现有图形库的选项，我将有数十万个节点，加上边..

Answer 1

就个人而言，我喜欢访问者模式的想法，但是访问所有节点可能会很昂贵。

查询接口(interface):如果用户/其他开发人员正在使用它，我会使用构建器风格的接口(interface)，方法名称可读:

    Visitor v = QueryBuilder
                  .selectNodes(ConditionFactory.hasMass(2.5))
                  .withChildren(ConditionFactory.noAttributes())
                  .buildVisitor();
    node.accept(v);
    List<Set<Node>> validPaths = v.getValidPaths();

正如上面所指出的，这或多或少只是对您已有的内容的语法糖(但糖使一切变得不同)。我会将“在图上移动”的代码(例如“检查访问的节点是否满足条件”或“检查连接的节点是否满足条件”)与实际检查(或是)条件的代码分开。此外，根据条件使用复合 Material 来构建和/或:

    // Select nodes with mass 2.5, follow edges with both conditions fulfilled and check that the children on these edges have no attributes. 
    Visitor v = QueryBuilder
                  .selectNodes(ConditionFactory.hasMass(2.5))
                  .withEdges(ConditionFactory.and(ConditionFactory.freestyle("att1 > 12"), ConditionFactory.freestyle("att2 > 23")) 
                  .withChildren(ConditionFactory.noAttributes())
                  .buildVisitor();

(我使用“freestyle”是因为现在缺乏创造力，但它的意图应该很清楚)节点，通常这可能是两个不同的接口(interface)，以避免构建奇怪的查询。

    public interface QueryBuilder {
         QuerySelector selectNodes(Condition c);
         QuerySelector allNodes();
    }

    public interface QuerySelector {
         QuerySelector withEdges(Condition c);
         QuerySelector withChildren(Condition c);
         QuerySelector withHyperChildren(Condition c);
         // ...
         QuerySelector and(QuerySelector... selectors);
         QuerySelector or(QuerySelector... selectors);

         Visitor buildVisitor();
    }       

使用这种语法糖可以使查询从源代码中可读，而无需强制您实现自己的数据查询语言。 QuerySelector 实现将负责在访问的节点周围“移动”，而 Conditition 实现将检查条件是否匹配。

这种方法的明显缺点是，您需要预见接口(interface)中的大部分查询并且需要已经实现它们。

节点数量的可扩展性:您可能需要添加某种索引以加快查找“有趣”节点的速度。一个突然出现的想法是(为每个索引)向图中添加一个层，其中每个节点为“索引变量”的不同属性设置之一建模。然后，正常边可以将这些 inode 与原始图中的节点连接起来。索引上的超边可以构建一个更小的网络来进行搜索。当然，还有一种无聊的方式，就是用 attributeValue -> node 映射将索引存储在类似 map 的结构中。无论如何，这可能比上面的想法更有效。

如果您有某种索引，请确保该索引也可以接收访问者，这样它就不必访问图中的所有节点。