Neo4j学习笔记七【深度遍历（一）】

遍历顺序

在图论中有两个主要顺序算法：深度优先(depth-first)和广度优先(breadth-first)算法。下面以一个树状图作为例子来了解下这两个算法。

深度优先

深度优先：以最快的速度达到图形的最深处。

上图粗的实线是遍历的顺序依次为a -> b -> c -> d -> e -> f -> g -> h，弧形细线是遍历到叶子节点后的返回路径
遍历出的结果为1 -> 2 -> 5 -> 6 -> 3 -> 7 -> 8 -> 4 -> 9
下面通过代码来验证下结果
首先用Cypher构造一棵上图这样的树

create(node1:NUMBER{name : 1})-[:POINT_TO]->(node2:NUMBER{name : 2}),
      (node2)-[:POINT_TO]->(node5:NUMBER{name : 5}),
      (node2)-[:POINT_TO]->(node6:NUMBER{name : 6}),
      (node1)-[:POINT_TO]->(node3:NUMBER{name : 3}),
      (node3)-[:POINT_TO]->(node7:NUMBER{name : 7}),
      (node3)-[:POINT_TO]->(node8:NUMBER{name : 8}),
      (node1)-[:POINT_TO]->(node4:NUMBER{name : 4}),
      (node4)-[:POINT_TO]->(node9:NUMBER{name : 9});

使用Neo4j API对构造的数据进行遍历

public static void main(String[] args){
    File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
    GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);

    try(Transaction tx = graphDB.beginTx()){
        Node startNode = graphDB.getNodeById(7l);

        //沿着POINT_TO关系深度优先遍历
        TraversalDescription traversalDescription = graphDB.traversalDescription()
                .relationships(MyRelationshipTypes.POINT_TO, Direction.OUTGOING)
                .uniqueness(Uniqueness.NODE_PATH)
                .depthFirst();

        //从节点1开始遍历
        Iterable<Node> nodes = traversalDescription.traverse(startNode).nodes();

        for(Node n : nodes){
            System.out.print(n.getProperty("name") + " -> ");
        }
        tx.success();
    }

    graphDB.shutdown();
}
//输出结果
1 -> 4 -> 9 -> 3 -> 8 -> 7 -> 2 -> 6 -> 5 ->

通过代码看出输出结果与预期不一样，从输出结果依然是深度遍历算法，但是顺序刚好相反，猜测是否与数据构造顺序有关，下面做个测试。

//删除DEPTH类型的节点
MATCH (node:NUMBER)
DETACH DELETE node;

//重新构造数据
create(node1:NUMBER{name : 1})-[:POINT_TO]->(node4:NUMBER{name : 4}),
      (node4)-[:POINT_TO]->(node9:NUMBER{name : 9}),
      (node1)-[:POINT_TO]->(node3:NUMBER{name : 3}),
      (node3)-[:POINT_TO]->(node8:NUMBER{name : 8}),
      (node3)-[:POINT_TO]->(node7:NUMBER{name : 7}),
      (node1)-[:POINT_TO]->(node2:NUMBER{name : 2}),
      (node2)-[:POINT_TO]->(node6:NUMBER{name : 6}),
      (node2)-[:POINT_TO]->(node5:NUMBER{name : 5});

重新执行上述java代码，要修改下startNode的id，输出结果如下：
1 -> 2 -> 5 -> 6 -> 4 -> 9 -> 3 -> 7 -> 8 ->
从结果可以看出，目前看来之前猜测的结果时正确的，但是在再次把数据清掉，重新跑一下又会有如下结果
1 -> 2 -> 6 -> 5 -> 4 -> 9 -> 3 -> 7 -> 8 ->
只能再次猜测Neo4j构建数据的时候有自己的规则，左右节点的位置不一定会固定，所以深度优先遍历的时候才会出现不一样的结果。希望该猜测待以后学习深入，有机会找到合理的解释。

广度优先

广度优先：访问更远的节点之前走的尽可能广

上图粗的实线是遍历的顺序依次为a -> b -> c -> d -> e -> f -> g -> h，弧形细线是遍历到叶子节点后的返回路径
遍历出的结果为1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
下面使用之前构造好的数据，通过代码来验证下结果

