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 [email protected] https://lists.neo4j.org/mailman/listinfo/user
