3

I try to implement the algorithm described in this paper (page 8), but there's a place that I can't understand, and the authors do not provide a more detailed explanation or pseudocode.

They show how to contract this graph:

enter image description here

Vertices A, G & F are external and must remain. Now, they analyze the connections:

For 1,8,9, the connections are {1}A,8,9, {8}G,9,1, and {9}F,8,1. Any vertices connected solely within the subgraph are removed from the list. In this particular instance none of the vertices is internal to the subgraph. Next, any repeated items are removed from these lists. What remains are 1,8,9, A,G,F. The centroid, X, is now calculated as the mean of the vertices in the subgraph (1,8,9).

What are these repeated items? What is the criteria that 1, 8 & 9 can be reduced?

Are there better papers & algorithms for graph simplification? What I want to do is simplify a road graph, removing junctions and cities if needed.

Improve this question

2 Answers 2

Reset to default
2

The set of vertices (along with any edges between them) {1,8,9} is considered a "subgraph." The "connections" (edges) emanating from these vertices can be enumerated by looping over the vertices:

1: 1-A, 1-8, 1-9
8: 8-1, 8-G, 8-9
9: 9-1, 9-8, 9-F

In this table each row corresponds to a vertex of the subgraph. The edges adjoining that vertex are listed. Think of the vertex as the "source" and the other as the "destination" of each edge. Thus, on the first row, 1 is the source of edge 1-8 and 8 is the destination, whereas on the second row, 1 is the destination of edges 8-1 (which, of course, is the same as edge 1-8) and 8 is the source.

If, within any such row, all destination vertices lie within the subgraph, then the entire row is deleted. (This would correspond to an "internal" vertex.) In this case, 1 has A as a destination, 8 has G as a destination, and 9 has F as a destination, so none of the rows is eliminated.

Next--this is probably the unclear part in the paper--the surviving lists of destination vertices are combined, giving

A, 8, 9; 1, G, 9; 1, 8, F

There are duplicates in this list: 1, 8, and 9 all appear twice (each is mentioned both as a source in one line and as a destination in another). The list of unique vertices is

A, 8, 9, 1, G, F

The algorithm is completed by replacing each vertex in the subgraph {1,8,9} by a new vertex X located at the centroid of the locations of {1,8,9}. That original list of edges now reads

X: X-A, X-X, X-X
X: X-X, X-G, X-X
X: X-X, X-X, X-F

We remove all the self-loops X-X to get

X-A, X-G, X-F

That's the new graph. The algorithm has finished.

Improve this answer
2
  • So, {1, 8, 9} are replaced because they are duplicates in {A, 8, 9; 1, G, 9; 1, 8, F}, or just because they are the rest of the subgraph? (after removing the internal nodes)
    – culebrón
    Commented Mar 16, 2012 at 19:44
  • 1
    The entire idea of the algorithm is to collapse the subgraph to a point. Thus, at the outset, you know that all the original vertices {1,8,9} will be replaced by a single new vertex X. The issues to address are (1) where to locate X and (2) what connections to make to X from the remaining vertices. The connections are obvious: any edge originating from beyond the subgraph and ending within the subgraph needs to end in X. The only element of any interest in this particular algorithm is the decision not to base the location of X on any of the internal vertices.
    – whuber
    Commented Mar 16, 2012 at 19:46
1

This book has all the answers if you want to study netwroks. May be you can find in you library.

http://www.amazon.com/Network-Flows-Theory-Algorithms-Applications/dp/013617549X

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.