bboyjing's blog

Neo4j学习笔记三【图形遍历】

发表于 | 分类于

第二章已经将本章需要遍历的数据构造完毕，下面就学习下如何利用Api进行简单的图形遍历。

使用Java Api进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public static void main(String[] args){
    /**
     * 指定Neo4j存储路径
     */
    File file = new File("/opt/neo4j-community-3.0.3/data/databases/graph.db");
    GraphDatabaseService graphDB = new GraphDatabaseFactory().newEmbeddedDatabase(file);
    
    /**
     * 遍历John看过的电影
     */
    try(Transaction tx = graphDB.beginTx()){
    	//在管理界面可以查处Jobn节点的id为0
    	Node userJohn =graphDB.getNodeById(0l);
        //获取从userJon节点出发的HAS_SEEN关系
        Iterable<Relationship> allRelationShips = 
            userJohn.getRelationships(Direction.OUTGOING, MyRelationshipTypes.HAS_SEEN);
        allRelationShips.forEach(relationship -> 
       	    System.out.println("User has seen movie: " + relationship.getEndNode().getProperty("name"))
        );
       
        System.out.println(" ");
        tx.success();
    }
    
    /**
     * 遍历John的朋友喜欢而John还没有看过的电影
     */
    try(Transaction tx = graphDB.beginTx()){
    	Node userJohn =graphDB.getNodeById(0l);
        
        //遍历出John的朋友看过的电影
        Set<Node> moviesFriendsLike = new HashSet<>();
        userJohn.getRelationships(MyRelationshipTypes.IS_FRIEND_OF).forEach(friendRelation -> {
        	//获取该关系上的除指定节点外的其他节点
            Node friend = friendRelation.getOtherNode(userJohn);
            friend.getRelationships(Direction.OUTGOING, MyRelationshipTypes.HAS_SEEN).forEach(seenMovie -> 
                moviesFriendsLike.add(seenMovie.getEndNode()));
        });
        
        //遍历出John看过的电影
        Set<Node> moviesJohnLike = new HashSet<>();
        userJohn.getRelationships(Direction.OUTGOING, MyRelationshipTypes.HAS_SEEN)
            .forEach(movieJohnLike -> moviesJohnLike.add(movieJohnLike.getEndNode()));
        moviesJohnLike.forEach(movie -> 
            System.out.println("John like movie: " + movie.getProperty("name"))
        );
        System.out.println("");
        
        //过滤John看过的电影
        moviesFriendsLike.removeAll(moviesJohnLike);
        moviesFriendsLike.forEach(movie -> 
            System.out.println("Recommend movie to John: " + movie.getProperty("name"))
        );
        System.out.println("");
        
        tx.success();
    }
    graphDB.shutdown();
}

如上我们可以看到，Node.getRelationships(…)返回的时一个Iterable对象，在对结果迭代之前实际上还没有访问结果中包含的元素。这样会产生一个问题，Iterable中有可能返回非常大的数据集，当转成Java的集合类时会使用比较多的内存。Neo4j提供了一个高精炼的API，可以满足简单、自然方式描述遍历的需求。

使用Neo4j提供的API遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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);
     
     /**
      * Evaluators.atDepth(2)列出深度为2的节点，userJohn节点的深度为0
      * NODE_GLOBAL，全局相同的节点将只遍历一次
      * NODE_PATH，同一路径下，相同的节点只遍历一次
      * NODE_LEVEL，同一层级下，相同的节点只遍历一次
      */
     try(Transaction tx = graphDB.beginTx()){
     	Node userJohn = graphDB.getNodeById(0l);
        TraversalDescription traversalMoviesFriendsLike = graphDB.traversalDescription()
            .relationships(MyRelationshipTypes.IS_FRIEND_OF)
            .relationships(MyRelationshipTypes.HAS_SEEN, Direction.OUTGOING)
            .uniqueness(Uniqueness.NODE_PATH)
            .evaluator(Evaluators.atDepth(2));
        
        Traverser traverser = traversalMoviesFriendsLike.traverse(userJohn);
        Iterable<Node> moviesFriendsLike = traverser.nodes();
        moviesFriendsLike.forEach(movie -> System.out.println(movie.getProperty("name")));
        
        //PathPrinter类在下面给出
        PathPrinter pathPrinter = new PathPrinter( "name" );
        String output = "";
        for(Path path : traverser){
        	output += Paths.pathToString( path, pathPrinter );
            output += "\n";
        }
        System.out.println(output);
        
        tx.success();
     }
     graphDB.shutdown();
}
//输出结果为
Alien
Fargo
Alien
Heat
(John Johnson)--[IS_FRIEND_OF]-->(Jack Jeffries)--[HAS_SEEN]-->(Alien)
(John Johnson)--[IS_FRIEND_OF]-->(Jack Jeffries)--[HAS_SEEN]-->(Fargo)
(John Johnson)--[IS_FRIEND_OF]-->(Kate Smith)--[HAS_SEEN]-->(Alien)
(John Johnson)--[IS_FRIEND_OF]-->(Kate Smith)--[HAS_SEEN]-->(Heat)

