Identifying useless vertices in a directed graph I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I'll call them hidden).

A useless vertex is a hidden vertex which:


can't be reached from an input vertex, OR
can't reach an output vertex.


For example:


input = yellow/green
output = blue
hidden = white
useless = red border




Note that:


cycles and self-loops are allowed
the graph may be disjoint
inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)




So what do you call this type of problem? Is there any algorithm for this?

I'm looking for more information about this. I have a python script which seems to work. I'm just not sure if it will work for all cases since I don't fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.
Let $n$ and $m$ be the number of vertices and edges of your input graph $G = (V,E)$, respectively.
You can find all useless vertices in time $O(n+m)$.

You can discover the set $S$ all vertices reachable by at least one source in $O(n + m)$ overall time.

You do this by either:


running one visit from each of the input vertices, marking discovered vertices as visited, and taking care of not revisiting already visited vertices; or
adding a dummy "super-source" vertex $s$ with an outgoing edge towards every input vertex in $G$, and then running a visit from $s$.


By using the same technique on the reversed graph $G^R$, you can find the set $T$ of all vertices that are reachable from an output vertex in $G^R$. In other words a vertex $v$ can reach an output vertex in $G$ iff $v \in T$.

The set you are looking for is then $V \setminus (S \cap T)$.