San
BAN USER- 0of 0 votes
AnswersGoal: Create a software application that takes a set of people-relationships as input and provides a user interface that allows an operator to determine how “connected” any two people are.
- San in United States
Relationships / Input:
John:Jane:Jill:Jeb:Jim
Jane:John:Jason:June
Jill:John:Jim
Jim:John:Jill:June
Jeb:June:John
June:Jim:Jane:Jeb
Jason:Jane
For example, John has a 2nd degree connection to June since June has a 1st degree connection to Jim who in turn has a 1st degree connection to John.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
Thanks again Bevan..The problem is we have to find a degree of connection if the two people are not directly friends. The question states an example :
"John has a 2nd degree connection to June since June has a 1st degree connection to Jim" --> They first find out Jim and then since is Jim is common between John and June they made is second degree ..this is where I am getting lost ...
Thanks Bevan .. BFS meaning - Breadth First Search right ? Which Data Structure should I use to first store these values ? I was thinking to first get all the distinct values and then create a two dimensional array of those values eg : In the list above I have 7 distinct values so I create an array of arr[7][7] ? Which data structure is ideal to store Matrix ? Any pseudocode will be really helpful...I need to create a working version
- San March 20, 2013
Repmartinskrull, Analyst at A9
Hi everyone, I am from new york,USA. I currently work in the Affiliate Marketing industry. I love all things ...
Thanks Kai..for your help but this logic is going in infinite loop :
- San March 20, 2013using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication1
{
public class node
{
public int nodeValue;
public int degree;
public node(int nodeValue, int degree)
{
this.nodeValue = nodeValue;
this.degree = degree;
}
}
class Program
{
public Boolean[,] adjMatrix;
static void Main(string[] args)
{
Program p = new Program();
p.Initialize();
}
/* parse the strings & represent them in a Graph structure.. i'm using matrix representation here
* node-> person
* edges-> relationship (i.e. connected or not )
* In the above example
* John, Jane, Jill, Jim, Jeb, June,Jason represented by vertices
* 0, 1, 2, 3, 4, 5, 6
*
* I'm using String[] array for convinience to represent the connections as below
* each index referring to each person as above, and each string value representing the connections to the persons.
*/
public void Initialize()
{
string[] connections = { "1:2:4:3",
"0:6:5",
"0:3",
"0:2:5",
"5:0",
"3:1:4",
"1"
};
int totalNodes = connections.Length;
adjMatrix = new Boolean[totalNodes, totalNodes];
//initially there are no connections among the nodes..
for (int i = 0; i < totalNodes; i++)
{
for (int j = 0; j < totalNodes; j++)
{
adjMatrix[i, j] = false;
}
}
//setting up the connections
// from the problem statement, its indicated that it's an undirected graph
// ( this can be seen from the connections that are made in the graph )
for (int i = 0; i < totalNodes; i++)
{
string[] str = connections[i].Split(':');
foreach (string st in str)
{
int j = Convert.ToInt32(st);
adjMatrix[i, j] = true;
}
}
int node1, node2;
// eg: You would like to know the connection degree b/w John & June
// so node1-> 0, node2-> 5
node1 = 0;
node2 = 5;
//use Breadth First Search to get the degreee of connection
BFS(node1, node2, totalNodes);
}
public void BFS(int source, int target, int totalNodes)
{
int degree=0;
Boolean found=false;
Boolean[] color = new Boolean[totalNodes];
for(int i=0;i<totalNodes;i++)
color[i]=false;
Queue<node> q = new Queue<node>();
q.Enqueue(new node(source,0));
//Deque<node> q= new ArrayDeque<node>();
//q.add(new node(source,0));
node tempNode = new node(0,0) ;
while(q.Count != 0 && !found)
{
tempNode = (node) q.Peek();
if(tempNode.nodeValue == target){
found=true;
degree = tempNode.degree;
break;
}
if(color[tempNode.nodeValue]){
continue;
}
color[tempNode.nodeValue]=true;
for(int i=0;i<totalNodes;i++){
if(adjMatrix[tempNode.nodeValue,i])
{
q.Enqueue(new node(i,tempNode.degree+1));
}
}
}
if(found){
Console.WriteLine("Degree -> "+degree);
}
else
Console.WriteLine(" Not Connected ");
}
}
}