这里.uniqueness和.evaluator需要稍微理解下，下图是数据库保存的数据结构。可以自行更改uniqueness和evaluator来查看打印结果，以帮助理解。稍微解释下NODE_GLOBAL和NODE_PATH。如果设置成NODE_GLOBAL，所有节点将只会被遍历一次，按照下图来看，如果John看过电影Fargo，就不会再遍历出Jack也看过电影Fargo的结果；如果设置成NODE_PATH，则表示在同一个路径下，一个节点只会被遍历一次，我所理解的路径时从初始节点开始，能通过有向箭头到达最后一个节点所走的路。
图三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public 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;
    }
}

自定义评估函数

上面代码遍历出了深度为2的节点，如果要从结果中排除John看过的电影，可以自定义规则。Evaluators实现定义了遍历的过程中哪些节点保存，哪些节点丢弃，下面先看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class CustomNodeFilteringEvaluator implements Evaluator{
    private final Node userNode;
    public CustomNodeFilteringEvaluator(Node userNode) {
        this.userNode = userNode;
    }
    @Override
    public Evaluation evaluate(Path path) {
        //遍历路径中的最后一个节点，当前例子中是所有的USERS、MOVIES节点
        Node currentNode = path.endNode();
        //判断是否是MOVIES节点，如果不是，则丢弃并且继续遍历
        if(!currentNode.hasLabel(MyLabels.MOVIES)){
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }
        //遍历指向当前节点的HAS_SEEN关系
        for(Relationship r : 
            currentNode.getRelationships(Direction.INCOMING, MyRelationshipTypes.HAS_SEEN)){
            //获取HAS_SEEN关系的源头，即USERS节点，如果节点是给定的目标节点（John），则丢弃
            if(r.getStartNode().equals(userNode)){
                return Evaluation.EXCLUDE_AND_CONTINUE;
            }
        }
        return Evaluation.INCLUDE_AND_CONTINUE;
    }
}

只要将自定义的CustomNodeFilteringEvaluator添加到Evaluator链中即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node userJohn = graphDB.getNodeById(0l);
TraversalDescription traversalMoviesFriendsLike = graphDB.traversalDescription()
            .relationships(MyRelationshipTypes.IS_FRIEND_OF)
            .relationships(MyRelationshipTypes.HAS_SEEN, Direction.OUTGOING)
            .uniqueness(Uniqueness.NODE_PATH)
            .evaluator(Evaluators.atDepth(2))
            .evaluator(new CustomNodeFilteringEvaluator(userJohn));
//输出结果
Alien
Alien
Heat
(John Johnson)--[IS_FRIEND_OF]-->(Jack Jeffries)--[HAS_SEEN]-->(Alien)
(John Johnson)--[IS_FRIEND_OF]-->(Kate Smith)--[HAS_SEEN]-->(Alien)
(John Johnson)--[IS_FRIEND_OF]-->(Kate Smith)--[HAS_SEEN]-->(Heat)

经过CustomNodeFilteringEvaluator，已经剔除掉John看过的电影Fargo，下面列出两张表来理解下Path接口和evaluate方法中的返回值

方法签名 描述
Node startNode() 路径的起点，不要与关系的起点混淆
Node endNode() 路径的终止点，遍历的当前节点，不要与关系的终止节点混淆
Iterable<Relationship> relationships() 按遍历顺序，到当前节点遍历过的所有关系
Iterable<Node> nodes() 按遍历顺序，路径中的所有节点
int length() 返回路径的长度，实际就是遍历过的节点数减1
方法签名 描述
INCLUDE_AND_CONTINUE 包括结果中的当前节点并继续
INCLUDE AND_PRUNE 包括结果中的当前节点但停止本路径的继续访问
EXCLUDE_AND_CONTINUE 丢弃当前节点并继续遍历
EXCLUDE_AND_PRUNE 丢弃当前节点并停止遍历

简单的图形遍历就到此结束。