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):
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:
[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):
- Check for a common friend in the friends of each side. (From one side)
- Increase depth and look for common friends. (Find common friends between friends of friends)
- 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:
[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]
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]