CareerCup

Do Breath First Search of a directed weighted graph where the weight is the closenessWeigth meaning that the higher it is the less close friend relationship is.

This algorithm will get the closest of the closest friends only.

Now I'm thinking about this algorithm when doing a party at my place. ;-)

// This represents a friend
class FriendVertex
{
	// Describes all the edges to another friends
	List<FriendEdge> relationships;

	object Data; // Whatever other data object there is to have.
}

// This represents a friend relationship
class FriendEdge
{
	FriendVertex friend;
	int closenessWeigth;
}

public IEnumerable<FriendVertex> GetNthClosestFriends(
	IEnumerable<FriendVertex> mFriends, 
	int nthFriends)
{

	Queue<FriendEdge> q = new Queue<FriendEdge>();

	HashSet<FriendVertex> foundFriends = new HashSet<FriendVertex>();

	// Populate known friends first
	foreach(FriendVertex fv in mFriends)
	{
		// Adding this friends as you don't want then but their friends
		foundFriends.Add(fv);

		q.Enqueue(new FriendEdge() { 
				friend = fv,
				closenessWeigth= 0});
	}	

	// Stop when there are no friends left or we fill the nthFriendCount
	while(q.Count != 0)
	{
		FriendEdge friendEdge = q.Dequeue();

		if(friend.closenessWeigth != 0)
		{
			friend.closenessWeigth--;
			q.Enqueue(friend);
		}
		else
		{
			
			// There would definitely be repeated friends so only caring 
			// about relationship that friend of a friend first.
			if(!foundFriends.Contains(friend))
			{
				// One less friend needed
				nthFriends--;
				foundFriends.Add(friend);

				yield return friend;				
			}
			
			// This means that we are done finding friends
			if(nthFriends == 0)
				break;

			// Get friends of this friend
			foreach(FriendEdge fe in friend.relationships)
			{
				// Recreating an object to not modify the original from the graph
				q.Enqueue(new FriendEdge() {
						friend = fe.friend,
						closenessWeigth = fe.closenessWeigth});
			}
		}

	}

	// No friends of friends found so returning empty set
	return new List<FriendVertex>();
}

In my view, the first thing is to define what makes a friend have a high priority. We use G(v,e,w) as the social graph, G.adj(me) as the sub-graph of my friends network, and W(v1,v2) as the familiar weight of v1 and v2. Here are my rules to choose friends.

1. Friends in the party are my closer ones.
2. Friends are familiar with each other.

So my goal is to max the total familiarity of top n friends and me.

Greedy Algorithm:

1. Fset is empty, put me in the Fset.
2. while(|Fset|<=n+1)
   {
        choose v in G.adj(me) that max(Familiar(v+Fset));
        Fset.insert(v);
        G.adj(me) = G.adj(me)-'v';
   }

Familiar(Set) = the sum familiar weight of each pair(v1,v2) which v1 and v2 belongs to Set;

This greedy algorithm can't find the global optimal solution. Wish better ideas!

Solution would be subgraph with n vertices which has most edges that connect two vertices in that subraph.

1) If we have subgraph, counting edges in it can be done fast (worst, n^2).

2) If we can find subgraph fast, e.g. in O(P(m)) time where P(m) is some polynomial - we could do binary search on number of vertices n in a subgraph in range (0..m) and find smallest subgraph that has n*(n-1)/2 connections, which would be fully connected subgraph i.e. clique.

3) this would mean that we could find clique in a graph in worst case O(P(m)*log(m)*m^2), and since finding clique is NP-complete, we conclude that finding best subgraph is at least as hard as finding a clique (can't be done in O(P(m)) time) - it is NP-complete.

Brute force solution has O( nchoosek(m, n) ) complexity (iterates over all subgraphs and finds best one).

Following is the feature set

1) proximity of the friend from the event ( no need to waste your b'day invitation for your out of country friend)
2) Your immediate relative (on FB you can specify relationships with people) who qualify for #1
3) Those not in #2 but in #1 - Notion of 'closeness'. A close friend maybe one with who have have frequent messages, mutual likes, part of same private groups
4) Spouses of #3)