Re: Help needed: Is Quick-Union-Find the right solution to this problem ?

On Mon, 11 Apr 2005 10:18:25 -0400 (EDT), "Arthur J. O'Dwyer"
<ajo@xxxxxxxxxxxxxxxxxxxxx> wrote:

>
>On Mon, 11 Apr 2005 aredo3604gif@xxxxxxxxx wrote:
>>
>> On Sun, 10 Apr 2005 19:46:32 GMT, aredo3604gif@xxxxxxxxx wrote:
>>> The user can dynamically enter and change the rule connection between
>>> objects. The rule is a "<" and so given two objects:
>>> a < b simply means that b < a can't be set, also it must be a != b.
>>> And with three objects a < b , b < c means a < c
>[...]
>>> As far as I check on the array or given list of objects from user
>>> input that it's never added anything like a = b nor b<a when a<b it's
>>> already in the list, would it work as expected so that I know which
>>> objects in the list are "the strongest" ones as per user given rules ?
>
> Note that this "checking" part is non-trivial. You'll also have to check
>that the user didn't enter a<b, b<c, c<a; and b<c, c<d, d<e, e<b; and so
>on. That's a solved problem (checking for cycles in a directed graph using
>depth-first search), but it is an O(n) algorithm. Your user won't like
>that, if he's adding a lot of constraints at once; adding n constraints
>one at a time will give O(n^2) performance, and that's Bad. Luckily, you
>don't need to do it that way.
>
>> After a bit of searching I think that I should use DAG and Topological
>> Sorting, right ?
>
> I doubt it. Topological sorting, as I understand it, just tells you a
>valid topological order for the data; e.g., the constraints a<b, c<b might
>yield either a,c,b or c,a,b as orders, and neither of those orders tells
>you what you want to know --- namely, that you can't deduce anything about
>the relationship between a and c.
>
> What you want is a "transitive closure" of the graph. If the user adds
>an edge a<b, then you have to take all the existing edges b<c, b<d, b<e,
>et cetera, and all the existing edges w<a, x<a, y<a, z<a, et cetera, and
>add the new edges w<c, w<d, w<e, x<c, x<d, x<e, y<c, y<d, y<e,...
> Then, if and only if you never get a loop (a<a) in the graph, it will
>be consistent. And if you want to find out the relationship between a
>and b, you just look at the edges a<b, b<a. At most one of them exists
>(because if they both existed, so would a<a, b<b, and that would be
>detectable).
>
> There are faster ways to deal with building the transitive closure of
>a graph, but I'm not going to explain them here. Someone else might; or
>(better) you could look them up and post here when you know how you're
>going to solve the problem.
>
>HTH,
>-Arthur


Thanks for your answer.
I did a bit of research and studied two approaches to Warshall
algorithm with complexity O(n^3) and O(n^3/c) as per the explanations
I found so far.

The use of an adjacency matrix seems the best way to go but my only
concern is the fact that in plain old ANSI C I got to use I'm going
have quite some troubles allocating memory dynamically to ensure
proper expansion of the matrix itself.
Anyway, the user can set the rules but can't destroy them so I never
have to shrink matrix size, just address a matrix that matches the
number of different elements inputted by the user to set the rules,
which is pretty easy to accomplish or I might have an array of strings
or an array of char structs to solve the issue.
I surely got to mantain 2 copies of the matrix if I understood
Warshall correctly to have all of this working for what I got to do,
right ?
The adjacency matrix must be mantained and updated according to user
input and nothing else.
Then I make a copy of the matrix and pass it to the Warshall algorithm
function. The function will update the copy to return the transitive
closure matrix, right ?
Then the next time the user sends a rule I simple check the transtive
closure matrix ?
But I think I am still missing something here.. how can I ensure that
the user won't set a rule like item1 < item2 if item2 < item1 by
checking the transitive closure matrix when such condition is given by
any transitive elements in between making one item lower than another
?
I am still a bit confused maybe, although I understood that this is
the way to go to solve the problem efficiently.

.

Relevant Pages

  • Re: Chart Performance Problem with Large Data Set
    ... How does this affect the execution time? ... The next thing I saw in your code is that you are using a Workbook to ... supply your graph with data. ... Since your data is in an array already, why don't you just use the array ...
    (microsoft.public.office.developer.web.components)
  • Re: named array range- having a brain meltdown
    ... > So I need to create a named range, within which is an array formula ... > without ever putting them in worksheet cells. ... > then be added to an existing graph as a new series. ...
    (microsoft.public.excel.misc)
  • Re: Absolute beginner vs. fuzzy logic
    ... into B) is readily available in MatLab. ... new +1-dimensional array. ... The graph showed how a certain mechanical system ... > each iteration. ...
    (comp.soft-sys.matlab)
  • Re: Can this be done in SQL? Find the transitive relation
    ... I am strugling get the following done in SQL. ... http://www.bookpool.com/sm/0977671542, section on transitive closure ... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ...
    (comp.databases.oracle.server)
  • Re: How to plot Double values graph with MSChART
    ... "The MSChart control provides a ChartData property for loading data ... directly from an array into the data grid. ... 'Set the column labels. ... Code for Drawing Graph ...
    (microsoft.public.vb.general.discussion)