public static void main(String[] args){
    File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
    GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);

    try(Transaction tx = graphDB.beginTx()){
        Node startNode = graphDB.getNodeById(7l);

        //沿着POINT_TO关系广度优先遍历
        TraversalDescription traversalDescription = graphDB.traversalDescription()
                .relationships(MyRelationshipTypes.POINT_TO, Direction.OUTGOING)
                .uniqueness(Uniqueness.NODE_PATH)
                .breadthFirst();

        //从节点1开始遍历
        Iterable<Node> nodes = traversalDescription.traverse(startNode).nodes();

        for(Node n : nodes){
            System.out.print(n.getProperty("name") + " -> ");
        }
        tx.success();
    }

    graphDB.shutdown();
}
//输出结果
1 -> 2 -> 4 -> 3 -> 6 -> 5 -> 9 -> 7 -> 8 ->

从结果可以看出，广度优先遍历的算法是正确的，但是同级节点遍历的顺序跟语气有点不一样，原因应该与上面一样。
至于遍历时选择哪种遍历方式，还是要根据数据模型的分布来定。

扩展关系

扩展器是Neo4j遍历Api的一个部件，负责决定遍历期间访问过的任意节点应该跟踪哪个关系。除选择关系类型和访问外，扩展器还负责跟踪关系的顺序。

标准扩展器

现在还不理解扩展器是个什么东西，用一个例子来演示下：在一个社交网络中，一起工作的人们通过WORKS_WITH关系连接起来，是密切朋友的人们通过IS_FRIEND_OF关系连接起来。我们要做的是查找John的直接关系（朋友和同事）喜欢的所有电影，该示例图形如下：

//首先通过Cypher构造数据
create(john:PERSON{name : 'John'})-[:LIKES]->(topGun:FILM{title : 'Top Gun'}),
      (john)-[:IS_FRIEND_OF]->(kate:PERSON{name : 'KATE'}),
      (john)-[:WORK_WITH]->(emma:PERSON{name : 'EMMA'}),
      (kate)-[:LIKES]->(fargo:FILM{title : 'Fargo'}),
      (kate)-[:WORK_WITH]->(alex:PERSON{name : 'Alex'}),
      (kate)-[:WORK_WITH]->(jack:PERSON{name : 'JACK'}),
      (emma)-[:WORK_WITH]->(jack),
      (emma)-[:LIKES]->(alien:FILM{title : 'Alien'}),
      (alex)-[:LIKES]->(godfather:FILM{title : 'Godfather'}),
      (jack)-[:LIKES]->(godfather),
      (jack)-[:LIKES]->(great:FILM{title : 'Great'});

下面用Neo4j api遍历

public static void main(String[] args) {
    File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
    GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);

    try(Transaction tx = graphDB.beginTx()){
        Node userJohn = graphDB.getNodeById(44l);

        //构造StandardExpander，添加要扩展的关系类型
        PathExpander standardExpander = StandardExpander.DEFAULT
                .add(MyRelationshipTypes.WORK_WITH)
                .add(MyRelationshipTypes.IS_FRIEND_OF)
                .add(MyRelationshipTypes.LIKES);

        //在最终结果中只考虑深度2上的节点，并且只保留电影节点
        TraversalDescription traversalDescription = graphDB.traversalDescription()
                .expand(standardExpander)
                .evaluator(Evaluators.atDepth(2))
                .evaluator(path -> {
                    if(path.endNode().hasProperty("title")){
                        return Evaluation.INCLUDE_AND_CONTINUE;
                    }
                    return Evaluation.EXCLUDE_AND_CONTINUE;
                });

        //从节点john开始遍历
        Iterable<Node> nodes = traversalDescription.traverse(userJohn).nodes();
        for(Node n : nodes){
            System.out.print(n.getProperty("title") + " -> ");
        }

        tx.success();
    }

    graphDB.shutdown();
}
//输出结果为
Alien -> Fargo ->

若果将.expand()改成.relationships()结果是一样的，使用expand代码会更清晰更简洁。

...
TraversalDescription traversalDescription = graphDB.traversalDescription()
    .relationships(MyRelationshipTypes.WORK_WITH)
    .relationships(MyRelationshipTypes.IS_FRIEND_OF)
    .relationships(MyRelationshipTypes.LIKES)
...

//以下时截取的源码，从源码看出relationships()底层实现就是StandardExpander
public TraversalDescription relationships(RelationshipType type, Direction direction) {
    if(this.expander instanceof StandardExpander) {
        return this.expand(((StandardExpander)this.expander).add(type, direction));
    } else {
        throw new IllegalStateException("The current expander cannot be added to");
    }
}

用于扩展的顺序关系

