Finally Got Past the 'Hello World' - Stage [Well Barely!!!!]

Got The Attached Script to Work that references an external .map file

ie Open/Close/Create a Query/Run it etc etc

Biggest Pain seems to be the Casting To get the Right Type......

J

Attachments:
Manifold.py

To err is human. To really foul things up requires a computer and a Very BIG Head

i ran that in pythonWin, and it totally worked! thanks!

Hey someone likes my newb python scripting attempt - One feels humble!!!

Actually the more I get into Python, the more I like it despite it's idiosyncrasies. - I think Mike made the comment that it is "downright irritating" at times but I think that is part and parcel of learning something that is so darned flexible

I Have been experimenting with Python.Net as opposed IronPython since I am looking at Python as more of a "glue" language for disparate systems- or a term I heard the other day - "Polyglot Programming"

I've been exploring a lot of libraries and hope to have some decent [sic] code up by the end of the week - okay I mean decent integrations between Manifold and Python Libraries - My comprehension of Python is still limited but I've stumbled upon some code that should add to the sum of Manifold rather than being a rehash of old stuff

Watch this space!!!!

J

To err is human. To really foul things up requires a computer and a Very BIG Head

Hi jonno - this is great. While you're "in the zone", it would be awesome if you could leave notes about the downloads and setup you go through for running python in different environments. Are you just using it in Manifold, or also from other consoles?

I've always got stymied at the full installation required for GDAL integration, and have long meant to check it out more deeply. You might be able to provide the kick start I and others need.

Cheers, Mike

cuda shuda wuda

I installed this

http://aspn.activestate.com/ASPN/Downloads/ActivePython/

and ran the examples from pythonWin. this installation seems to configure everything properly to run python scripts on windows-

Mike,Chris

You know what its like when you start something new - you need a meaty project to get your teeth into and accelarate the learning curve.

I haven't gone anywhere near GDAL - I'm afraid - far too complex. I was toying with the idea of some R but then I realised I would have to learn R first - bit of a downer - so I decided to stick to things that I vaguely knew about such as Public Transport Models and Graph Theory. Just re-read that and it sounds pompous as hell. I have to do Travel Time 'Isochrones' for both private and public transport and I have to use some god-awful systems to accomplish this - Accession GIS - see - http://forum.manifold.net/forum/t67047.3 - I do NOT know graph theory!!!

It's always been a bit of an ambition of mine to recreate the model in Manifold but routing esp Shortest Path Calculations were never upto the task so I gave up. However Python has renewed hope. So I've been doing a lot of work on SP.

Now, the best standard I've heard from this forum and personal experience in Scripting and UIScripting is 2 seconds per Calculation - which is not great!!! especially when transport modelling is concerned - which revolves around Origin/Destination Pair Calculations - so 500x 500 matrices or 125,000 bidirectional SP calculations - which is a reasonable request.

see:-

http://forum.manifold.net/forum/t71988.5

http://forum.manifold.net/forum/t37404.4

http://forum.manifold.net/forum/t51990.4

http://forum.manifold.net/forum/t44201.5

Now by my [Excel] calculations, it would take roughly 3 Days for Manifold to perform this calculation [ 125K * 2sec / (24 * 60 * 60) ] whereas Accession - the dog of a system that it is - could accomplish this in 10 minutes / 600 seconds

So my ultimate target is roughly the same as Accession - ie - 210 SP calculations a second

Which equates to a whopping 42,000 % improvement in performance!!!!

[CUDA - possible but lets let that one go for now and try and focus on scripting vs hardware/software improvements]

I was looking at Python as a potential Black Box application which could be run in a separate process to Manifold - so the basic idea was to approach it from a Graph(Nodes/Edges] perspective

My Process:-

Manifold

1) I have a Network Drawing that is made up of Line Objects

2) I do a Node Points Transform

3) I do a merge of identical Points using a Select UnionAll Query based Upon [X (I)],[Y (I)] values

4) I now have two Drawings in my file - 'Network' and 'Nodes'

