Implementation and performance of sparse graphics in C ++

Question

I am currently working on a managed graph structure in C ++ (without Boost GL for this project). The main application will identify connected components and receivers. The graphs are expected to be sparse (the upper limit is E ~ 4V at the edges of num) and all will be uniform. I am trying to solve an adjacency list, a list of incidents, or perhaps some other representation that I have not heard about (the matrix with the application is not a variant of bc sparseness). The bottleneck is likely to be the space as a whole and the speed of the graph initialization: the graphs will be initialized from potentially huge arrays, so that each element in the array will be a vertex with a directed edge to one of the neighboring elements. To get edges for each vertex, you must first compare all its neighboring elements.

My questions: (1) Which view is usually quicker to initialize, and also quicker to bypass BFS, (2) What algorithms (except vanilla BFS) exist for finding connected components? I know that O (V + E) uses BFS (which is optimal, I think), but I am worried about the size of the intermediate queue, since the width of the graph grows exponentially with height.

There is not much experience in implementing schedules, so I would be grateful for any suggestions.

Answer 1

Consider the layout as follows:

The adjacency list can be implemented as an array of [Nx4] (n in this case is 3, and 4, because you say that 4 is the maximum number of edges in your case) in the following form:

2 3 0 0 3 0 0 0 0 0 0 0 

the above view assumes the number of vertices in sorted order, where the first index in the array is specified (v-1) .

The list of incidents, on the other hand, requires that you define a list of vertices, a list of edges, and elements of the connection between them ( incidence list - graph ).

Both are good in terms of space utilization compared to the adjacency matrix, as your graph is very sparse, as you said.

My suggestion would be to go to an adjacency list, which you can initialize as a continuous array [Nx4] in memory (since you say that you will have no more than 4 edges for one vertex). This view will initialize faster. ( Also, this view will work better in terms of cache efficiency. )

However, if you expect your chart to be dynamically and frequently resized, incident lists may be better since they are usually implemented as lists that are not continuous (see link above). In this case, the removal and distribution of the adjacency array may be undesirable.

Answer 2

The most effective way to implement a graph for your goals is probably to combine an adjacency list for each vertex and additionally a hash structure that maps pairs of vertices to edges if they exist. This will require O (| V | + | E |) for the O (| E |) adjacency list for the hash structure and give you the expected O (1) containsEdge(vertex v, vertex w) , insertEdge(vertex v, vertex w) and removeEdge(vertex v, vertex w) using matching to get the pointers needed to quickly change vertex adjacency lists.