Object dependency and QSort

Hi experts,
I'll try to explain my problem as simple as I can.

Imagine objects (each of them are complicated STRUCT objects) "A", "B" and "C".
Based on application's logic, object "B" depends on object "A" and object "C" depends on object "B".
I'd like to use QSort and custom sort function to sort these objects based on their dependency.
Of course, the expected result should be {"A"; "B"; "C"}.

And now the problem:
custom sort function used by QSort expects two arguments (compared objects) and should return one of the values {-1; 0; 1}. When comparing "A" and "B", or "B" and "C", I'm absolutely able to compare those two and decide the return value. However, there's no direct dependency between "A" and "C" and therefore I'm unable to decide which one of them is "greater". Of course, there is dependency (transitive dependency), but not direct dependency. Is this doable using QSort (and custom sort function) or any other existing sort algorithms?

Thanks many times...
Marcel
LVL 1
darkriserAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

peetmCommented:
So, where/how is the dependency stored?  For example, does an object encode its dependency information?  If so, you'll need to query deeper into each object in the comparison function.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
patrickrivaCommented:
Hi there, are you trying to use Qsort cause you have large numbers of recors? How many records are we talking about? hunderds, thousands, millions?

p
0
oleberCommented:
It'll be very difficult to sort your element with any normal algorithm, if you don't have a way of comparing all the objects.

Consider to use some dynamic programming, and calculate the transitivity.

Note: QSort performance depends allot of your starting data. There are some contexts where QSort is the fastest algorithm (almost ordered lists), but check if your are in this situation.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

darkriserAuthor Commented:
peetm: yes, this is the worst scenario - not to use any of the "known" algorithms and to do it by myself by going deeper into the dependencies.

patrickriva: yes, I have up to 500.000 objects that need to be sorted.

oleber: this is exactly my problem - that I can compare only objects with a direct dependency. Calculating the transitivity is my worst scenario. Therefore wanted to ask if there's any better solution.
0
patrickrivaCommented:
- where do you have the 500k items? list, db table?

- do you have an id o guid for each item?

- is there a risk of finding loops in the dependencies?    A -> B -> C -> A


0
oleberCommented:
The way in with you have the relation is important.

Please explain better the relation.

if you have for each element one that is bigger and one that is smaller, your work is simple. Find the smallest and iteret on the rest.

Please explain better the relations that you have.
0
patrickrivaCommented:

and also:

