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