Those of us who have been around the programming community will have already used the composite design pattern to model hierarchies.
Some of you will also know that a tree is an acyclic directed graph.
So here's the challenge: come up with a design pattern that can implement a part hierarchy, and/or a general graph (with or without cycles - so tree's can be modelled as well) The design pattern should be based on abstract classes (aka interfaces) You can't use a composite pattern because the connections between the vertices can (potentially) be weighted (unlike a tree) A primer on graphs can be found here (which also contains excellent pointers to reference material for procedural representation)
This is an area which can easily be modelled using procedural programming, but becomes harder when the programming model restricts the uses of cycles. (ie OO vs procedural)
Is it just an academic exercise? No! Neural nets, for example, are an implementation of a digraph.
We can all declare an interface which implements a class that encapulates an adjacency matrix and publishes methods against the adjacency matrix - but then that's not a design pattern.
One last criterium . . . it needs to be fast.
(and I'm not at college and this isn't my homework)
Reply With Quote