Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

i'm a computer science student and a complete beginner in GIS and stuff. i'm trying create my own web-based multi-modal journey planner as my thesis. And as it is a thesis i cant use any ready-made routing engines like graphserver or opentripplanner, etc. though i can use third party applications for data convertions, like map data into sql or KML, etc. i've done some research and this what i've learned so far.

  1. that i can download map data from Open Street Maps (OSM) and convert them into sql like SQLlite or postreSQL for querying. (in RTree index structures)
  2. that i can also convert GTFS data into sql, again for querying.
  3. that i can link those two data sets through stops (those loading & unloading stations for each mode of transit).
  4. that i should convert those two data sets into a graph then link them in order to perform multi-modal routing. (i don't know if there are other solutions)
  5. that i can convert the resulting route into KML so i can overlay/display them on GOOGLE MAPS or other api's, for presentation. (forgot where i read this, but i know i read about this somewhere)

My question is how can i convert an osm database into a graph data .. how can i perform routing on those graph data .. this is where i got lost, i still dont know how can i perform routing algorithms from those given data sets as input/source. i tried reading the source code of graphserver, but it did no good to me.. besides it needs to be in linux system to work, and i'm currently working on windows .. i have few understanding on java .. but if i have to, i can learn it. if it what it takes so i can grasp the steps in performing routing. (as i see .. most of the routing engine are written in java)

share|improve this question
Is the purpose creating your own routing engine or getting all the bricks to fit together? If the first, why don't you just make up your own graph data, rather than spending time on GIS and converters, when you don't care about the actual results anyway? – Uffe Kousgaard Aug 27 '12 at 9:23
but would that be time consuming? .. and as i said, i'm a complete beginner in this stuff (GIS, spatial databases, etc) i only have like a year to finish this project, if gonna study those from scratch, i might not make it in time.. honestly i dont know how to create a graph data, i only picture them as an interconnected vertices just like in those illustrations you can find when they try to show how routing algorithms work, like dijkstra's. basically i dont know how to represent them in tables like in databases(if that's how they should even be represented) – Charles Jordan Cabero Aug 28 '12 at 2:52
so i decided to just study on how those released routing engine works and by that i mean how they handle or manipulate data from sources like OSM file, or postgreSQL and spatialLite tables/databases, etc. and as i read, they always like make their own sort of graph data from those sources then perform their routing algorithms on the generated graph. and thats where i got lost, i dont know how to create graph data or what are those graph data anyway(i mean are they like some kind of database tables or something?) and how can i actually perform routing algorithms from them? how do i access them? – Charles Jordan Cabero Aug 28 '12 at 3:02
i mean are they like multidimensional-arrays where i can access them by their index numbers and such, or database tables, where i just have to iterate in the rows see some relationships with other tables then perform some tasks. (these are only examples of known programming ways in accessing data, to performs tasks, to better explain what i'm trying to say) @UffeKousgaard – Charles Jordan Cabero Aug 28 '12 at 3:09
If you don't know what a graph is for routing, then you probably should go back and ask your teacher. Or pick an easier subject. – Uffe Kousgaard Aug 29 '12 at 14:06
show 1 more comment

4 Answers

up vote 1 down vote

SpatiaLite has routing support, and its probably a bit easier to understand than some of the "bigger" engines. See the docs. More searching, following links, reading the code and so on will help you to understand this, and given your stated needs, I won't provide step-by-step instructions here.

I understand that you don't want a canned solution, but I think you may benefit from looking at a simple working system.

share|improve this answer
i wish i could vote up your answer. but with my current reputation. i couldn't. anyway thanks a lot!. i think i know now what the data really looks like when they say "graph data". it was just another table of arcs with their nodes and computed cost column. (pls correct me if i'm wrong). i think with this i can proceed with my project now. i just have to work on connecting OSM and GTFS datas together, well i'm trying to reference my work with graphserver. thanks a lot again! – Charles Jordan Cabero Aug 29 '12 at 14:29
up vote 1 down vote

My question is how can i convert an osm database into a graph data .. how can i perform routing on those graph data .. this is where i got lost, i still dont know how can i perform routing algorithms from those given data sets as input/source.

This is the jist of your thesis, right? As in, you'll probably want to read a lot about routing and its algorithms, as well as everything implemented by OSRM, learn that (aka, do the work of your thesis), and then implement it.

share|improve this answer
i already done some research on different routing algorithm and i think i already found one that will be best for multi-modal transportation. i'm not trying to copy the routing algorithms those routing engines implements, what i'm just trying to figure out from them is how to they perform it, by that i mean, how do they access external sources like OSM, postgreSQL tables. etc. though as what i read, they convert them into their own graph data, then perform the routing on those graph data. now, how do they convert those external sources into graph, and what exactly are those graph anyway? – Charles Jordan Cabero Aug 28 '12 at 3:38
i mean, are they some kind of database table? ..or array or some memory addresses or what? .. and how exactly do they access those graph data to perform routing?.. do they like call them by as i said, sql queries if they are database tables, indexes if they are arrays, or pointer if they are like memory addresses?.. in short what are those GRAPH DATA's anyway? if i could just know what are they, maybe i can find out how to access them and perform some tasks.. – Charles Jordan Cabero Aug 28 '12 at 3:43
oh yeah.. i think you dont need to answer the questions on my two previous comments, co'z it think i know now what they mean when they say "graph data" . its just another database table/s of arcs with two nodes corresponding to its endpoints and cost(weight) as columns, of course their could be more, but those are the must (please correct me if i'm wrong). anyway thanks for your response. i think i could proceed now with my project. just gotta figure out how to link osm and gtfs data. since im working on multi-modal transit. i'm trying reference my work with graphserver. – Charles Jordan Cabero Aug 29 '12 at 14:54
@charles don't store your data into an sql db - better use a simple array of nodes pointing to its edges like I'm doing with GraphHopper (java) – Karussell Aug 30 '12 at 22:31
@Karussell i noticed that existing routing engine are usually coded in java, c, python, c# etc .. but no in PHP.. why so? .. i was planning in coding my routing engine in PHP ,, but would that be a very bad idea? .. why do you people use java ? – Charles Jordan Cabero Sep 20 '12 at 8:49
show 2 more comments
up vote 0 down vote

Try pgRouting. It is possible to use OSM data with this library, so you can check out how this make graphs from .osm files.

share|improve this answer
just one thing .. on the link you provided .. there is a part there that says "Advantages of the database routing approach" i want to highlight that "database routing approach" . so does that mean there are other kind of approach? i mean without using databases? .. i'm trying to reference my work with graphserver since its the closest routing engine that could help me since it does offer multi-modal routing. and i have the idea here that using database is the way to perform routing when it comes to GIS. am i wrong on my assumption here? – Charles Jordan Cabero Aug 29 '12 at 15:39
up vote 0 down vote

Regarding your question: "how can i convert an osm database into a graph data", you can also use osm2po. Among other things, it will create a postgreSQL input file from raw OSM. OSM road networks are not routable in the basic form: there are some junctions/intersections that need attention and the road speeds need to be determined from the given road attribute. osm2po does a good job with this. Once in the database, you would need to add your own spatial index on the "geom_way" column, and it could also be a good idea to index the clazz (road class) column so that you can extract principle roads between your source/target points and more local roads around the source and target.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.