×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Graph Routing Question

Graph Routing Question

Graph Routing Question

(OP)
Hi guys. I'm currently doing a module on programming languages. I have an assignment which requires graph traversal, finding out the 3 shortest paths from one train station to another. There're interchanges for changing of train lines.

The station diagram is depicted here: http://www.smrt.com.sg/trains/images/MRT_SysMp_with_all_CCL-Sept11_big.jpg

I have come up with an adjacency list of stations, without definition whether it's an interchange or not. As for progressing from there, I'm dumbfounded by how this language works. Could anyone lead me in the correct direction as to solve this problem?

User input: beginning station AND end station
Program output: shortest path 1, shortest path 2, shortest path 3

The paths require printing of each station's name throughout the whole path.

These are the lines of arcs I have come up with in an adjacency-list manner.

Thanks a million! :D

arcs(jookoon,[pioneer]).
arcs(pioneer,[jookoon,boonlay]).
arcs(boonlay,[pioneer,lakeside]).
arcs(lakeside,[boonlay,chinesegarden]).
arcs(chinesegarden,[lakeside,jurongeast]).
arcs(jurongeast,[chinesegarden,clementi,bukitbatok]).
arcs(clementi,[jurongeast,dover]).
arcs(dover,[clementi,buonavista]).
arcs(buonavista,[dover,commonwealth]).
arcs(commonwealth,[buonavista,queenstown]).
arcs(queenstown,[commonwealth,redhill]).
arcs(redhill,[queenstown,tiongbahru]).
arcs(tiongbahru,[redhill,outrampark]).
arcs(outrampark,[tiongbahru,tanjongpagar,harbourfront,chinatown]).
arcs(tanjongpagar,[outrampark,rafflesplace]).
arcs(rafflesplace,[tanjongpagar,cityhall,marinabay]).
arcs(cityhall,[rafflesplace,dhobyghaut,bugis]).
arcs(bugis,[cityhall,lavender]).
arcs(lavender,[bugis,kallang]).
arcs(kallang,[lavender,aljunied]).
arcs(aljunied,[kallang,payalebar]).
arcs(payalebar,[aljunied,eunos,dakota,macpherson]).
arcs(eunos,[payalebar,kembangan]).
arcs(kembangan,[eunos,bedok]).
arcs(bedok,[kembangan,tanahmerah]).
arcs(tanahmerah,[bedok,simei,expo]).
arcs(simei,[tanahmerah,tampines]).
arcs(tampines,[simei,pasirris]).
arcs(pasirris,[tampines]).
arcs(expo,[tanahmerah,changiairport]).
arcs(changiairport,[expo]).
arcs(bukitbatok,[jurongeast,bukitgombak]).
arcs(bukitgombak,[bukitbatok,choachukang]).
arcs(choachukang,[bukitgombak,yewtee]).
arcs(yewtee,[choachukang,kranji]).
arcs(kranji,[yewtee,marsiling]).
arcs(marsiling,[kranji,woodlands]).
arcs(woodlands,[marsiling,admiralty]).
arcs(admiralty,[woodlands,sembawang]).
arcs(sembawang,[admiralty,yishun]).
arcs(yishun,[sembawang,khatib]).
arcs(khatib,[yishun,yiochukang]).
arcs(yiochukang,[khatib,angmokio]).
arcs(angmokio,[yiochukang,bishan]).
arcs(bishan,[angmokio,braddell,marymount,lorongchuan]).
arcs(braddell,[bishan,toapayoh]).
arcs(toapayoh,[braddell,novena]).
arcs(novena,[toapayoh,newton]).
arcs(newton,[novena,orchard]).
arcs(orchard,[newton,somerset]).
arcs(somerset,[orchard,dhobyghaut]).
arcs(dhobyghaut,[somerset,cityhall,clarkequay,littleindia,brasbasah]).
arcs(marinabay,[rafflesplace]).
arcs(harbourfront,[outrampark]).
arcs(chinatown,[outrampark,clarkequay]).
arcs(clarkequay,[dhobyghaut,chinatown]).
arcs(littleindia,[dhobyghaut,farrerpark]).
arcs(farrerpark,[littleindia,boonkeng]).
arcs(boonkeng,[farrerpark,potongpasir]).
arcs(potongpasir,[boonkeng,woodleigh]).
arcs(woodleigh,[potongpasir,serangoon]).
arcs(serangoon,[woodleigh,kovan,bartley,lorongchuan]).
arcs(kovan,[serangoon,hougang]).
arcs(hougang,[kovan,buangkok]).
arcs(buangkok,[hougang,sengkang]).
arcs(sengkang,[buangkok,punggol]).
arcs(punggol,[sengkang]).
arcs(marymount,[bishan]).
arcs(lorongchuan,[bishan,serangoon]).
arcs(bartley,[taiseng,serangoon]).
arcs(taiseng,[bartley,macpherson]).
arcs(macpherson,[taiseng,payalebar]).
arcs(dakota,[mountbatten,payalebar]).
arcs(mountbatten,[dakota,stadium]).
arcs(stadium,[mountbatten,nicollhighway]).
arcs(nicollhighway,[stadium,promenade]).
arcs(promenade,[nicollhighway,esplanade]).
arcs(esplanade,[promenade,brasbasah]).
arcs(brasbasah,[esplanade,dhobyghaut]).

RE: Graph Routing Question

Generally, a graph is described with nodes eg, not arcs(pioneer,[jookoon,boonlay]). but arc(pioneer, jookoon), and arc(pioneer, boonlay).
Now, searching in this forum, you should find the answer of your problem.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login


Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close