Model an undirected graph in Rails?

Question

Importing the language of graph databases, understand

1. nodes (represented by circles),
2. edges (represented by arrows), and
3. properties (metadata of nodes / edges)

The graphic (courtesy of wikipedia) describes a directed graph.

What's the best way to model an undirected graph in Rails?

That is to say, a graph where all edges are reciprocal (as in above graphic), and where the properties of each edge are the same regardless of direction (contrary to above graphic).

Let's assume a default Rails 3 setup using a sql store via ActiveRecord.

A double polymorphic association would create a directed graph, able to model the data described by the above image.

def Edge < ActiveRecord::Base
  belongs_to :head, polymorphic: true
  belongs_to :tail, polymorphic: true
end

class Node < ActiveRecord::Base
  has_many :from, as: :head
  has_many :to, as: :tail
end

class Group < ActiveRecord::Base
  # a Node of Type: Group
  has_many :from, as: :head
  has_many :to, as: :tail
end

Should one extend this model to manage inverse relationships, or is a better model available?

---

One element of an app may be a graph problem, but it does not mean the app is centered around the problem, that graph transversals must be performed on the data, nor that the dataset is larger than available memory.

Answer 1

In an undirected graph, the only thing you need to know, is whether a node is connected to another node. And there is no such thing as a direction.

Simple approach:

class Node
  has_many :connected_nodes
  has_many :nodes, :through => :connected_nodes
end

class ConnectedNode
  belongs_to :node
  belongs_to :connected_node, :class_name => 'Node'
end

This is also called an adjacency list: for each node we can easily get the list of adjacent (connected) nodes.

A possible problem with this approach: we store the connections twice. A is connected to B and B is connected to A.

So it seems better normalized to store each connection only once, and then we get really close to your original proposal.

class Connection
  belongs_to :node1, :class_name => 'Node'
  belongs_to :node2, :clasS_name => 'Node'
end

Only we do our very best to not impose any order or direction through the naming.

Retrieving the connected nodes is all the nodes connected to as node1 or as node2, hence effectively disregarding any possible direction.

In this case you also need to express a validation that a connection with (node1, node2) is unique, but that (node2, node1) is actually the same and cannot be inserted twice.

My personal choice would be to use the second schema, although maintaining the first solution might be quicker (see also this question).

I also found a very interesting article where the author explains how graphs can be stored in the database. Very profound, but more database centric.

Hope this helps.

Answer 2

Why not use Neo4J?

http://wiki.neo4j.org/content/Ruby

https://github.com/andreasronge/neo4j-rails-example

https://github.com/andreasronge/neo4j

Answer 3

Instead of using polymorphic associations, try using has_many, :through

class Group < ActiveRecord::Base
  has_many :memberships
  has_many :persons, :through => :memberships
end

class Membership < ActiveRecord::Base
  belongs_to :group
  belongs_to :person
end

class Person < ActiveRecord::Base
  has_many :memberships
  has_many :groups, :through => :memberships
end

You can store the properties of the edge int the Membership model.