Introduction
So I recently came across this problem while browsing the google codejam contest practice problems. The problem is outlined below with the solution I came up with at the end. I typically use python as my programming language of choice for algorithm type problems as it is easy to use and therefore more focus can be put into actually formulating your algorithm rather than having to worry about the syntax and semantics of the language. A downside is that due to it’s highlevel nature it is less performant than other languages in general but this shouldn’t be a problem in most cases.
Problem
You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.
In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C_{1}, C_{2}, C_{3}, …, C_{n}, Y where X inherits from C_{1}, C_{i} inherits from C_{i + 1} for 1 ≤ i ≤ n – 1, and C_{n} inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.
A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.
Input
The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines follow. The i^{th} line starts with a nonnegative integer M_{i} indicating the number of classes that class i inherits from. This is followed by M_{i} distinct positive integers each from 1 to N representing those classes. You may assume that:
 If there is an inheritance path from X to Y then there is no inheritance path from Y to X.
 A class will never inherit from itself.
Output
For each diagram, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is “Yes” if the class diagram contains a diamond inheritance, “No” otherwise.
Limits
1 ≤ T ≤ 50.
0 ≤ M_{i} ≤ 10.
Small dataset
1 ≤ N ≤ 50.
Large dataset
1 ≤ N ≤ 1,000.
Sample
Input 
Output 
3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0

Case #1: No
Case #2: Yes
Case #3: Yes

Solution
So pretty much my solution is based off of the breadth first search graph algorithm. Pretty much all that is done is to first build the graph using the classic adjacency list representation. We then loop through all nodes in the graph and invoke the BFS algorithm on each node. The special trick comes in the conditional section where we show that if we are trying to add a node to the existing path and the node already exists in the path created then it means we have already visited that node and hence another path to this node has been found. We can therefore break the loop as we have found this second path. Ways in which this algorithm can be improved is to simply return true or false as we only need a boolean for output and to come up with an alternate faster way of searching the existing path for the given node rather than just going
if not v in path:
Perhaps a hash table should suffice in achieving this. Example input can be retrieved here, to run the program simply go
python [programName.py] < inputfile
from commandline.
The code:
from sys import stdin
# create directed graph
def build_graph(rawData):
""" Graph is built into an adjacency list
e.g. 2 3
1
means that the first node points to the 2nd and 3rd and
the second node points to the first with the 3rd node
having no outgoing edges
"""
graph={}
count = 1
for line in rawData:
data = line.split()
edges = []
for edgesString in range(1, len(data)):
edges.append(int(data[edgesString]))
graph[count] = edges
count+=1
return graph
# count number of paths using BFS
""" The special trick: if the node currently exists in the path then
we can simply say that there is another path to this node and hence
break the loop as we have found there is more than 1 path to the target
"""
def count_paths(graph, start, path=[]):
numPaths=1
q=[start]
while q:
v=q.pop(0)
if not v in path:
path=path+[v]
q=q+graph[v]
else:
numPaths+=1
break
return numPaths
for i in range(int(stdin.readline())):
rawData = []
for node in range(int(stdin.readline())):
rawData.append(stdin.readline())
graph = build_graph(rawData)
numPaths = 0
# loop through all nodes in the graph
for node in range(1,len(rawData)+1):
numPaths = count_paths(graph, node)
if numPaths >= 2: break
isDiamond = 'Yes' if numPaths >= 2 else 'No'
print 'Case #'+str(i+1)+': ' + isDiamond
Tags: algorithms, google, google codejam, programming, python