Python

Script A [Graph Preparation/Representation]:-

1) Open Above .map File

2) Run SQL that identifies FromNodeID and ToNodeID from Network,Nodes Drawings [as well as Distance]

3) Make this bi-directional by copying 2) above

ie copy a,b,c to b,a,c

4) Create Python Dictionary of graph that takes the form:-

'3021':{'3026':4059.77597904121,'3025':4132.92644502657,'3028':935.207463614358,'3030':1291.26062435126,'3022':1488.94358523082}

which equate to all Nodes/distances around FromNode 3021

5) Use Python Pickle Library to save this Object to a file

http://www.python.org/doc/2.5.2/lib/module-pickle.html

Pickle's neat - you can save to file/read an object from file without having to recreate it programmatically

6) Graph saved To file - This takes a bit of time [depending on size on graph] but once done..............................

Script B [Calculations]

1) Load Map File

2) Generate 100 * 100 OD calculations from [Nodes] Drawing - potential 10,000 calculations

3) Create Results Table in .map

4) Create Comments to Hold Time Elapsed Data

5) If FromNode<>ToNode and SP calc has not already been performed [ ie A-B and B-A]

6) Perform dijkstra SP = FromNode - ToNode ( I found this code and verified it with Manifold)

7)From Results - FromNode,ToNode,Path eg 1,2, [1,3,7,9,2], Obtain cumulative distances to get Distance Result

8)Insert into Results Table, FromID,ToID,Distance,PathTaken [See Attached Image for Format]

I ran the above code for 3 map files - see the results below:-

See attached Excel Results Image

File Network Count Node Count SP Calculations Time Seconds Calc/Second RN.map 37082 33559 5086 807 6.302 RN1.map 5438 4804 5229 120 43.575 RN2.map 1743 1547 5263 37.5 140.3467

You learn something new each and every day!!!!

I never realised how linear the relationship was between graph size and speed of graph traversal/calculations

So everytime Adam was saying split it up - he was making a lot of sense!!!

By my calculations:-

A graph that is 21.27481354 times smaller (RN2 vs, RN) will run 22.27017878 quicker (practically linear anyway)

If my graph had a Network size of 1000, I think I would acheive my result of 210 SP calcs/sec!!!!

So my code works on small graphs but not large ones - they take more creative thinking though I STRONGLY believe that my code could be somewhat "optimized" by someone who knows what they are doing

Code will be uploaded when I am happy that others can use it - its pretty ugly in its present form and I have to find all the proper attributions for non-Manifold code. Manifold stuff - that blame lies squarely on my shoulders.

[Edit] Results Table did not paste so have saved image

Attachments:
Excel_Results.PNG
Results_Table.PNG

To err is human. To really foul things up requires a computer and a Very BIG Head

I am probably barking up completely the wrong tree as I understand very little of your post but, when I was attempting to perform very fast searches through a FNODE TNODE hydrological network, I found Manifold's script manipulation of RecordSets to be the weakest link. Would a binary search using a sorted array be applicable to your goal?

http://69.17.46.171/forum/t71484.8#71761

It seems to me the manifold forum community are a collection of people mostly in what could be described as the land management sector. One of the main reasons I still come to the forums is to glean the off-Manifold comments and suggestions as these give me insights into workflow processes that can help me in my profession. I wonder if the forums could have an 'off-topic' category added where topics that are only barely related to Manifold can be discussed. What would hold the off-topic category together is that most of the threads would be land management related or IT related and that might be a great thing for manifold. For example, jonno wants to do traffic analysis with Python or whatever, I want to be able to create xml based field data collection forms. If these topics could be shunted into the off topic forum, then other professionals who know nothing of Manifold and are not looking for it could blunder into the site, care of a search engine which has logged the off-topic discussions. For a product that depends on attracting attention to a web site, that could be a good thing?

Cheers.

Hi Dan,

This does look promising for Traffic Analysis. I still have to get my head around what you're actually acheiving in the file but it was certainly impressive whatever it did!!!! Might pick your brain later about it.