- how  are the relations between items stored?  (do you have parents/children collections on each object or are they in a table that uses id/guid as references?
0
darkriserAuthor Commented:
I'm using a dynamically created array of STRUCT objects. I was unable to achieve such a performance using other concept.

no IDs, no GUIDs, I have another array of pointers, each pointer points to a single object of the "main" array (some kind of table of contents:-). And my goal is to sort the array of pointers, not the array of structs itself.

no loop dependencies, of course. this would cause an infinite loop...
0
darkriserAuthor Commented:
ok, each element (struct object) has a parameter - pointer to an array of pointers, each of them referencing to predecessor objects.

Take my example from the top - B depends on A and C depends on B.
object B has a parameter - an array storing only 1 pointer - referencing object A.
similary, object C has a parameter - an array storing only 1 pointer - referencing object B.

of course, there are more complicated dependencies, but for illustration this should be enough...
0
oleberCommented:
So one can have multiple predecessors in your structure?

But at the end you will have a list with single predecessors?


0
darkriserAuthor Commented:
oleber: of course, each object can depend on any number of predecessors.
and my goal is to sort the objects based on their dependency.

imagine my objects as Excel cells with formulas, and the predecessors as other cells used in the formula. I need to "sort" the cells into an order, so that I can go through the sorted list and calculate each cell based on its formula and arguments (predecessors). Due to the right order I'll have to calculate each cell only once.
0
patrickrivaCommented:

I'll try to explain my idea of algorithm and leave to you the implementation

- build a support class like


itemInGraph (IIG)
      used = false
      item_pointer
      parents_list
      children_list

globals
      chain_master_item_list
      map_item_to_IIG

for each item I add it to the "graph" as follows
      
      create an IIG for I
      add I, IIG to map_item_to_IIG

      if I has no parent
            add IIG to the chain_master_item_list

      foreach parent pI of I
      {
            if map_item_to_itemInGraph not contains pI
            {
                  create an IIG for pI
                  add pI, IIG_of_pi to map_item_to_IIG
            }      

            add pI to parents_list of IIG
            add I to children_list of map_item_to_IIG[pI]
      }

      // build a similar foreach for children cI of I
      // if you have in your original data link to childrens



at this point you have a graph that reflects your relations
plus a list of chain_masters (i.e. items without parents)


to print out one valid sorting of the items you can go with

      foreach n in chain_master
            use_and_navigate_from(IIG)

      use_and_navigate_from(IIG)
      {
            if (IIG.has_no_parents || IIG.has_all_parents_used)
            {
                  print IIG -> item_id [pointer/index]
                  mark IIG as used = true
            }

            foreach children cIIG of IIG
            {
                  if cIIG.has_all_parents_used
                  {
                        use_and_navigate_from(cIIG)
                  }
                  else
                  {
                        pIIG = IIG.first_parent_not_used_of
                        use_and_navigate_from(pIIG)
                  }
            }      
      }
0
oleberCommented:
in your case, it's a bad idea to do a formal sorting, from the begging.

A simple way to do this is the count the predecessors.

you have a list that will have your sorted list.

1 You get one cell without predecessors, and add it in the list.
2 You go to all the child's and you decrease in one the number of parents.
3 you go again to the step 1 until find no more cell

The algorithm seems to be simple

0
itsmeandnobodyelseCommented:
Your problem can be mapped by a directed graph with no cycles. There is not really a fast way to get the nodes of such a graph sorted but if the complexity really is comparable with the nested algorithms of Excel cells, the graph may have many vertices but hardly is deep. If so, you could write a compare function which makes a deep search on the predecessor list of the left operand looking for the right operand. If it finds the right operand in any of the predecessor's lists it returns 1. If not it returns -1.  

If the dependency lists contain some kind of mathematical 'operands', a deep search will have only a relatively small number of dependicies on avarage and the lookup search should terminate quickly. Assuming the avarage amount of operands after full resolution is less than 10, you have at worst case (bubble sort with a reverse sorted array)  10 * 500k comparisions, which should last far less than a minute. Using a fast sort algorithm, I would guess it is a few seconds only.


Regards, Alex
0
JimFiveCommented:
You don't really need to sort the dependency graph.  To Calculate object B you just need to traverse it's dependency graph and calculate it's children.  So, I would consider:
1.  Create a dummy header object that has as it's dependency list All objects that are not dependent on other objects (Best to build your graph so this is already true.)
2.  Do a depth first traversal from the header and calculate everything.
3.  Assuming that multiple objects can be dependent on the same object, you can store the calculated value at each level so that you only need to perform the calculation once.
3a.  When an object updates, everything "above" it on the heirarchy needs to be recalculated.
--
JimFive
0
oleberCommented:
Does my algorithm works?

Seems to be ease if there is no cycles and seems to be MxN.

M the number elements to be sorted
N the average number of childes

0
roussoscCommented:
Do you know that every two objects are comparable?  It may be possible that the dependencies do not generate a well-ordering.  A partial ordering and a topological sort may be all you can achieve.
0
florin_ganeaCommented:
I will take the idea of paths in directed graphs, since it maps perfectly your problem.
If the assumption that the digraph does not have cycles is false, you're kinda doomed: your problem is exactly finding the Hamiltonian path, if there is one.
This problem is described in http://en.wikipedia.org/wiki/Hamiltonian_path_problem and it is, as complexity, NP-hard.
0
florin_ganeaCommented:
Therefore, find the poor vertex with no incoming edges and start a traditional backtracking for getting your path.
0
darkriserAuthor Commented:
Thanks to all of you. Your solutions seem to work perfectly, however I decided to use another approach. I created second array of pointers pointing to my objects (something like a topic of content). Each object was assigned a sequence_number (0,1,....,n-1). Then I simply go through my "index" array (pointers to objects) and compare the sequence_number of the current object and all its "children". Once child's sequence_number is higher than the current object's sequence_number, i swap their position and sequence_numbers, as well. Using this method I get a sorted list of objects, where all "children" of every object are "in front" of the object itself...

Thanks a lot again to all of you...
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.