Srini Srini - 1 month ago 32
C++ Question

C# Degree of separation for connected paths

I am very new to graphs, trying to figure out the right way to create a graph for this:

Given a set of Cities and Interstates that City have, need to find out if other Cities roads intersects with one of the respective City say Boston and the degree of separation.

E.g : If Boston is the City for which the connecting interstates degree needs to be figured, 0 is the degree of separation for Boston. If new York can connect directly to Boston the degree of separation is 1, If new York connects to Boston through a different city road , the degree of separation is 2 and so on

E.g Input :

Boston,I-94;I-90
NewYork,I-80;I-94
Seattle,I-80;I-5


E.g Output:

0, Boston
1, NewYork
2, Seattle


I have transformed the input data into a
Dictionary<string,List<string>>
that has connecting cities. Trying to figure out how construct a Graph or a way i can use
Dictionary<string,List<string>>
to do BFS.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;

namespace DegreesOfSeperation
{
public class Program
{
public static void Main(string[] args)
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT */

//use dictionary to store the values for creating the graph
Dictionary<string, List<string>> vertices = new Dictionary<string, List<string>>();

string str = null;
//skip the lines with # and decrement the counter to avoid index out of bounds error
while ((str = Console.ReadLine()) != null && str != "")
{
String[] strArr = str.Split(',');
string cityKey = strArr[0];

//use dictionary to store the values for creating the graph
vertices.Add(cityKey , new List<string>());
vertices[cityKey ].AddRange(strArr[1].Split(';'));
}

if (vertices.Count > 0)
{
//create a new dictionary to insert the final vertices with neighbors
Dictionary<string, List<string>> vertices1 = new Dictionary<string, List<string>>();

foreach (var item in vertices)
{
var currentValues = item.Value.ToList();
var matchingKeys = (vertices.Where(vertex => vertex.Value.Any(value => currentValues.Contains(value))).Select(pair => pair.Key)).Where(keys => keys != item.Key);

//add values to the dictionary with the new matching vertices/nodes
vertices1[item.Key] = matchingKeys.ToList();
}

//Now Vertices1 has the transformed values as below
//Boston: NewYork
//NewYork: Boston, Seattle
//Seattle: NewYork
//How to form the Graph and do the Breadth-First-Search here ??
}
}
}
}

asp asp
Answer

This can be solved with a breadth first search (BFS) in the graph. This algorithm gives you back a tree whose root is the city you start with and the unique path from there to any other node/city is the one with the fewest possible hops.

If you need this information for all your cities/nodes then run the algorithm once for each city.

For an explanation of BFS and its running time a good source is e.g. wikipedia.


BFS needs a graph as input, preferably given by an adjacency list. The given data thus needs a transformation first: Run over the list and for each city store the cities that are connected directly to it:

Boston: NewYork NewYork: Boston, Seattle Seattle: NewYork

Now you maintain three pieces of information: A working queue Q initialized with Boston (in your case), a list S of "already connected" cities initialized with Boston and an array P of "predecessors": For each city this will contain the previous city on the path from Boston. For Boston this points to nil.

Run over the queue: Pick the first entry c in Q, Run over its adjaceny and whenever you encounter an unconnected city add it to S, set its predecessor to c and add it to the end of Q.

If every city can actually be reached from Boston then you end with a tree of "predecessors". To determine the distance of a city follow the predecessors from this city to Boston.

Comments