query language for graph sets: data modeling question

Question

Hello.

Suppose I have a set of directed graphs. I need to query those graphs. I would like to get a feeling for my best choice for the graph modeling task. So far I have these options, but please don't hesitate to suggest others:

• Proprietary implementation (matrix) and graph traversal algorithms.

• RDBM and SQL option (too space consuming)

• RDF and SPARQL option (too slow)

What would you guys suggest? Regards.

EDIT: Just to answer Mad's questions:

• Each one is relatively small, no more than 200 vertices, 400 edges. However, there are hundreds of them.

• Frequency of querying: hard to say, it's an experimental system.

• Speed: not real time, but practical, say 4-5 seconds tops.

Answer 1

The first option you mentioned seems best. If your graph won't have many edges (|E|=O(|V|)) then you might earn better complexity of time and space using Dictionary:

var graph = new Dictionary<Vertex, HashSet<Vertex>>();

An interesting graph library is QuickGraph. Never used it but it seems promising :)

Answer 2

I wrote and designed quite a few graph algorithms for various programming contests and in production code. And I noticed that every time I need one, I have to develop it from scratch, assembling together concepts from graph theory (BFS, DFS, topological sorting etc).

Perhaps a lack of experience is a reason, but it seems to me that there's still no reasonable general-purpose query language to solve graph problems. Pick a couple of general-purpose graph libraries and solve your particular task in a programming (not query!) language. That will give you best performance and space consumption, but will also require understanding of graph theory basic concepts and of their limitations.

And the last one: do not use SQL for graphs.