Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #5620
| From | Martin <mfpublic@gmail.com> |
|---|---|
| Newsgroups | comp.soft-sys.math.mathematica |
| Subject | Constructing a huge graph |
| Date | 2011-10-13 07:50 +0000 |
| Organization | Steven M. Christensen and Associates, Inc and MathTensor, Inc. |
| Message-ID | <j76583$2bv$1@smc.vnet.net> (permalink) |
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.
Back to comp.soft-sys.math.mathematica | Previous | Next — Next in thread | Find similar | Unroll thread
Constructing a huge graph Martin <mfpublic@gmail.com> - 2011-10-13 07:50 +0000 Re: Constructing a huge graph Ray Koopman <koopman@sfu.ca> - 2011-10-15 10:04 +0000
csiph-web