Finding Vertex with 1 Edge in Large Graph - Algorithm

[brydustin]

If I have a very large graph (set of edges and vertices, NOT the "picture/sketch" of the graph), what is a very efficient way to find all the vertices with only one edge attached to them. Most of the vertices will have many edges attached to them. Also any vertex may be connected to itself, and when we say that we want all vertices with only one edge we really mean all vertices with at most one non-self edge (i.e. may be connected to self and at most one other vertex).

I'm looking for some sort of computer algorithm to sort out a very large E=edge and V=vertex pair of sets.

 

[Jack21222]

I am a terrible "programmer" with almost no formal training, so this is probably not the most efficient way.

I assume the edges are labeled by the vertices they're adjacent to (xy, xz, wz and so on). I'd remove any edges of the form xx, yy, and any multiple edges. Then, sort the list alphabetically, and compare the first letter of each edge to the edge above and below it. If both are different, that first letter of the edge is a vertex of degree 1 in the simple subgraph obtained, and thus is adjacent to only one other vertex.

That's the algorithm I'd use, anyway, if I had to do such a thing. But again, as I said, I'm not really a programmer, I just smash some code together when I have to on occasion. So, if my suggestion is not feasible, I apologize.

 

[gsal]

yeah...I would put together a short program (say, in python) and programmatically go through your data and pick the data of interest...

you know what your data looks like, so you should be able to pick it apart, too.

other than that, I don't know what exactly you are expecting from this thread without much info.

Go ahead and post a dozen lines from your data...take a shot at some code, post it, too...THEN, we may be able to help