Constructing a huge graph

*To*: mathgroup at smc.vnet.net*Subject*: [mg122090] Constructing a huge graph*From*: Martin <mfpublic at gmail.com>*Date*: Thu, 13 Oct 2011 03:47:53 -0400 (EDT)*Delivered-to*: l-mathgroup@mail-archive0.wolfram.com

Hi I am currently trying to construct a very large weighted graph but I find myself in huge troubles :-). I simply lack the experience in Mathematica to figure out how to get around the issue below. The data: I have a large number of points, more specifically > 15 000 pairs of integer coordinates (x, y) in a list. The aim: Construct a weighted (undirected) graph with an edge between any two points (so the total number of edges is more than Binomial[15 000, 2] -- quite a lot). The point is that I want to find a shortest path between two specific vertices. The code: I have written looks like this: GraphDistance[ (Graph[ #1, (* the edges *) EdgeWeight -> First[#2]] &) @@ Reap[ (Module[{}, Sow[weight @@ #]; (* compute weight *) UndirectedEdge @@ # (* make edge *) ] &) /@ Subsets[coords,{2}], startP, targetP, Method --> "Dijkstra" (* weights are >= 0 *) ] The problem: The code is sooo slow - even for 5000 points :-), and Mathematica (for Students) aborts the computation because of "insufficient memory" already when I have 10000 points. Help: I have tried to look through a number of ressources on the internet but I have to admit that all the different pieces of advice on how to construct efficient code is a bit overwhelming for me as an inexperienced Mathematica programmer. I believe that it should be possible to get a reasonably efficient code for the above problem, but I do not know how to accomplish that. My own thoughts: First of all, the Subsets function constructs a huge list, and afterwards I use Map, to get two lists that are used for the Graph object - I believe this is where the problem is. I guess that, if I could produce my own subsets function where I would be able to compute the weight directly on each pair of points (x,y), and then put it directly in a SparseArray, could reduce both time, and memory consumption?? I hope that you can maybe point me in the right direction, or have any specific advice for my particular graph problem :-). Thanks in advance.

**Follow-Ups**:**Re: Constructing a huge graph***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Constructing a huge graph***From:*DrMajorBob <btreat1@austin.rr.com>

**Re: Constructing a huge graph***From:*Daniel Lichtblau <danl@wolfram.com>