Graph theory algorithm

  • Thread starter brydustin
  • Start date
  • #1
205
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
172
1
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.
 
  • #3
1,065
53
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
 

Related Threads on Graph theory algorithm

  • Last Post
2
Replies
25
Views
10K
  • Last Post
Replies
3
Views
11K
  • Last Post
Replies
10
Views
3K
Replies
3
Views
819
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
22
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
Top