4

I have implemented algorithm BFS(Breadth First Search) using a neighbors list ADT for scanning a graph and gathering information about it and answer questions.

I have function called BFS which implements the algorithm and i can answer questions(like: How many connected components the graph has ? Diameter of the graph ? and few more) by using the variables in the function.

For example, to find out how many connected components there are, i can print a variable int components (in the end of the function). To find out the diameter of the graph i'm using a int [] distances array and scanning it(in the end of the function) and getting the max value(precisely but not accurate), and so on.

My question is how can select/get the data from the function(and then i can wrap it within different functions)but still avoiding duplicate code ? is there a design pattern or different strategy for this type of problem ? solutions came in my mind:

  1. Print all the required data in the end - possible but ugly and none modular.
  2. Re-implement the function and every time return a different type of data(int, int[] etc) - code duplication.
  3. Return an object of all data, and then every different function will use it - overkill.

I can add some code if needed.

  • Maybe a Factory together with an Observer..? – solarflare May 8 at 3:13
  • I read over the internet how to combine both DP but i didn't understand. Can you further detail ? – DeSpeaker May 8 at 11:22
2

If your function has a lot of out-parameters and if most of the time you only need a subset, then your function does too many things and its “interface” should be simplified.

The usual way is functional decomposition / method extraction: break the large function down into smaller ones that do-one-thing-and-do-it-well. Each function would then only provide the parameters that are really relevant for its goals. If you need several different results you would call the relevant functions directly. So you’d consume only what you need.

However, for some problems, this technique is not feasible. It is when the same algorithm has to calculate the different results together in order not to redo complex calculations several time. The typical case is when one calculation is the by-product of another. In this case you should consider to implement your algorithm as a class, that could cache/store the different intermediary results or by-products.

A variant thereof would be to use the strategy pattern. It’s also about embedding algorithms into classes, but with interchangeability in mind. In this way you could have a class Searcher, and specify a more specialised search strategy to be used (e.g. BFSearch or DFSearch).

Finally, before choosing one of these approaches, you should think about the larger picture of your design: which of all your potential “queries” depend on a particular bfs execution ? and which results are independent of any search and are in fact graph properties (e.g. connected groups, diameters)? Because even if it is similar algorithms, it makes no sense to re-identify connected groups of the whole graph every time your're just interested in a quick search (unnecessary performance overhead).

So I'd recommend to isolate the queries about the general graph properties from the search results. For this you should structure the algorithm in a way to be able to reuse the common parts (either subfunction of classification). If performance is at stake, and if there’s an opportunity to avoid recalculating something, you can think of some form of caching (e.g. if and only if you have the graph diameter as by-product of a bfs, you could store this result for the graph, for later re-use, but otherwhise use a separate function that calculate it only when really needed).

  • First of all, Thanks for the replaying. I tried to consider functional decomposition but in relation to my problem, all products(helper variables) of the algorithm which helps to solve the queries is "ready to use" only after running the whole algorithm. Secondly, I considered some sort of caching strategy as you mentioned. I can run the algorithm once and then store all helper vars(like: components, diameter, distances, father) as class members and create different functions like: getDiameter(), getShortestPath(src, dest) and use the helper vars to implement them. – DeSpeaker May 8 at 10:58
  • @DeSpeaker That sounds much better than a big function with lots of parameters and that would recalculate the helpers every time. Of course, if the graph is changed, the cache must be invalidated. For thus you could think of registering your search class as an observer of the graph. – Christophe May 8 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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