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
