Merging linear chain of vertices in a Graph (in C++)

Question

I have a large graph and it is represented in adjacency list. I would like to compress the graph by merging the linear chain of nodes. For example, if the edges are a-c, b-c, c-d, d-e, e-f, e-g:

a - c - d - e - f
    |       |
    b       g

Then c-d, d-e can be merged to a single node x and the new edge list should have a-x, b-x, x-g. I would like to implement it in C++, but I am wondering if there is any C++ graph library which handles this. Also, any suggestion for a efficient algorithm is appreciated.

Answer 1

I think you example might be broken so I am going to solve a slightly different one:

a - c - i - d - e - f
    |           |
    b           g
                |
                h

I think the solution looks like:

a - c - x - e - f
    |       |
    b       h

If you agree, then consider counting the number of times each vertex appears in the adjacency list, and storing the first two neighbors for each:

a b c d e f g h i
1 1 3 2 3 1 2 1 2
c c a i d e e g c
    b e g   h   d

The places where it is 2, we can consider collapsing: at d, g, and i:

d g i # candidates
2 2 2
i e c
e h d

Now you can see g has two neighbors not in the candidates, so simply delete g because it is a singleton "chain." This leaves d, whose neighbor i is in the candidates, so collapse d and i into a new vertex x and you're done.