in reply to OT(ish) - Best Search Algorithm

For my deeper understanding, is this definition of circle valid?

A "circle of friends" is a set of (site) members where each member has exactly two "friendship" relations in the whole set

I think this definition fits your description, but I'm not sure. My mental image is of a circle of persons, each holding hands - is that the right image?

Solutions for that could be any of the "circle detection" algorithms for graphs, but I don't know how how efficient they are. I'm not sure where A* comes into play as I see no sensible metric on which to optimize...

Replies are listed 'Best First'.
Re^2: OT(ish) - Best Search Algorithm
by Melly (Chaplain) on Oct 15, 2007 at 09:25 UTC

    A "circle of friends" is a set of (site) members where each member has exactly two "friendship" relations in the whole set

    Hmm, I think so - each member can have many "friendships", but the answer will only have two "friendships" per person in the solution (i.e. superfluous friendships will be ignored).

    I think this definition fits your description, but I'm not sure. My mental image is of a circle of persons, each holding hands - is that the right image?

    Yes, but with some constraints - the first friend in the pathway must not be known to the last friend in the pathway (i.e. I know both of them, but they don't know each other).

    map{$a=1-$_/10;map{$d=$a;$e=$b=$_/20-2;map{($d,$e)=(2*$d*$e+$a,$e**2 -$d**2+$b);$c=$d**2+$e**2>4?$d=8:_}1..50;print$c}0..59;print$/}0..20
    Tom Melly, pm@tomandlu.co.uk
Re^2: OT(ish) - Best Search Algorithm
by bart (Canon) on Oct 15, 2007 at 10:57 UTC
    I don't think that'll work. People can have more friends than just two. They can even share more friends than 2.

    For example, A is befriended with B, which is befriended with C and E, where C is befriended with D, and D befriended with A (the original circle), but E is also befriended with F which in turn is befriended with A.

    So there's 2 circles of friends, and A and B are in both: A-B-C-D-A and A-B-E-F-A.

      Your example still fits with my (tentative) definition. For both circles, it is true that each member has exactly two friendship relations in it. My definition does not say anything about the number of overall friendship relations on the whole site, but only about friendship relations within a circle.

      But I think I need a second thing in the definition, but I'm not sure which one is "better":

      • A "circle of friends" must have at least three members
      • There must be at least one person for every member of the circle without a direct "friend" relation

      The two are not equivalent, because the first rule allows circles of three persons, while the latter allows circles starting at four members.