### Find a vertex ordering of a finite graph G

I've tried to implement this algorithm in C++ but it has some problems. I need some advice how to get it work faster and propertly.

Algorithm As Batagelj & Zaversnik (2003) describe, it is possible to find a vertex ordering of a finite graph G that optimizes the coloring number of the ordering, in linear time, by repeatedly removing the vertex of smallest degree. In more detail, the algorithm proceeds as follows:

Initialize an output list L.
Compute a number dv for each vertex v in G, the number of neighbors of v that are not already in L. Initially, these numbers are just the degrees of the vertices.
Initialize an array D such that D[i] contains a list of the vertices v that are not already in L for which dv = i.
Initialize k to 0.

Repeat n times:

1.Scan the array cells D[0], D[1], ... until finding an i for which D[i] is nonempty.

2.Set k to max(k,i)

3.Select a vertex v from D[i]. Add v to the beginning of L and remove it from D[i].

4.For each neighbor w of v, subtract one from dw and move w to the cell of D corresponding to the new value of dw.

At the end of the algorithm, k contains the degeneracy of G and L contains a list of vertices in an optimal ordering for the coloring number. The i-cores of G are the prefixes of L consisting of the vertices added to L after k first takes a value greater than or equal to i. Initializing the variables L, dv, D, and k can easily be done in linear time. Finding each successively removed vertex v and adjusting the cells of D containing the neighbors of v take time proportional to the value of dv at that step; but the sum of these values is the number of edges of the graph (each edge contributes to the term in the sum for the later of its two endpoints) so the total time is linear.

Here is my code (Susedia = Neighbors)
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364`` ``````int his_place_inArray(int x,vector A) { for(int i=0;i vertex_ordering(vector A) { vector L; vector> D(100); vector d(A.size()); vector N; //tsusedia //Compute a number dv for each vertex v in G, the number of neighbors of v //that are not already in L. Initially, these numbers are just the degrees //of the vertices. for (int i = 0; i < A.size(); i++) { N = susedia(A[i], L); d[i] = N.size(); //Initialize an array D such that D[i] contains a list of the vertices //v that are not already in L for which dv = i. D[d[i]].push_back(A[i]); } int i; int k = 0; //Initialize k to 0. int chosen; //chosen vector chosen_N; //Neighbors of chosen for (int j = 0; j < A.size(); j++) { //for n times for (i = 0; i < 10; i++) { if (D[i].empty() == false) { k = max(k, i); break; } } chosen = D[i][0]; L.push_back(chosen); D[i].erase(D[i].begin()); chosen_N = susedia(chosen, L); int n; //neighbor //For each neighbor w of v, subtract one from dw and move w to the cell of D corresponding to the new value of dw. for (int w = 0; w < chosen_N.size(); w++) { n = chosen_N[w]; int p = his_place_inArray(n,A); //chosen neighbor place in A int p_inD = his_place_inArray(n,D[d[p]]); //chosen neighbor place in D D[d[p]].erase(D[d[p]].begin()+p_inD); d[p]--; D[d[p]].push_back(n); } } return L; }``````
Topic archived. No new replies allowed.