CODEWITHSUNDEEP
c++algorithmdata-structures
harunB10
harunB10

Reputation: 5207

Traversing through all possible elements in the data structure

I'm stuck with algorithmic problem for several days and any help is appreciated here.

Let's say that I have some modules in my app which can call other modules (as submodules). Something like blocks in Matlab Simulink. Also modules could call each one forming a loop.

For the sake of simplicity I've made a schema how that could look like.

enter image description here

In admin panel administrator can activate or deactivate some of these modules. For activation it is quite easy. Only one chain must be checked. But for deactivation it is tricky. We cannot just deactivate it because it might be used by some other module(s). That's why all possible cases must be checked. Also all submodules of that one must be deactivated (and checked if used by other modules).

For example, let's say that I want to deactivate X (and it's submodules A-B-C-E)

X is inside D:

D - X

and inside:

Z - N

which calls

D - X

Also X calls the whole chain which should be deactivated:

X - A - B - C - E

So once again, this whole chain (X-A-B-C-E) has to be deactivated but we must check if X-A-B-C-E is used somewhere else first.

I work in C++ but any pseudocode would be helpful.

What I've tried so far is setting first X-A-B-C-E in a Map.. Then going for all chains and cancel the ones in my initial Map. The ones which are left are safe to deactivate. But it doesn't work.

Also tried to parse this as Linked lists... But also there I don't know where to start and how to go through all possible combinations.

Like I said, it's the tricky one and any tip is helpful.

Upvotes: 3

Views: 69

Answers (1)

Stack Exchange Broke The Law
Stack Exchange Broke The Law

Reputation: 58868

This would be the straightforward brute-force approach:

  1. Make a list of modules you are going to disable.
  2. Make a list of modules you have already looked at.
  3. Add X to the list of modules you're going to disable.
  4. Find a module you're going to disable that you haven't already looked at. Call it M.
  5. Add M to the list of modules you've already looked at.
  6. Identify the other modules that have to be disabled if M is disabled. Add all of them to the list of modules you are going to disable, unless they're already in the list.
  7. Repeat steps 4-6 until there are no modules you haven't looked at yet.

But note that two lists might not be the best data structure here. It is probably more efficient to have a boolean flag in each module indicating whether you've looked at it. I'm just illustrating the general idea, ignoring such details.

If this looks like a breadth-first search, that's because it is.

Upvotes: 1

Related Questions