Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have two client types, an "Observer"-type and a "Subject"-type. They're both associated with a hierarchy of groups.

The Observer will receive (calendar) data from the groups it is associated with throughout the different hierarchies. This data is calculated by combining data from 'parent' groups of the group trying to collect data (each group can have only one parent).

The Subject will be able to create the data (that the Observers will receive) in the groups they're associated with. When data is created in a group, all 'children' of the group will have the data as well, and they will be able to make their own version of a specific area of the data, but still linked to the original data created (in my specific implementation, the original data will contain time-period(s) and headline, while the subgroups specify the rest of the data for the receivers directly linked to their respective groups).

However, when the Subject creates data, it has to check if all affected Observers have any data that conflicts with this, which means a huge recursive function, as far as I can understand.

So I think this can be summed up to the fact that I need to be able to have a hierarchy that you can go up and down in, and some places be able to treat them as a whole (recursion, basically).

Also, I'm not just aiming at a solution that works. I'm hoping to find a solution that is relatively easy to understand (architecture-wise at least) and also flexible enough to be able to easily receive additional functionality in the future.

Is there a design pattern, or a good practice to go by, to solve this problem or similar hierarchy problems?

EDIT:

Here's the design I have: Class diagram with methods included. The "Group" class is the hierarchy

The "Phoenix"-class is named that way because I didn't think of an appropriate name yet.

But besides this I need to be able to hide specific activities for specific observers, even though they are attached to them through the groups.


A little Off-topic:

Personally, I feel that I should be able to chop this problem down to smaller problems, but it escapes me how. I think it's because it involves multiple recursive functionalities that aren't associated with each other and different client types that needs to get information in different ways. I can't really wrap my head around it. If anyone can guide me in a direction of how to become better at encapsulating hierarchy problems, I'd be very glad to receive that as well.

share|improve this question

migrated from stackoverflow.com Aug 22 '12 at 12:02

This question came from our site for professional and enthusiast programmers.

    
This sounds like a graph theory problem. So we have some digraph representing the hierarchy of groups. Each group is a vertex in the graph. What properties hold true? Is it true that there always exists a unique vertex n with an in-degree of 0 while every other vertex has an in-degree of at least 1? Is every vertex connected to n? Is the path to n unique? If you could list the properties of the data structure and abstract its operations to an interface -- a list of methods -- we (I) might be able to come up with an implementation of said data structure. –  Words Like Jared Aug 15 '12 at 22:06
    
Thank you for your response. There is multiple hierarchies of groups that aren't attached to each other, except through the Observers, but I don't think they're a part of the graph objects, they just have a link to vertices in them. Each group in a hierarchy can only have 1 parent, but 0..* children. How would you implement that in a graph? And only a hierarchy with 1 group in will have an in-degree of 0. For 2-group-hierarchies and larger they will all have an equal in- and out-degree of at least 1. I'll try list it's relevant methods in an hour, when I'm at work. –  Aske B. Aug 16 '12 at 6:08
    
So do the groups work just like subclassing in C#: You may subclass one base class, with the exception that there is a forest (i.e. disjoint trees)? Well if you connect all the pointers/references then implicitly you have a graph, already -- you don't need to do anything else. Thing is, though, if you want to efficiently do operations like "Are these two groups in the same hierarchy?" "What is the common ancestor for these two groups?" etc. you need the problem systematically analyzed to take advantage of all the things you know in advance about the structure. –  Words Like Jared Aug 16 '12 at 12:39
    
Now that I've seen your diagram, what's your question exactly - if it's about the design approach I can't really help you at this point since I'm new to the various design methodologies, myself. However if you're looking for efficient O(n) algorithms for a well-defined data structure I can work on that. I see you didn't put in any mutating methods on Group and the structure of the hierarchies. Am I to assume that these will be static? –  Words Like Jared Aug 16 '12 at 12:42
1  
@Malachi I didn't find an answer. Unfortunately I didn't have time to fully investigate it and had to move on to something else. I don't have time to look into it now either, but I'll make sure to check my notifications every once in a while - and if someone makes a good viable answer, then I'll accept it. –  Aske B. Jul 22 '13 at 11:29

