Re: [Neo4j] Some questions about design when using neo4j
Gen, I guess there is nothing out of the box right now, but you could get inspiration from http://jung.sourceforge.net/doc/api/index.html, especially http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html and implement one or just use it on a toy graph to test it out? Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Sat, Sep 3, 2011 at 12:33 AM, Benjamin Gustafsson benjamingustafs...@gmail.com wrote: Just in case there are any graph experts out there that want to exercise their brains. (Its quite a while since I studied algorithms and optimization regarding graphs. :-) I'm able to implement a algorithm described in pseudocode (if anyone knows a good algorithm for my special case below). I have the transportation problem and need to find a preferably small (not necessarily smallest) set of nodes that transports a certain amount of credit/commodity from source node S to sink node T. All edges have a capacity stated as a attribute for the edge, this can be read while traversing the graph. Transportation cost for commodity/credit in the graph is zero. The only cost in this graph problem is computation time to *find a set of paths delivering all the commodity*(in my case credit). The path lengths chosen are not important. (This is the standard ripplepay problem, but I didn't like the algorithms used by the original ripplepay implementation. It does not scale up to millions of users. It is not fast enough.) http://en.wikipedia.org/wiki/Transportation_network_%28graph_theory%29 And I also need a quick way of analysing if it is possible to send all commodity across the network. If the amount commodity to be sent is lower than max flow. (lower than min cut). There will initially be clusters with very few edges connecting the clusters. If the nodes are in different clusters the min cut can be really easy/*quick* to find (if we do it the right way). http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Any implementations for neo4j already available regarding my special case? -- //Benjamin Gustafsson ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Some questions about design when using neo4j
Hey, If you want to play with JUNG over Neo4j, you can do it via TinkerPop. Graph g = new Neo4jGraph(/tmp/neo4j); GraphJung jung = new GraphJung(g); That GraphJung object is a implementation of the JUNG Interfaces and can be processed by the JUNG algorithms package. https://github.com/tinkerpop/blueprints/wiki/JUNG-Ouplementation HTH, Marko. http://markorodriguez.com On Sep 28, 2011, at 1:06 AM, Peter Neubauer wrote: Gen, I guess there is nothing out of the box right now, but you could get inspiration from http://jung.sourceforge.net/doc/api/index.html, especially http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html and implement one or just use it on a toy graph to test it out? Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/- Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Sat, Sep 3, 2011 at 12:33 AM, Benjamin Gustafsson benjamingustafs...@gmail.com wrote: Just in case there are any graph experts out there that want to exercise their brains. (Its quite a while since I studied algorithms and optimization regarding graphs. :-) I'm able to implement a algorithm described in pseudocode (if anyone knows a good algorithm for my special case below). I have the transportation problem and need to find a preferably small (not necessarily smallest) set of nodes that transports a certain amount of credit/commodity from source node S to sink node T. All edges have a capacity stated as a attribute for the edge, this can be read while traversing the graph. Transportation cost for commodity/credit in the graph is zero. The only cost in this graph problem is computation time to *find a set of paths delivering all the commodity*(in my case credit). The path lengths chosen are not important. (This is the standard ripplepay problem, but I didn't like the algorithms used by the original ripplepay implementation. It does not scale up to millions of users. It is not fast enough.) http://en.wikipedia.org/wiki/Transportation_network_%28graph_theory%29 And I also need a quick way of analysing if it is possible to send all commodity across the network. If the amount commodity to be sent is lower than max flow. (lower than min cut). There will initially be clusters with very few edges connecting the clusters. If the nodes are in different clusters the min cut can be really easy/*quick* to find (if we do it the right way). http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Any implementations for neo4j already available regarding my special case? -- //Benjamin Gustafsson ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
[Neo4j] Some questions about design when using neo4j
Hi I'm trying to figure out how to design a graph database where I have 1. Users 2. Groups 3. Items 4. credit_line -relation between Users. A balance of credit. 5. credit_line -relation between Users and Groups. 6. memberOf-relation from Users to Groups. 7. have -relation between User and Item. 8. display -relation between Item,User and User/Group. (A triple) (a Item belonging to a User is displayed as available for only a specific group/user, or multiple groups/users. This is unclear how it should be represented in neo4j, does it need a node?) 9. owesItemTo -relation between User, Item, User/Group. (A triple, Do I need a node?) The credit line will have limits. [Credit given by node A and Credit given by node B] These limits defines the credit line. My thoughts are therefore to place the balance accounting as a property on the edges in the database. Node:User -- Edge with Property: Credit line, value -- Node:User Node:User -- Edge with Property: Credit line, value -- Node:Group But I feel that this approach is kind of weak. I really don't know how to represent the credit line. (Maybe it needs a node... Because if I use two directed edges they need to be synchronised all the time. If A owes value to B, B owes -value to A) How would you have designed this? It is to be used as a multi user database. I will therefore use a lot of transactions in the application, editing balances between users and groups, in long chains as atomic actions. (This has to be quick so that the same node and edges can be used by the next transaction.) I have thought about traversal algorithms that may be executed in advance to find a path. And then try to use the pre-discovered path in a quick transaction, or roll back if the path no longer has enough credit available in all the chain. To understand how my credit line should be used you can take a look att ripplepay.com. But I'm designing a barter system with items. -- //Benjamin Gustafsson ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Some questions about design when using neo4j
On Tue, Aug 30, 2011 at 1:20 PM, Benjamin Gustafsson benjamingustafs...@gmail.com wrote: If an item can only be had by one user at a time, then the display, or visible_to, relationship could originate from the item. 9. owesItemTo -relation between User, Item, User/Group. (A triple, Do I need a node?) Same here. Thanks I will rename have to owner_of. Then use the relations item visible_to user/group item currently_held_by user/group Why would you need two relationships? Can you let a single relationship represent the mutual credit line between two users? If I use a single directed relationship, how could I prepare the data for the traversal to be fast? I know the traversal is equally fast in both directions, but the calculation remaining_credits can be made in advance or while traversing. I can't really decide if the pre calculated properties remaining_credits will make traversal faster or if it just introduces the unnecessary risk of inconsistency. I could have 5 properties: long balance long end_node_limit long start_node_limit long end_node_remaining_credits long start_node_remaining_credits My thoughts are something like this to make a faster traversal: If the traversal finds a incoming mutual_credit-relation it could check property end_node_remaining_credits to decide if it is enough for the transaction. And if the traversal finds a outgoing mutual_credit-relation it could check property start_node_remaining_credits to decide if it is enough for the transaction. Exactly. The direction would multiplex to two properties. That being said, it is OK to have two relationships as well. Since all modifications are in a transactional context, it will always be consistent. It will however require you to find two relationships instead of one, which, depending on how you implement it, may or may not require more time. David ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user -- David Montag david.mon...@neotechnology.com Neo Technology, www.neotechnology.com Cell: 650.556.4411 Skype: ddmontag ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
