Path Search Algorithm?

[Nimsical]

Problem's Context:
[highlight=java]
class Person {
public String name;
public LinkedList friends;

Person (String name)
{
this.name = name;
friends = new LinkedList();
}
}
[/highlight]


Problem

Implementing a "shortest path algorithm".
Between two Person classes, where each "friend" (Item in Person.friends) has friends. These friends consist of other Person classes, which also might or might not have other friends.

Personally, I've thought of three easy steps to at least find the first possible path (not the shortest):

1. Check for a common friend in the friends of each side. (From one side)
2. Increase depth and look for common friends. (Find common friends between friends of friends)
3. Switch sides

Although I have failed to implement any method that I've thought of, so please - do share.

For better understanding, you might wanna take a look at the whole implementation of the friend system:

Spoiler: Problem

[highlight=Java]
import java.util.LinkedList;

public class S3 extends WaterLooProblem {

static LinkedList people = new LinkedList();

public static void main (String[] args)
{
name = "Senior Problem 3: Degrees of Seperation";
header();

// Add initial people
people.add(new Person ("Abby"));
people.add(new Person ("Zoey"));
people.add(new Person ("Alberto"));
people.add(new Person ("Natalie"));
people.add(new Person ("George"));
people.add(new Person ("Ali"));
people.add(new Person ("Kara"));
people.add(new Person ("Ricardo"));
people.add(new Person ("Jeff"));
people.add(new Person ("Stephen"));
people.add(new Person ("Bruce"));
people.add(new Person ("Chris"));
people.add(new Person ("Terry"));
people.add(new Person ("Kim"));
people.add(new Person ("Trevor"));
people.add(new Person ("Richard"));
people.add(new Person ("Siobahn"));
people.add(new Person ("Normar"));

// BeFriend everyone initially
processCommand('i', "Abby", "Bruce");
processCommand('i', "Abby", "Chris");
processCommand('i', "Abby", "George");
processCommand('i', "Abby", "Natalie");
processCommand('i', "Abby", "Stephen");
processCommand('i', "Abby", "Zoey");

processCommand('i', "Zoey", "Stephen");
processCommand('i', "Zoey", "Alberto");
processCommand('i', "Zoey", "Natalie");

processCommand('i', "Alberto", "Jeff");

processCommand('i', "Jeff", "Ricardo");
processCommand('i', "Jeff", "Terry");

processCommand('i', "Ricardo", "Siobahn");
processCommand('i', "Ricardo", "Kara");

processCommand('i', "Siobahn", "Nomar");

processCommand('i', "Kim", "Trevor");
processCommand('i', "Kim", "Richard");

processCommand('i', "Trevor", "Richard");

processCommand('i', "Normar", "Kara");

processCommand('i', "Ali", "Kara");
processCommand('i', "Ali", "George");

for(;
processLine(readLine());
}
static void processLine(String line)
{
String[] args = line.split(" ");
if (args.length == 3)
processCommand(args[0].charAt(0), args[1], args[2]);
else if (args.length == 2)
processCommand(args[0].charAt(0), args[1], null);
else if (args.length == 1)
processCommand(args[0].charAt(0), null, null);
}

static void processCommand(char cmd, String arg0, String arg1)
{
boolean res = false;
switch (cmd)
{
case 'i':
// arg0 == person
// arg1 == new friend
res = findPersonByName(arg0).beFriend(findPersonByName(arg1));
printf( (res) ? "They are now friends! [ " + arg0 + " -> " + arg1 + "]\n" : "They're already friends? Did nothing.\n");
if (res)
processCommand('i', arg1, arg0);
break;
case 'd':
// arg0 == person
// arg1 == friend
res = findPersonByName(arg0).deFriend(findPersonByName(arg1));
printf( (res) ? "They are no longer friends! [ " + arg0 + " -> " + arg1 + "]\n" : "They're not friends? Did nothing.\n");
if (res)
processCommand('i', arg1, arg0);
break;
case 'n':
// arg0 == person
Person per = findPersonByName(arg0);
if (per != null)
printf(arg0 + " has " + per.friends.size() + " friend(s)!\n");
else
printf(arg0 + " was not found!\n");
case 'f':
// arg0 == person
printf(arg0 + " has " + findPersonByName(arg0).calculateFriendsOfFriends() + " friends of friends!\n");
break;
case 's':
// arg0 == person
// arg1 == friend
printf("Shortest path is: " + shortestPath(findPersonByName(arg0), findPersonByName(arg1)));
break;
case 'q':
printf("GoodBye!\n");
System.exit(0);
break;
}
}

static Person findPersonByName(String name)
{
Object [] peepz = people.toArray();
for (int i = 0; i < peepz.length; i++)
{
if (((Person)peepz).name.equals(name))
return (Person) peepz;
}
return null;
}

static Person findPersonByName(LinkedList friends, String name)
{
Object[] peepz = friends.toArray();
for (int i = 0; i < peepz.length; i++)
{
if (((Person)peepz).name.equals(name))
return (Person) peepz;
}
return null;
}

// FIXME: ShortestPath
static int shortestPath (Person p1, Person p2)
{

return -1;
}

static boolean areFriends(LinkedList friends, Person per)
{
return (friends.indexOf(per) == -1) ? false : true;
}
}


class Person {
public String name;
public LinkedList friends;

Person (String name)
{
this.name = name;
friends = new LinkedList();
}

boolean beFriend (Person per)
{
if (per != null && friends.indexOf(per) == -1)
{
friends.add(per);
return true;
}
return false; // we did nothing
}

boolean deFriend (Person per)
{
if (per != null && friends.indexOf(per) != -1)
{
friends.remove(per);
return true;
}
return false;
}

int calculateFriendsOfFriends()
{
int count = 0;
for (int i = 0; i < friends.size(); i++)
count += ((Person) friends.get(i)).friends.size();
return count;
}

static void printf(String arg)
{
System.out.print(arg);
}

}
[/highlight]

 

[A_Nub]

NVM DISREGARD THE FOLLOWING IT IS COMPLETELY WORNG and Only goes 2 deep.

assume each Persons linked list of friends is sorted
all persons must be friend them selves[HIGHLIGHT=java]
Person toFind = personByName(name)

Person common = this;

while(common != this || common != toFind) commonFriend(common,toFind);

Person commonFriend(Person a, Person b){//find a common friend
for(i = 0; i < a.list.len || b.list.len; i++){//all a's friends or all a's friend (whatever comes first)
if(a.list == b.list){//common friend
return a.list;
}else{
return NULL;
}
}

[/HIGHLIGHT]

 

[yaustar]

My inclination first is to brute force it. Any optimisation on the search would most likely involve storing the data differently and/or additional metadata.

If you are going to transverse the graph, then you have to stop it backtracking on itself. i.e. A is friends with B and C, B is friends with A and C, C is friends with B and A. Now you have a circular graph where it is possible to end up where you started.

 

[Moca]

Here's a solution to find the distance in F# I wrote yesterday (From what I understood, this is what you asked for). It's not as elegant or fast as it could be, but it does the job. Have fun deciphering it, perl man.

type Person(name:string) = class
  let _Name = name
  let mutable _Friends = List.empty<Person>
  member p.Name    with get() = _Name
  member p.Friends with get() = _Friends and set(x) = _Friends <- x
  member p.Befriend(person:Person) = 
    match person with
    | _ when person.Name = p.Name -> ()
    | _ when not(List.exists (fun (x:Person) -> x.Name = person.Name) p.Friends) ->
        p.Friends <- p.Friends @ [person]
    | _ -> ()
  member p.Defriend(person:Person) = 
    p.Friends <- (List.filter (fun (x:Person) -> x.Name <> person.Name) p.Friends)

end

let FindPersonByName name (list:List<Person>) = 
  let rec findPerson count = 
    if count >= list.Length then null
    if (list.Item(count)).Name = name then (list.Item(count))
    else findPerson (count + 1)
  findPerson 0

let shortestDistance(person1:Person) (person2:Person) =
  let countList = ref (List.empty<int>)
  let rec findClosest (list:List<Person>) (checkedList:List<Person>) (index:int) (count:int) =
    if index < list.Length then
      let node = list.Item(index)
      if List.exists (fun (x:Person) -> x.Name = person2.Name) list then 
        if count >= 0 then countList := count :: !countList 
      elif List.exists (fun (x:Person) -> x.Name = node.Name) checkedList then 
          findClosest list checkedList (index + 1) count
      elif (try (List.min !countList) with |_ -> -1) < count then
        findClosest node.Friends (node :: checkedList) 0 (count + 1)
        findClosest list (node :: checkedList) (index + 1) (count)
  findClosest person1.Friends [person1] 0 0
  try List.hd !countList with |_ -> -1

let people = 
  Person ("Abby") ::Person ("Zoey") ::Person ("Alberto") ::Person ("Natalie")
    :: Person ("George") ::Person ("Ali")     ::Person ("Kara")   ::Person ("Ricardo") 
    :: Person ("Jeff")   ::Person ("Stephen") ::Person ("Bruce")  ::Person ("Chris")
    :: Person ("Terry")  ::Person ("Kim")     ::Person ("Trevor") ::Person ("Richard")
    :: Person ("Jeff")   ::Person ("Siobahn") ::Person ("Normar") ::[];;

let Abby  = (FindPersonByName "Abby" people)
let Kara  = (FindPersonByName "Kara" people)
let Zoey  = (FindPersonByName "Zoey" people)
let Normar = (FindPersonByName "Normar" people)
let Kim = (FindPersonByName "Kim" people)
let Alberto = (FindPersonByName "Alberto" people)
let Stephen = (FindPersonByName "Stephen" people)

Abby.Befriend Zoey

Kara.Befriend Zoey
Kara.Befriend Stephen

Zoey.Befriend Alberto

Kim.Befriend Abby
Kim.Befriend Normar
Kim.Befriend Alberto

Alberto.Befriend Kim
Alberto.Befriend Abby
Alberto.Befriend Zoey

And if you make the decision - probably one of the best decisions you will ever make - to learn F#, you call the function like this:

shortestDistance Abby Stephen

EDIT: Since I didn't actually read your befriend code, I didn't know that both people involved in the "befriending" become each others friend. Here's some updated code to reflect that :|

let Befriend (person1:Person) (person2:Person) =
  person1.Befriend person2
  person2.Befriend person1

Befriend Abby Zoey
Befriend Kara Zoey
Befriend Kara Stephen
Befriend Zoey Alberto
Befriend Normar Stephen
Befriend Kim Abby
Befriend Kim Normar
Befriend Kim Alberto
Befriend Abby Alberto