3 Answers 3

Here's a simple "Group" implementation that allows you to navigate to the Root, and navigate that Root's tree as a collection.

public class Group
{
  public Group Parent
  public List<Group> Children

  public IEnumerable<Group> Parents()
  {
    Group result = this;
    while (result.Parent != null)
    {
      result = result.Parent;
      yield return result;
    }
  }
  public Group Root()
  {
    return Parents.LastOrDefault() ?? this;
  }


  public IEnumerable<Group> WalkTreeBreadthFirst(
  {
    //http://en.wikipedia.org/wiki/Breadth-first_search
    HashSet<Group> seenIt = new HashSet<Group>()
    Queue<Group> toVisit = new Queue<Group>();
    toVisit.Enqueue(this);

    while (toVisit.Any())
    {
      Group item = toVisit.Dequeue();
      if (!seenIt.Contains(item))
      {
        seenIt.Add(item);
        foreach (Group child in item.Children)
        {
          toVisit.Enqueue(child);
        }
        yield return item;
      }
    }
  }

  public static IEnumerable<Group> WalkTreeDepthFirst()
  {
    // http://en.wikipedia.org/wiki/Depth-first_search
    HashSet<Group> seenIt = new HashSet<Group>();
    Stack<Group> toVisit = new Stack<Group>();

    toVisit.Push(this);

    while (toVisit.Any())
    {
      Group item = toVisit.Pop();
      if (!seenIt.Contains(item))
      {
        seenIt.Add(item);
        foreach (Group child in item.Children.Reverse())
        {
          toVisit.Push(child);
        }
        yield return item;
      }
    }
  }
}

So - given a group, you can walk that Group's tree:

Group myGroup = GetGroup();
Group root = myGroup.Root;
foreach(Group inTree in root.WalkTreeBreadthFirst())
{
  //do something with inTree Group.
}

My hope in posting this, is that by showing how to navigate a tree (and dispelling the complexity thereof), you may be able to visualize about the operations you want to perform on the tree, and then revisit the patterns on your own to see what best applies.

share|improve this answer

With the limited view we have of the usage or implementation requirements of your system it's hard to get too specific. For example, things that would come into consideration might be:

  • is the system highly concurrent (lots of users)?
  • what is the read/write ratio of data access? (high read, low write is common)

As for patterns etc., I would worry less about what exact patterns crop up in your solution, and more about the design of the actual solution. I think knowledge of design patterns is useful, but not the be-all and end-all: to use a writer analogy, design patterns are more like a dictionary of commonly seen phrases, rather than a dictionary of sentences you must write an entire book from.

Your diagram looks generally ok to me.

There's one mechanism you've not mentioned and that is of having some sort of cache in your hierarchy. Obviously you must implement this with great care, but it could significantly improve the performance of your system. Here's a simple take on it (caveat emptor):

For each node in your hierarchy, store inherited data with the node. Do this lazily or pro-actively, that's up to you. When an update is made the hierarchy, you can either regenerate the cache data for all affected nodes there and then, or set 'dirty' flags in the appropriate places, and have the affected data lazily re-generated when necessary.

I have no idea how appropriate this is in your system, but may be worth considering.

Also, this question on S.O. may be relevant:

http://stackoverflow.com/questions/1567935/how-to-do-inheritance-modeling-in-relational-databases

share|improve this answer

I know this is Kind of Obvious but I am going to say it anyway, I think you should take a look at the Observer Pattern you mentioned that you have an Observer Type and what you have looks kind of like the Observer Pattern to me.

couple of links:

DoFactory

oodesign

check those out. otherwise I would just Code what you have in your Diagram and then use the Design Pattern to simplify if necessary. you already know what needs to happen and how the program is supposed to work. Write some Code and see if it still fits.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.