Re: a little nasty problem?

*To*: mathgroup at smc.vnet.net*Subject*: [mg108807] Re: a little nasty problem?*From*: David Bevan <david.bevan at pb.com>*Date*: Thu, 1 Apr 2010 06:00:51 -0500 (EST)

The Combinatorica functions MakeGraph[] and either TransitiveReduction[] or HasseDiagram[] may do what you require. Then you could use LayeredGraphPlot[]. David %^> > -----Original Message----- > From: dh [mailto:dh at metrohm.com] > Sent: 31 March 2010 12:22 > To: mathgroup at smc.vnet.net > Subject: [mg108791] Re: a little nasty problem? > > Hi Francisco, > I am not sure if I understood correctly. > 1) Create a chain by starting at the highest interval and take all > intervals that a lower than the preceding one. > 2) delete the found intevalls with the exception of the highest one. > 3) repeat until only the highest one remains > > This can be done e.g. by: > > int == {{"C", {0.5, 0.6}}, {"D", {0.1, 0.2}}, {"A", {0.8, > 0.9}}, {"B", {0.4, 0.6}}, {"F", {0.6, 0.65}}, {"G", {0, 0.7}}}; > alpha == int[[All, 1]]; > low == int[[All, 2, 1]];(*lower indices*) > high == int[[All, 2, 2]];(*upper indices*) > ord == Reverse@Ordering[low]; > res == {}; > While[Length[ord] > 1, > AppendTo[res, > FoldList[If[high[[#1]] >== high[[#2]], #2, #1] &, First@ord, Rest@ord] > ]; > ord == Prepend[Complement[ord, Union[Flatten@res]], First[ord]]; > ];(*create chains*) > res == res /. {x1___, x_, x_, x2___} -> {x1, x, > x2};(*remove duplicates*) > Map[alpha[[#]] &, res, {2}](*replace numbers by characters*) > > Daniel > > On 30.03.2010 12:00, Francisco Gutierrez wrote: > > Dear Mathgroup: > > Suppose I have a series of intervals, and I create an order relation. > E.g., x is a typical interval, x=={0.6,0.9}, and x>==y if x[[1]]>==y[[1]]= and > x[[2]]>==y[[2]]. > > If x[[1]]>==y[[1]] and x[[2]]<y[[2]], or viceversa, the intervals are > incomparable. > > This relation violates [weakly] transitivity. > > Now, I have a set of intervals, and I want to create the lattice that > this order relation generates (suppose the weak violation of transitivity > does not pop up).. > > For example,int== > {{C,{0.5,0.6}},{D,{0.1,0.2}},{A,{0.8,0.9}},{B,{0.4,0.6}},{F,{0.6,0.65}},{= G > ,{0,0.7}}} > > > > I would like my code to put A at the top, with two chains: {A,F,C,B, D} > and {A,G}. Of course, it ought to flag any antichain if it exists. > > Now, there are several ways to do this. But what I have been able to > cook up is TERRIBLY inefficient. With 10 intervals it works no more. Is > there an efficient code to make the job? I am trying to do something that > is unfeasible? > > > > Perhaps I am naively attacking a problem that has no solution. Or > perhaps I am naively suggesting an easy problem is solvable. Some help ou= t > there? > > Francisco > > > > > -- > > Daniel Huber > Metrohm Ltd. > Oberdorfstr. 68 > CH-9100 Herisau > Tel. +41 71 353 8585, Fax +41 71 353 8907 > E-Mail:<mailto:dh at metrohm.com> > Internet:<http://www.metrohm.com> > >