Here is the situation:

I am using a number of vertices to build a road network. Most vertices point towards another (root) vertex - except the first vertex. A vertex can only point to one other vertex. A vertex may be the root of multiple vertices, but at no time one has knowledge of how many vertices are pointing to itself.

Now I need to find unique cycles in that graph to get enclosing polygons, which I then use to place buildings. However I also need to get the dead ends of this graph, since a polygon edge may be cut by one or more dead ends, or nearby dead ends could be used to form a cycle.

Could you give me any advice to tackle this problem, please. Especially if there is existing code for Unity to speed up development. Any help would be appreciated.

Sounds more like just a straight algorithm problem – nothing to do with Unity. Some comments:

Is there an underlying grid? Most graph algorithms don’t care about the space in-between verts (the concept of the area inside loop ABC doesn’t even make sense, often.) Might be easier to draw the lines on the grid; maybe mark dead-ends special, and then run something to find connected areas of that grid (find an empty space, recursively find all connected free spots.)

Graphs on 2D surfaces are, I believe, called “flat” graphs, if you do a search. Also, technically, if a vert can only point to one other, the edge only goes that way, so there are no cycles. Traditional graph code assumes you point to everyone who points to you (this is if you search for flat graph algorithms.)

[edit]

If the graph really generates well-formed N-gons (no internal dead-ends, or crossing edges,) you could try this: consider each edge has two sides, and each side may be facing an N-gon. Might have a separate edge list to make it easier.

Pick any edge and one end to start. If you look from start to end of that edge, your right side is the possible N-gon (so when you start at the other end, you’re checking the other side.) Follow edges around until you get back. To do that, go to the end vert of the current edge and search the edge list. For each, transform to local coords of the current edge (vector from start to end) and find the angle. Closest to 180 w/o going over wins. That’s the next edge that bends around to “your” right. Repeat for that new edge from that vert.

If you get back to the start, list all those verts as an N-gon and mark them. Otherwise just mark them. Quit when you have them all marked (each side of each edge.)

I *think* that would work. Running time is fast – O(n). Might be an assignment in 3rd-year algorithms class at a good school. Then you have the problem of seeing what size building will fit in them.