How do we do Graph representation in Ruby

1.3k views Asked by At

The real question is how to represent a graph data structure in ruby (some example code might help me understand).

I currently have an idea to represent a graph. that is every Node has an array of neighbourNodes which are object_id of node objects. Is there any better solution? Can i achieve this with some library easily. I have looked at GRATR and RGL. both are outdated (atleast i think so.) Anyway any working example on tuby 2.0.0 will help me a lot.

I have Busstops which compose Routes. Routesis a sequence of Busstops. How would I represent the graph for all the Routes. I want to use Dijkstra's Algorith to find a shortest path between two busstops (which may or may not lie on the same Route. Which means you have to change a bus on the way)).

3

There are 3 answers

0
Sam On BEST ANSWER

As mentioned in the comments, since you do not want to use a new data store such as Neo4j, the best option is using PostGIS and pgRouting. They are relatively easy to implement as they use SQL and are extensions for PostgreSQL.

9
Richard Peck On

This question is really vague, so you should expect to receive vague answers. Here's mine:


It's All Data

When you're looking to do something visually, it all starts with data

Your busstops have routes -- this means nothing to Rails or your graphing system. What will mean something is numbers & data; specifically geolocational data (for the bus stops & other geolocational data)

We've never done anything with maps or routes; so I don't know how you'd plot a route, and find the nearest bus stop. I do know, however, that in order to get that working, you'll definitely need to pull the correct data from your database


How I'd Approach It

I'd start by getting all the data you'll need stored in the database:

  • Each bus stop needs a location (long & lat value)
  • Each bus stop's route needs to be mapped out (perhaps with sequential waypoints of locational data)
  • You need a "reference" point (long & lat value to gauge against)

Once you have all these values in place, you'll then be able to get some sort of process sorted to show the data on the graph

0
Saad Masood On

Since i asked a graph representation in ruby.i came up with this idea that every Node is connected to some other Nodes called Edges. In ruby I create a Node Object and then push other Node'sobject_ids to thisNode.

newNode.neighbours << otherNode.object_id

There might me other ways. But this came to my mind. Please do tell me if there is a better way to do this.

For now this is what im using.