ArrayList of ArrayList (for Cycle Detection)

Question

Well this question is more about an efficient algorithm than the implementation, so I won't post code. (won't really help you to understand the question)

To introduce you to the question: I'm developing a program to calculate automovilistics crash reports. It offers you a serie of "equations" (Eq from now on, Eqs for plural), where you imput data and usually get n results.

e.g.: you select space covered (x), which and imput time (t), aceleration (a) and initial speed(v), then x = (a*t)+((a*t^2)/2). The thing is this Eqs are inside an object that contains a lot of things more than vars and the ecuation itself,lets call it Bo (the busssines object im talking about.

So the BO its pretty big (and needs to be), among other things it has, 1 Bo can have N Eqs, and more than one result, aditionally every Eq can take ranges of values as imput, which makes you get well... (lets pretend you just can use ranges on 2 variables, actually this is not restricted) so you will have a table of results for each result (some Bos have 4 diferent results). Te steps for the ranges are capped, to 20 first range,10 second range. (in a Bo with 4 results thatwould map on 800 results for 1 Bo).

Btw, I have to store (save in a file) this Bos with their respectives results, and Var imputs can't calculate them on runtime each time (I could just save the ecuations, and the var imputs and calculate the result each time i need them),because Bos can change ther ecuations, and the user needs to keep the previus results, don't ask..

Also, you can Import one of the results of Bo to an Eq imput of another Bo. So in the previous example(lets call it Bo1) aceleration could come from another Bo (Bo2) that calculates that, and takes other paramethers to calculate it, and if you change the imputs of Bo2, the result will change, so at least 1 var of Bo1 will change making Bo1's result change. This can cascade (B2 imports from B3 and so on). And one Bo can imports all its N variables from N others Bos.

I can't use pointers or Reference types (maybe could use ref types, anyway it would be a lot of work, have to work with previous saved data from diferent users, and object missing referencies,etc).

I decided to just use a collections of arrays, in each array is stored, {Id_of_Bo_Exporting, Id_Bo_importing,Id_Variable_of_Bo_Importing,..(ohters ids to map the especific result exporting)} Arrays are of int (long for the first 2).

I don't really like it but the code is working just fine. (Thanks for reading) question is comming son I promisse.

The problem is, I have to check for cirucular imports, if B3 imports from B2 and B2 impotrs from B1, I shouldnt allow an import of Bo1 from B3 (or B2). This would lead to an endless loop, (I can stop the loop but is not logic from the mathematical view to allow that import).

and the Import list, could be eventually really long,

I thougth of an ArrayList< ArrayList< long>> So each time I add an import i Add Ids on this "thing" i don't like. (the araylist of arraylist)

Each Array of long will have on the first position the "Bo id header", and each time that Bo imports, the new Id adds in its list, AND every other Bo importing the Bo (the one makin the import).

So if I user tries to make B9 from B1, the method will detect, B1 is getting added to its own list and wont allow.

the implementation its pretty easy. (lets use java, no I'm using .net, didn't start the proyect myself)

example {{}}

B1 imports from B2: {{B1,B2}}

B1 imports from B6: {{B1,B2,B6}}

B2 imports from B4: {{B1,B2,B6,B4},{B2,B4}}

B4 imports from B9: {{B1,B2,B3,B4,B9},{B2,B4,B9},{B4,B9}}

B3 imports from B10: {{B1,B2,B3,B4,B9,B10},{B2,B4,B9},{B4,B9},{B3,B10}}

Each Array of long will have on the first position the "Bo id header", and each time that Bo imports, the new Id adds in its list, AND every other Bo importing the Bo (the one makin the import).

So if I user tries to make B9 from B1, the method will detect, B1 is getting added to its own list and wont allow.

the implementation its pretty easy. (lets use java, no I'm using .net, didn't start the proyect myself)

private boolean checkCircularity(long ida,long idb){
//ida importing, idb exporting
// asume List is public and called iL
// Clone il to restore it in case}
for (int i = 0 ; i < iL.size() ;i++)  
    // Each arraylist of long in the big array iL
{    
    // I would use some kind of SetUniqueList, dont know in c#
    // but i could check it if needed and add it if it doesnt exist
    if (iL.get(i).contains(ida))
    {
        if (((iL.get(i)).get(0)) == idb)
        {// Circiut, breaks for's restore the original list and returns false
        }
        else{
            if (!iL.get(i).contains(idb)) {iL.get(i).add(idb);}
        }
    }
}       return true;    }

Now the question (taking off using a ListSet or whatever) can you think of a more efficient method to do this? Both list (imports and iL can get Big really fast depending on the user). Caption is in speed.

ArrayList of ArrayList (for Cycle Detection)

Answers (1)

Related Questions