VIsitor and decorator concepts

[GoogleCodeExporter]

According to "The generic graph component library" paper, the visitor and 
decorator concepts are used in creating generic iterators ("Lifting sequential 
graph algorithms for distributed-memory parallel computation").

Original issue reported on code.google.com by nunofari...@gmail.com on 15 Nov 2010 at 2:05

[GoogleCodeExporter]

Implementing these visitor and decorator concepts would greatly increase the 
versatility of the algorithms implemented with this library, like BFS and DFS, 
and more domain-specific algorithms like MST calculation with more "auxiliary" 
algorithms (like BFS, DFS, etc.)

Original comment by nunofari...@gmail.com on 15 Nov 2010 at 2:08

[GoogleCodeExporter]

An usage example of adding a decorator concept would be the possibility of 
using vertex colors to keep track of the visited nodes in a graph, like needed 
in the BFS algorithm.

Original comment by nunofari...@gmail.com on 15 Nov 2010 at 2:14

[GoogleCodeExporter]

Visitors and Decorators may become extremely handy if we need to implement any 
kind of algorithm, that traverses the graph in a BFS manner (for example) - 
obviously the algorithm will have its specific behavior, all that is needed is 
to have the correct implementation of the BFS algorithm (with the visitor 
actions in their right place) so that the user can write any algorithm in a BFS 
manner as an integral part of the intended algorithm, only by defining the 
actions in the Visitor interface. The basic idea is, an algorithm maybe used in 
a BFS manner by defining the specific node-actions for the algorithm.

Original comment by nunofari...@gmail.com on 16 Nov 2010 at 3:32

[GoogleCodeExporter]

For the visitor/decorator to work correctly the middle layer that links the 
"data-structures" layer to the "algorithms layer" must be solid, with all of 
the node-actions in the right place. For example, the BFS traversal (which will 
be in this middle layer) must be well defined in order to support as many 
abstract algorithms as possible, like MST calculation (some MST algorithms 
traverse the graph in a well known BFS or DFS manner), or simply node coloring.

For now, the visitor/decorator issue will be put in second plan - I think that 
I should consolidate the part of graph representations, and later I will focus 
on the algorithmic versatility of the library and probably study its impacts on 
memory efficiency over the graph implementations.

Original comment by nunofari...@gmail.com on 16 Nov 2010 at 3:39