No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
app
config
db
doc
lib
log
public
script
spec
test
vendor
.gitignore
.rspec
.rvmrc
Gemfile
Gemfile.lock
README.mkd
Rakefile
config.ru

README.mkd

DAG (Directed Acyclic Graph) - Demo

This project demonstrates the implementation of a directed and acyclic graph structure. It is essentially an improvement over the encoding, queries and some technical issues as present in the act-as-dag gem.

Read the article Encoding and Querying Graphs in the Relational Model for more information.

Scalability

The inner workings of this implementation are such that it won't fall on your feet for large and even huge graphs. It essentially (unlike the act-as-dag gem) scales very well. I would recommend to replace some queries with CTEs, and use db-triggers for maximum performance on really huge networks. Read the article for a start.

Extending to General Graphs

The acyclic structure, and other graph properties are enforced by hooks in the app/model/arc.rb. The implementation is flexible and any of the constraints can be disabled at will:

before_save :prevent_back_loop
before_save :prevent_cycle
before_save :prevent_multi_arc
before_save :prevent_self_loop

Usage By Example

Node.create

Node.first.successors << Node.create

Node.first.successors

Node.first.graph_descendants

Node.last.graph_ancestors

Generator Tasks

There are a few generators to create graphs to explore or play with.

  1. rake generator:twostar N=10, creates two connected stars in a particular manner, see the corresponding figure in the article.

  2. rake generator:cycle N=3, tries to create a cycle, results in a chain if before_save :prevent_cycle is not disabled

  3. rake generator:er N=100 M=500, creates an Erdős–Rényi like random network

N is the target number of nodes, and likewise M the target number of arcs (if applicable). Defaults are in place.

Notation

The customary descendants and ancestors terms as used in graph theory clash with existing ruby methods. They are replaced by graph_descendants and graph_ancestors respectively.