遍历图

本页介绍如何使用遍历框架来遍历图。

《黑客帝国》示例

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

图 1. Matrix 节点空间视图

以下是如何定义 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 关系的最终节点将是 Matrix 的编码者。

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

现在你知道是谁编写了 Matrix

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)