QuickGraph design implementation question

Topics: algorithm, graph, serialization
May 12, 2010 at 12:58 PM

Hi,

Would someone be able to give a high level overview of the QuickGraph implementation and how it works in principle.  I've been having a look through the code, and as a new .NET developer I'm kind of having a hard time at the moment.  Some of the things re the design I had in mind are:

  •  events - there seems to be a lot of code around events - what's the driver for having events in the design?  It seems to make it complicated to understand.  Is it to allow algorithms to be highly paralleled when they run or something?
  • re the code below, what's the design concept here re the observers (which ties into events in Q1 no doubt), how does this design concept work & what are the benefits

 

            var dfs = new DepthFirstSearchAlgorithm<Node, Relationship<Node>>(graph);
            var observer = new VertexPredecessorRecorderObserver<Node, Relationship<Node>>();

            using (observer.Attach(dfs)) // attach, detach to dfs events
                dfs.Compute();

 

  • database persistence - unless I've missed something there is no database persistence?  Is there a reason for this? (e.g. is it because its generics based so it is difficult to write a data access layer without the concrete classes used?)
  • what do people normally do re persisting large graphs then? 

 

 

 

 

 

Coordinator
May 12, 2010 at 5:37 PM

- events:

Algorithms are usually composed of visitor who trigger events, and observers who listen to a subset of those events. Events allow to hook to a subset of the events and also to dispatch the events to multiple observers easily.

- observers:

The idea of observers comes from the Boost Graph Library. For example, the breath first search algorithm can be reused to solve different problems by using different observersers.

- db persistence:

No particular reason. Database schemas are usually highly application specific, so each user should simply write its own.

- large graph

QuickGraph was not designed to deal with extremely large graphs. You need to use io-efficient libraries such as STLXX to deal with those. Otherwise, try sticking to int as vertices and SEquatableEdge<int> in order to avoid bloating your heap.

May 13, 2010 at 12:06 AM

Hi pelikhan - just to clarify then.   So would be true to say that the reason the basis of the design isn't just a simpler set of methods that work on a simple structure based on Dictionary/Lists of Apex/Vertices is that it becomes more difficult to reuse some of the algorithms?  But then why for example couldn't the algorithms just be simple methods (with no events / observers) and supply the resultant list of hits, after which the client does what he specifically want to do with them after this?   So I guess I'm trying to understand what type of requirement pushed the design over the edge requiring events/observers etc

thanks

 

 

Coordinator
May 13, 2010 at 5:58 AM

> So would be true to say that the reason the basis of the design isn't just a simpler set of methods that work on a simple structure based on Dictionary/Lists of Apex/Vertices is that it becomes more difficult to reuse some of the algorithms? 

I'm not sure I get your sentence.

>  But then why for example couldn't the algorithms just be simple methods (with no events / observers) and supply the resultant list of hits, after which the client does what he specifically want to do with them after this? 

Look for the AlgorithmsExtensions. There are a number of helper methods that hide the complexity and provide simple methods to solve common problems.

May 13, 2010 at 6:41 AM

I guess I was trying to say that one could create a few classes that model a graph and write methods that walk-the-tree so to speak, without having to have events & observers as part of the design - so I'm trying to understand why the QuickGraph design does have events & observers as part of the design?

 

Coordinator
May 15, 2010 at 3:54 PM

You can read about the Boost Graph Library, it has more details about this kind of architecture.

May 15, 2010 at 10:56 PM

ok - thanks