LiveJournal Connect - How It Works
LiveJournal connect is deceptively simple in its operation. In fact, my current source code is less than 400 lines when comments and multi-line
prints are excluded. Here's a simple breakdown, searching from "A" to "B":
Let's look at three examples, run on 20 Feb 03:
- Validate user input. Make sure usernames fit the LJ criteria.
- If the second user name is a *, call random.bml on LJ to get a random user.
- Check "A" for a friends list.
- First, check database; if downloaded today, return that information.
- Second, go to LJ and get that information via a special interface.
- Cache the information in the database.
- If mutual friends option is checked, those friends are filtered here.
- Assuming friends are found, see if "B" is on "A"'s friends list. (Check 1-hop chain)
- Assuming no link, check "B" for a friend-of list via same mechanism.
- Assuming friend-of is found, check for common friend. (This finds 2-hop chains)
- At this point, if no link has been found, we need to start searching through friends. In the following discussion, a "side" is defined as the
chain of links either linking from "A" or to "B".
- Examine which side has fewer friends to search through. (In the case of the first time through, we're comparing how many friends "A" has
with how many people list "B" as a friend.)
- Concentrating on the side with the lower count, get the appropriate friends information. (If on "A"'s side, we check their friends; if on "B"'s
side, check their friend-of's.)
- See if each friend can be used in a link. This involves a simple hash structure:
- If coming from "A"'s side, make a hash key with the name of the friend and a hash value of the person who led to this friend.
- If coming from "B"'s side, make a hash key with the name of the friender and a hash value of the friend.
- If no link is found, update the side count (the count is equal to the number of friends that need to be checked on the next pass) and restart.
- Once a link is found, move backwards using the first hash and forwards with the second hash until the chain is displayed.
This produces the shortest chain, even if one side is continually lower, because any short-circuit is immediately obvious. We're always checking
every new person looked at to every other person ever looked at on the other side. I can't think of a single instance where this makes a chain any
longer than it possibly needs to be.
- sachmet to brad: First, LJC looks at my friends list (35); then brad's friend-of list (119), and sees jwz as a common friend. 2 hop chain.
- sachmet to lisa: My friends (35); then lisa's friend-of (185). My side being lower, starting with my friends, digging through to neenerface who
has paladin3 as a friend of lisa. 3 hop chain.
- sachmet to jibunnotameni: My friends (35); then jibunnotameni's friend-of (12). Their side being lower, their friend-ofs are checked (79). My
side now being lower, my friends are checked, and a mutual friend between my friends and their friend-ofs finds a 4 hop chain.