StandardExpander有一个限制，要扩展的关系顺序时固定的，使用的是创建时的关系顺序，但是在一些情况下会挑选一个特定的顺序扩展关系。沿用上面的例子，这一次我们要按自己的意愿先输出John的朋友看过的电影，还是John的同事先看过的电影。

 public static void main(String[] args) {
	File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
	GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);

	try(Transaction tx = graphDB.beginTx()){
		Node userJohn = graphDB.getNodeById(44l);

		//OrderedByTypeExpander，添加要扩展的关系类型，总是先遍历WORK_WITH关系
		PathExpander orderedByTypeExpander = new OrderedByTypeExpander()
				.add(MyRelationshipTypes.WORK_WITH)
				.add(MyRelationshipTypes.IS_FRIEND_OF)
				.add(MyRelationshipTypes.LIKES);

		//在最终结果中只考虑深度2上的节点，并且只保留电影节点
		TraversalDescription traversalDescription = graphDB.traversalDescription()
				.expand(orderedByTypeExpander)
				.evaluator(Evaluators.atDepth(2))
				.evaluator(path -> {
					if(path.endNode().hasProperty("title")){
						return Evaluation.INCLUDE_AND_CONTINUE;
					}
					return Evaluation.EXCLUDE_AND_CONTINUE;
				});

		//从节点john开始遍历
		Iterable<Node> nodes = traversalDescription.traverse(userJohn).nodes();
		for(Node n : nodes){
			System.out.print(n.getProperty("title") + " -> ");
		}

		tx.success();
	}

	graphDB.shutdown();
}
//输出结果
Alien -> Fargo ->

下面改变顺序，先输出朋友看过的电影

...
//OrderedByTypeExpander，添加要扩展的关系类型，总是先遍历IS_FRIEND_OF关系，只需要把IS_FRIEND_OF放在WORK_WITH前面即可
PathExpander orderedByTypeExpander = new OrderedByTypeExpander()
	.add(MyRelationshipTypes.IS_FRIEND_OF)
	.add(MyRelationshipTypes.WORK_WITH)
	.add(MyRelationshipTypes.LIKES);
...
//输出结果
Fargo -> Alien ->

自定义扩展

下面我们不利用Neo4j的Api部件，使用自定义PathExpander来实现John的直接联系人喜欢的所有电影。
为了实现这个目标，我们将自定义一个具有一下特性的扩展器

• 仅仅跟踪从起始节点（John）开始的IS_FRIEND_OF和WORK_WITH关系
• 对所有在深度1访问过的节点（代表John的朋友和同事）仅仅跟踪LIKES关系

public class DepthAwareExpander implements PathExpander{
    //使用Map存储要跟踪的遍历深度和关系类型之间的映射
    private final Map<Integer, List<RelationshipType>> relationshipToDepthMapping;

    public DepthAwareExpander(Map<Integer, List<RelationshipType>> relationshipToDepthMapping) {
        this.relationshipToDepthMapping = relationshipToDepthMapping;
    }

    @Override
    public Iterable<Relationship> expand(Path path, BranchState branchState) {
        //查找遍历的当前深度
        int depth= path.length();

        //在当前的深度查找要跟踪的关系
        List<RelationshipType> relationshipTypes = relationshipToDepthMapping.get(depth);

        //扩展当前节点配置过的类型的所有关系
        RelationshipType[] relationshipTypeArray =  new RelationshipType[0];
        RelationshipType[] relationshipTypesArray = relationshipTypes.toArray(relationshipTypeArray);
        return path.endNode().getRelationships(relationshipTypesArray);
    }

    @Override
    public PathExpander reverse() {
        return null;
    }
}

public static void main(String[] args) {
	File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
	GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);

	try(Transaction tx = graphDB.beginTx()){
		//配置深度、关系映射
		Map<Integer, List<RelationshipType>> mappings = new HashMap<>();
		mappings.put(0,
			Arrays.asList(new RelationshipType[]{
				MyRelationshipTypes.IS_FRIEND_OF,
				MyRelationshipTypes.WORK_WITH})
		);
		mappings.put(1, Arrays.asList(new RelationshipType[]{MyRelationshipTypes.LIKES}));

		Node userJohn = graphDB.getNodeById(44l);

		TraversalDescription traversalDescription = graphDB.traversalDescription()
				.expand(new DepthAwareExpander(mappings))
				.evaluator(Evaluators.atDepth(2));

		//从节点john开始遍历
		Iterable<Node> nodes = traversalDescription.traverse(userJohn).nodes();
		for(Node n : nodes){
			System.out.print(n.getProperty("title") + " -> ");
		}

		tx.success();
	}

	graphDB.shutdown();
}