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.
- input = yellow/green
- output = blue
- hidden = white
- useless = red border
- 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.