I am attempting to implement an algorithm found in a paper. One of the subtasks is: "given a directed acyclic graph $(V,E)$, subset of edges $E' \in E$, and vertices $u,v \in V$, find all edges $e \in E''\subset E'$ that lie on some simple path composed of of edges in $E'$ from $u$ to $v$". That is to say, find all edges that lie on some simple path from $u$ to $v$ in the induced graph $(V,E')$.
The best I was able to come up with is:
Create induced graph $(V,E')$. For every edge $e \in E'$, search for an endpoint $q$ of $e$ using BFS from root node $u$. If found, search for $v$ with BFS from root node $q$. If both succeed, add $e$ to $E''$.
I suspect there a more efficient way to do it but the paper claims it can be done in $O(|E|)$ . In addition, I would like to be able to do this with existing libraries or methods (I'm currently using networkx with python).
I'm trying to find a solution to the same problem but for edges on simple paths in directed graphs with cycles. I have worked out a solution which doesn't work in my case (it finds all paths, not just simple ones) but that should work for you.
I based it on Kosaraju's algorithm for finding strongly connected components. Essentially starting from your source node and your initial (sub)set of edges you generate the set of all edges that are reachable using DFS.
You then take your destination node and the set of edges from the last step and by DFS find all edges that can reach the destination (this is the same operation as the previous step but with the edge directions reversed).
The result is the intersection of the edges which can be reached from the source and can reach the destination, and thus must fall on some path between them. The complexity is $O(|E|)$.