J

To err is human. To really foul things up requires a computer and a Very BIG Head

Jonno, The following link might throw some illumination on how the script works: http://en.wikipedia.org/wiki/Binary_search

Basically, it means when searching for FNODE/TNODE matches in a large tabular array (~59000) records in my case, the algorithm doesn't need to search through each record sequentially at each match iteration.

I didn't look deep, but I think that you should concentrate not on only selecting right tools (mani,phyton,etc.), but mainly on selecting right algorithm

Python Script A for Graph Creation

See Above Comments and test it on a small graph first

If everyone can get the code to work I'll post the SP Script which requires Script A

Jonathan

Attachments:
BuildGraph.py

To err is human. To really foul things up requires a computer and a Very BIG Head

Python Script B for SP Calculation

See Above Comments

J

Attachments:
ODPairs.py

To err is human. To really foul things up requires a computer and a Very BIG Head

Jonno,

These scripts are great!

However, the output appears to miss off some of the paths in my network - i.e. it doesn't calculate the path for every possible ij pair. I realise this is probably something to do with the algorithm, but some of my nodes don't feature in the "Results" table at all, even in the "Path Taken" column. Could this be a bug with my network or is the script a test about speed, rather than completeness? Wonder if it's something to do with the NumPoints parameter?

This is a very pertinent idea though, I was thinking about doing some work calculating shortest paths with Manifold and the Java JGraph T library, but Python seems like it would be easier to integrate.

I share your despair of Accession, although I have never used it I used to have colleages who used it and it certainly seemed to be a lumbering useless bit of software. And very expensive, as you point out.

Thanks for posting

Steve

It's probably my code! Have you tested/verified the SP calculation with Manifold at all?? If Manifold says it should work then it should! I have no problems with Manifold's accuracy - just it's speed.

Am doing some work on the scripts at the moment - chunking them up into smaller graphs for clculations on larger graphs/ One way attributes/Speed Columns etc - will hopefully post new code soon.

Glad someone found it useful!

Jonathan

To err is human. To really foul things up requires a computer and a Very BIG Head

don't undertstand what the aim because don't have the map project file

f = open(MyPicklePath, 'w')

for each in xrange(len(Edges)):

    MyFilter1(MyDict,each+1,Edges[each])

p=pickle.Pickler(f)

p.dump(MyDict) 

sorry -yes shortest path by script

Steve,

Mea Culpa:-

There was a Problem With The Query in BuildGraph.py script [It was based on start/End points but I did not take into consideration that lines could have multiple branches and Start/End Points only work where there is one branch]

I have attached a new version

I haven't tested yet but it should work

Attachments:
BuildGraph.py

To err is human. To really foul things up requires a computer and a Very BIG Head

Hi Jonno,

I've tested your new version but the Pickled file is still showing edges that don't exist. I think it's something to do with the MyFilter function. I've tried debugging it, but haven't got anywhere so far (I'm new to Python but suspect it's a general lack of logic that is hampering me!). From my untrained eye it appears that there is something wrong with the nested if statements and as a consequence spurious links are being created as the first "for" statement cycles through all the edges.

Steve

Steve,

How are you building your Nodes Drawing>>

I'm basically starting with a Network Drawing - applying a Nodes Transformation and then removing duplicates.

which should give me my Start Point, End Point of each Line [Though I could be wrong]

To err is human. To really foul things up requires a computer and a Very BIG Head

Yes that's what I'm doing. I don't think it's the SQL that was causing my problem, that may have been a separate issue. I hope I have now fixed my particular bug. The MyFilter sub was trying to add the details of the connected edge to the node, but the counter had moved on, so it was giving spurious results.

It's not pretty, maybe someone can improve this code, but replace line 58 in BuildGraph.py

from: MyDict[n]={b:c}

to : MyDict[n]={(f[0][1]):(f[0][2])}

Attachment below.

Attachments:
BuildGraph2.py