遍历图

本页描述了如何使用遍历框架遍历图。

矩阵示例

此遍历图示例使用了电影三部曲《黑客帝国》中的一些角色。源码位于NewMatrix.java。

图 1. 矩阵节点空间视图

下面示例展示了如何定义 TraversalDescription 来查找某人 X 的所有朋友以及朋友的朋友，并返回排除 X 本人的结果

private Traverser getFriends( Transaction transaction, final Node person )
{
    TraversalDescription td = transaction.traversalDescription()
            .breadthFirst()
            .relationships( RelTypes.KNOWS, Direction.OUTGOING )
            .evaluator( Evaluators.excludeStartPosition() );
    return td.traverse( person );
}

执行实际遍历并打印所有找到的朋友的姓名

int numberOfFriends = 0;
String output = neoNode.getProperty( "name" ) + "'s friends:\n";
Traverser friendsTraverser = getFriends( tx, neoNode );
for ( Path friendPath : friendsTraverser )
{
    output += "At depth " + friendPath.length() + " => "
              + friendPath.endNode()
                      .getProperty( "name" ) + "\n";
    numberOfFriends++;
}
output += "Number of friends found: " + numberOfFriends + "\n";

遍历返回以下输出

Thomas Anderson's friends:
At depth 1 => Morpheus
At depth 1 => Trinity
At depth 2 => Cypher
At depth 3 => Agent Smith
Number of friends found: 4

破解矩阵

要找到《黑客帝国》的幕后策划者，遵循所有类型为 KNOWS 或 CODED_BY 的出向关系。与 CODED_BY 关系相连的最终节点就是矩阵的编码者。

private Traverser findHackers( Transaction transaction, final Node startNode )
{
    TraversalDescription td = transaction.traversalDescription()
        .breadthFirst()
        .relationships( RelTypes.CODED_BY, Direction.OUTGOING )
        .relationships( RelTypes.KNOWS, Direction.OUTGOING )
        .evaluator(Evaluators.includeWhereLastRelationshipTypeIs( RelTypes.CODED_BY ) );
    return td.traverse( startNode );
}

下面展示如何打印结果并查找所有黑客

String output = "Hackers:\n";
int numberOfHackers = 0;
Traverser traverser = findHackers( tx, getNeoNode( tx ) );
for ( Path hackerPath : traverser )
{
    output += "At depth " + hackerPath.length() + " => " + hackerPath.endNode().getProperty( "name" ) + "\n";
    numberOfHackers++;
}
output += "Number of hackers found: " + numberOfHackers + "\n";

现在你知道谁编写了矩阵

Hackers:
At depth 4 => The Architect
Number of hackers found: 1

遍历有序路径

下面的示例展示了如何使用自定义的 Evaluator 来查找符合预定义顺序的路径。源码位于OrderedPath.java。

首先，创建将在其上进行遍历的示例图

Node A = tx.createNode();
Node B = tx.createNode();
Node C = tx.createNode();
Node D = tx.createNode();

A.createRelationshipTo( C, REL2 );
C.createRelationshipTo( D, REL3 );
A.createRelationshipTo( B, REL1 );
B.createRelationshipTo( C, REL2 );

在设置图的遍历时，将关系的顺序（REL1 → REL2 → REL3）存储在一个 ArrayList 中。遍历时，Evaluator 可以检查该顺序，以确保仅返回符合预定义关系顺序的路径。

final ArrayList<RelationshipType> orderedPathContext = new ArrayList<>();
orderedPathContext.add( REL1 );
orderedPathContext.add( REL2 );
orderedPathContext.add( REL3 );
TraversalDescription td = tx.traversalDescription()
    .evaluator( new Evaluator()
    {
        @Override
        public Evaluation evaluate( final Path path )
        {
            if ( path.length() == 0 )
            {
                return Evaluation.EXCLUDE_AND_CONTINUE;
            }
            RelationshipType expectedType = orderedPathContext.get( path.length() - 1 );
            boolean isExpectedType = path.lastRelationship()
                    .isType( expectedType );
            boolean included = path.length() == orderedPathContext.size() && isExpectedType;
            boolean continued = path.length() < orderedPathContext.size() && isExpectedType;
            return Evaluation.of( included, continued );
        }
    } )
    .uniqueness( Uniqueness.NODE_PATH ); (1)

