0
$\begingroup$

Consider a special kind of graph where the nodes can be partitioned into $n$ layers. There are edges only between successive layers and no edges between the nodes of any given layer. So for example, the nodes in layer-1 are connected only to the nodes in layer-2, the nodes in layer-2 are connected only to the ones in layer-3 and so on. I call such a graph a "neural graph" since neural networks happen to look like this. Also note that such graphs are bi-partite since all nodes can be colored with two colors in a way that no edge has the same color on both ends.

I'm given a set of nodes, each belonging to different layers in the graph. I need to find any path (represented as an array of nodes) that starts at layer $1$, ends at layer $n$ and necessarily goes through all these nodes in the set. If no such path exists, the algorithm should return an empty array. Any ideas for doing this efficiently?

The graph can be represented in any representation, but adjacency list is preferred.

$\endgroup$
9
  • $\begingroup$ Is the graph full between any two layers? That is, im asking if for every $v$ in layer 1 there is an edge to any other $u$ in layer 2. $\endgroup$
    – nir shahar
    Jun 28 at 0:26
  • $\begingroup$ No, that is not guaranteed. If it helps, what is guaranteed is that there are no "dead end nodes" meaning every node is compatible with at-least some nodes in the next layer (apart from layer $n$ of course). But the question is well-framed even without this requirement. $\endgroup$ Jun 28 at 0:29
  • $\begingroup$ Also, there is no node not connected to any nodes in the previous layer (apart from the nodes in layer $1$). $\endgroup$ Jun 28 at 0:38
  • $\begingroup$ What do you mean by "goes through all these nodes in the set"? This is the first time you mention any set, so I don't know what set you are referring to. $\endgroup$
    – D.W.
    Jun 28 at 3:13
  • $\begingroup$ "I'm given a set of nodes, each belonging to different layers in the graph". $\endgroup$ Jun 28 at 3:15
1
$\begingroup$

Use BFS from some arbitrary node $v$ in that set. Then, denote by $u_1,\dots,u_k$ the nodes that you want to go through, and take the path $u_1\rightsquigarrow v\rightsquigarrow u_2 \rightsquigarrow v \rightsquigarrow\dots\rightsquigarrow u_k$.

If you want to start at the first layer and end at the last layer then just append a path from any node on the first layer to $v$ and then to $u_1$, and also append a path from $u_k$ to $v$ to some node on the last layer.

$\endgroup$
5
  • $\begingroup$ Why BFS instead of DFS? $\endgroup$ Jun 28 at 16:41
  • $\begingroup$ Doesn't really matter. BFS is just easier to think about when talking about paths (and shortest paths) $\endgroup$
    – nir shahar
    Jun 28 at 17:04
  • $\begingroup$ Any reason to think one of them will be faster than the other? $\endgroup$ Jun 28 at 17:50
  • $\begingroup$ Nope, but BFS is most likely to give a slightly shorter path, not that it matters for this question... $\endgroup$
    – nir shahar
    Jun 28 at 17:51
  • $\begingroup$ All paths start at layer $1$ and end at layer $n$, so they all have the same length ($n$). $\endgroup$ Jun 28 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.