Hi Rafael, Thanks for the positive review, it's always nice to hear that the answers provided were helpful, everyone on this list can take pride in that. This was an interesting problem, from what I've identified there are three main questions in your email, I'll answer them each bellow:
1. Regarding node types: There are no node types in Neo4j, since they would not provide any additional value to the storage or traversal of the graph. I've discussed this on the mailing list before, so I'll save myself a couple of keystrokes by providing a link to that discussion: http://lists.neo4j.org/pipermail/user/2008-October/000848.html In the particular case of dealing with node types in a graph matching situation this is solved by defining PatternNode object, these are structural types[1] for nodes used for finding nodes that match the type. The main way to find nodes is still through graph traversal, so the most important aspect of the "node type" is the relationships that brought us to the node, even in the graph matching case. Several PatternNode objects could theoretically match the same node, at different stages of the matching process. 2. Regarding your graph structure: If a person could live in several different kinds of places (and not only streets) your structure could be a good solution. But if a person always lives in a street you already know that the node at the other end of the relationship represents a street, and would not have to represent the type in any other way. This could even be extended, so if a person could live in either a street or at a farm (assuming that farms don't have street addresses) you could differentiate using the relationship type: Node[name="Dan Citydweller"] --[LivesInStreet]--> Node[name="Baker st."] Node[name="Farmer Bill"] --[LivesAtFarm]--> Node[name="Bills Farm"] In this situation you would not know the type of a node given to you at random, this is solved by indexing the nodes in separate indexes for each entity type (and use those to retrieve nodes to start traversing at, instead of random nodes). So in this case you would have a street index and a person index: Node getThePlaceWhereThisPersonLives(Node person) { Iterable<Node> locations = person.traverse(Order.DEPTH_FIRST, StopEvaluator.END_OF_GRAPH, ReturnableEvaluator.ALL_BUT_START_NODE, LivesInStreet, Direction.OUTGOING, LivesAtFarm, Direction.OUTGOING); Iterator<Node> iter = locations.iterator(); if (iter.hasNext()) { return iter.next(); // We know that a person only lives in one place, so stop traversing and return that place } else { return null; } } Iterable<Node> getPersonsLivingInThisStreet(Node street) { return street.traverse(Order.BREADTH_FIRST, StopEvaluator.END_OF_GRAPH, ReturnableEvaluator.ALL_BUT_START_NODE, LivesInStreet, Direction.INCOMING); } void execute() { System.out.println("Dan lives in:" + getThePlaceWhereThisPersonLives(personIndex.get("Dan Citydweller")).getProperty("name") ); System.out.println("These people live at Baker street:"); for (Node person : getPersonsLivingInThisStreet(streetIndex.get("Baker st."))) { } } We would of course have to take care of keeping the indexes updated by inserting into them when creating new persons / streets. You could of course achieve similar results by using the graph matching component, and use indexes for finding the positions for starting traversals as in the example above. i.e. the execute method would stay unchanged but the other two methods would be updated to use the graph matching component: Iterable<Node> getPersonsLivingInThisStreet(Node street) { // Create the pattern - this would be done on setup instead of each time a query is made final PatternNode personPattern = new PatternNode( "person" ); PatternNode streetPattern = new PatternNode( "street" ); personPattern.createRelationshipTo( streetPattern, LivesInStreet ); // Do the actual matching Iterable<PatternMatch> hits = PatternMatcher.getMatcher().match( streetPattern, street ); // Transform the result return new IterableWrapper<Node, PatternMatch>( hits ) { protected Node underlyingObjectToObject( PatternMatch match ) { return match.getNodeFor( personPattern ); } }; } // getThePlaceWhereThisPersonLives would be similar 3. Regarding how well this scales: 2 million nodes are not much, given that I've understood your application there should not be any problems with that size. What I don't understand however is what kinds of documents you were looking for. Documents on how to design the graph structure or documents on how the internals are implemented and the performance implications of that? Or something else entirely? For design document see the wiki at http://wiki.neo4j.org/ in particular: * The design guide: http://wiki.neo4j.org/content/Design_Guide * The domain modeling gallery: http://wiki.neo4j.org/content/Domain_Modeling_Gallery For documentation about the internals the source code is your friend, the comments in there are actually quite good with ASCII-art describing the on disk layout and all! Happy hacking! /Tobias Disclaimer: All examples are just quickly hacked up, and may contain small errors, but should hopefully convey the general idea. [1] http://en.wikipedia.org/wiki/Structural_type_system On Thu, Nov 19, 2009 at 8:38 PM, Rafael Almeida <[email protected]>wrote: > Hello, I've sent a message here earlier this year regarding finding > subgraphs inside a graph. I've got nice answers, but I didn't have the time > then to implement the ideas. Now, having a little bit more time, I have been > able to play with neo4j. > > I've been told to use the graph-matching component, it seems very nice, but > I'm having trouble using it to solve my problem. I'll describe what I need > right now: > > I have a graph which has different types of nodes and edges. I see that > there is a RelationshipType, so I've created my types using it. However, I > don't see a node type. So the types of nodes are described with a property > called "type". Both relationships and nodes may have different attributes > describing that relation and node. > > My user will give me a graph with a few properties filled in and I'll have > to find that subgraph in the bigger graph I have stored. Example, the user > will gives me something like: > > Node[type="Person"] --[LivesIn]--> Node[type="Street", name="Baker Street"] > > So I would have to match every person living in baker street. All two nodes > and relationship should be returned with all their properties. > > In order to use the graph-matching component I think I need an initial > node. So I was thinking in using index-util component to index all those > types and properties. Then, for the search part, I'd fill in the properties > of each node or connection, figure out which is the smallest set of nodes to > start from and begin the matching from there. > > I think that would work, but is that the best way to do it? Would that > scale well for a graph with 2 millions of nodes? I couldn't find much > documentation on neo's design. Perhaps I didn't look hard enough. Could > someone point me to a good document on that? Perhaps I'd need to implement > something myself or read up on some theory. Any pointers will be > appreciated. > > > > _______________________________________________ > Neo mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson <[email protected]> Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