请注意，唯一性设置为 Uniqueness.NODE_PATH。这使得在遍历过程中可以重新访问同一节点，但不能重新访问相同的路径。

然后，执行遍历并打印所有找到的有序路径

Traverser traverser = td.traverse( tx.getNodeById( A.getId() ) );
PathPrinter pathPrinter = new PathPrinter( "name" );
for ( Path path : traverser )
{
    output += Paths.pathToString( path, pathPrinter );
}

这会返回以下输出

(A)--[REL1]-->(B)--[REL2]-->(C)--[REL3]-->(D)

在此示例中，使用了自定义类来格式化路径输出。

static class PathPrinter implements Paths.PathDescriptor<Path>
{
    private final String nodePropertyKey;

    public PathPrinter( String nodePropertyKey )
    {
        this.nodePropertyKey = nodePropertyKey;
    }

    @Override
    public String nodeRepresentation( Path path, Node node )
    {
        return "(" + node.getProperty( nodePropertyKey, "" ) + ")";
    }

    @Override
    public String relationshipRepresentation( Path path, Node from, Relationship relationship )
    {
        String prefix = "--", suffix = "--";
        if ( from.equals( relationship.getEndNode() ) )
        {
            prefix = "<--";
        }
        else
        {
            suffix = "-->";
        }
        return prefix + "[" + relationship.getType().name() + "]" + suffix;
    }
}

遍历中路径的唯一性

下面的示例演示了节点唯一性的使用。它列出所有由 Principal1 拥有的、从其他宠物继承下来的宠物。

后代示例图

uniqueness of paths in traversals graph

要返回所有属于 Principal1 且为 Pet0 的后代（即 Pet1 和 Pet3），遍历的唯一性需要设置为 NODE_PATH，而非默认的 NODE_GLOBAL。这样，节点可以被遍历多次，且可以返回那些节点不同但有部分节点（如起始节点和终止节点）相同的路径。

Node dataTarget = data.get().get( "Principal1" );
String output = "";
int count = 0;
try ( Transaction transaction = graphdb().beginTx() )
{
    start = transaction.getNodeById( start.getId() );
    final Node target = transaction.getNodeById( dataTarget.getId() );
    TraversalDescription td = transaction.traversalDescription()
            .uniqueness( Uniqueness.NODE_PATH )
            .evaluator( new Evaluator()
    {
        @Override
        public Evaluation evaluate( Path path )
        {
            boolean endNodeIsTarget = path.endNode().equals( target );
            return Evaluation.of( endNodeIsTarget, !endNodeIsTarget );
        }
    } );

    Traverser results = td.traverse( start );
}

这将返回以下路径

(2)-[descendant,2]->(0)<-[owns,5]-(1)
(2)-[descendant,0]->(5)<-[owns,3]-(1)

你还可以看到它与使用 NODE_GLOBAL 唯一性时的区别。请注意，TraversalDescription 对象是不可变的，因此需要创建新的实例。

TraversalDescription nodeGlobalTd = tx.traversalDescription().uniqueness( Uniqueness.NODE_PATH ).evaluator( new Evaluator()
{
    @Override
    public Evaluation evaluate( Path path )
    {
        boolean endNodeIsTarget = path.endNode().equals( target );
        return Evaluation.of( endNodeIsTarget, !endNodeIsTarget );
    }
} ).uniqueness( Uniqueness.NODE_GLOBAL );
Traverser results = nodeGlobalTd.traverse( start );

现在只返回一条路径，因为节点 Principal1 只能被遍历一次。

(2)-[descendant,2]->(0)<-[owns,5]-(1)