I have a tree structure of interconnected nodes of various types. Each node keeps track of which nodes it is connected to. In this structure I need to find the longest unconnected chain or path of same type nodes.
I've read up on graphs and breadth/depth first searches but these don't quite yield the results I need. (they'll find a chain but also include all the dead end branches between an origin and destination node)
Is there an existing algorithm for this purpose?
If by "chain" you mean connected component, then
Say your graph has edges E and vertices V.
Iterate over the edges, deleting all edges connecting nodes of a different type. This is O(|E|).
Find the the connected components, using depth-first or breadth-first. This is O(|E|+|V|).
The largest connected component will be the longest chain of same-type nodes.
If by chain you mean simple cycle (starts, stops at same node, doesn't revisit any nodes), then this is NP complete. If the connected components are small, it should be feasible none the less.
If by chain you mean simple path, then this is NP-Hard.