Longest common path between k graphs

Question

I was looking at interview problems and come across this one, failed to find a liable solution.

Actual question was asked on Leetcode discussion.

Given multiple school children and the paths they took from their school to their homes, find the longest most common path (paths are given in order of steps a child takes).

Example:

child1 : a -> g -> c -> b -> e
child2 : f -> g -> c -> b -> u
child3 : h -> g -> c -> b -> x

result = g -> c -> b

Note: There could be multiple children.The input was in the form of steps and childID. For example input looked like this:

(child1, a)
(child2, f)
(child1, g)
(child3, h)
(child1, c)
...

Some suggested longest common substring can work but it will not example -

1 a-b-c-d-e-f-g
2 a-b-c-x-y-f-g
3 m-n-o-p-f-g
4 m-x-o-p-f-g
1 and 2 will give abc, 3 and 4 give pfg
now ans will be none but ans is fg

it's like graph problem, how can we find longest common path between k graphs ?

Answer 1

Approach 1: With Graph construction

Consider this example:

1 a-b-c-d-e-f-g
2 a-b-c-x-y-f-g
3 m-n-o-p-f-g
4 m-x-o-p-f-g

Draw a directed weighted graph.

I am a lazy person. So, I have not drawn the direction arrows but believe they are invisibly there. Edge weight is 1 if not marked on the arrow.

Give the length of longest chain with each edge in the chain having Maximum Edge Weight MEW.

• MEW is 4, our answer is FG.
• Say AB & BC had edge weight 4, then ABC should be the answer.

The below example, which is the case of MEW < #children, should output ABC.

1 a-b-c-d-e-f-g
2 a-b-c-x-y-f-g
3 m-n-o-p-f-h
4 m-x-o-p-f-i

If some kid is like me, the kid will keep roaming multiple places before reaching home. In such cases, you might see MEW > #children and the solution would become complicated. I hope all the children in our input are obedient and they go straight from school to home.

---

Approach 2: Without Graph construction

If luckily the problem mentions that the longest common piece of path should be present in the paths of all the children i.e. strictly MEW == #children then you can solve by easier way. Below picture should give you clue on what to do.

Take the below example

1 a-b-c-d-e-f-g
2 a-b-c-x-y-f-g
3 m-n-o-p-f-g
4 m-x-o-p-f-g

Method 1:

Get longest common graph for first two: a-b-c, f-g (Result 1)

Get longest common graph for last two: p-f-g (Result 2)

Using Result 1 & 2 we get: f-g (Final Result)

Method 2:

Get longest common graph for first two: a-b-c, f-g (Result 1)

Take Result 1 and next graph i.e. m-n-o-p-f-g: f-g (Result 2)

Take Result 2 and next graph i.e. m-x-o-p-f-g: f-g (Final Result)

The beauty of the approach without graph construction is that even if kids roam same pieces of paths multiple times, we get the right solution.

---

If you go a step ahead, you could combine the approaches and use approach 1 as a sub-routine in approach 2.

Answer 2

You can construct a directed graph g with an edge a->b present if and only if it is present in all individual paths, then drop all nodes with degree zero.

• The graph g will have have no cycles. If it did, the same cycle would be present in all individual paths, and a path has no cycles by definition.

• In addition, all in-degrees and out-degrees will be zero or one. For example, if a node a had in-degree greater than one, there would be two edges representing two students arriving at a from two different nodes. Such edges cannot appear in g by construction.

The graph will look like a disconnected collection of paths. There may be multiple paths with maximum length, or there may be none (an empty path if you like).

In the Python code below, I find all common paths and return one with maximum length. I believe the whole procedure is linear in the number of input edges.

---

import networkx as nx

path_data = """1 a-b-c-d-e-f-g
2 a-b-c-x-y-f-g
3 m-n-o-p-f-g
4 m-x-o-p-f-g"""
paths = [line.split(" ")[1].split("-") for line in path_data.split("\n")]
num_paths = len(paths)

# graph h will include all input edges
# edge weight corresponds to the number of students
# traversing that edge
h = nx.DiGraph()
for path in paths:
  for (i, j) in zip(path, path[1:]):
    if h.has_edge(i, j):
      h[i][j]["weight"] += 1
    else:
      h.add_edge(i, j, weight=1)

# graph g will only contain edges traversed by all students
g = nx.DiGraph()
g.add_edges_from((i, j) for i, j in h.edges if h[i][j]["weight"] == num_paths)

def longest_path(g):
  # assumes g is a disjoint collection of paths
  all_paths = list()
  for node in g.nodes:
    path = list()
    if g.in_degree[node] == 0:
      while True:
        path.append(node)
        try:
          node = next(iter(g[node]))
        except:
          break
    all_paths.append(path)
  if not all_paths:
    # handle the "empty path" case
    return []
  return max(all_paths, key=len)

print(longest_path(g))
# ['f', 'g']