Как я могу отсортировать массив, который зависит от количества других? - PullRequest
Новая
       21

Как я могу отсортировать массив, который зависит от количества других?

0 голосов
/ 22 апреля 2019

Например, у меня есть этот массив: 

G->colour = [2,1,0,1,0,1,0,1,2];
G->vertex = [1,2,3,4,5,6,7,8,9];
G->order = [1,2,3,4,5,6,7,8,9]; //the same of vertex

вершина 1 имеет цвет 2, вершина 2 имеет цвет 1 и т. Д. *
Мне нужно это решение G->order = [1,9,3,5,7,2,4,6,8]. Я хочу отсортировать порядок, используя количество вершин одного цвета в порядке возрастания, т.е.

  • У меня есть две вершины с цветом 2 (вершины: 1, 9)
  • У меня есть три вершины с цветом 0 (вершины: 3,5,7)
  • У меня четыре вершины с цветом 1 (вершины: 2,4,6,8)

У меня есть функция (RMBC), которая сортирует вершины по цвету. Например: 

G->colour = [2,1,0,1,0,1,0,1,2];
G->order = [1,2,3,4,5,6,7,8,9];

Возвращает функцию order = [3,5,7,2,4,6,8,1,9].

Кроме того, я поместил структуру графа и жадную функцию, которая окрашивает наши вершины.

У меня гораздо больше кода, но я думаю, что с этим все в порядке.

Спасибо! 

typedef struct Graph
{
    u32** vecinos;
    u32* vertexes;  // Position of vertexes
    u32* color; //Structure type declarations do not support initializers
    u32* grados;
    u32* order; //it has the order of vertex for greedy
    u32* visitados;
    u32 m; //number of edges
    u32 n; // number of vertex
    u32 max; // number of colors
    u32* indEnVecinos;
} Graph;

//RMBC
u32* vert_color;
char RMBC(Graph* G)
{
    vert_color = G->color;
    qsort(G->order, G->n, sizeof(u32), compColoresNormal);
    return 0;
}

int compColoresNormal(const void *v1, const void *v2) {
    u32 color1 = vert_color[*(const u32 *)v1 - 1];
    u32 color2 = vert_color[*(const u32 *)v2 - 1];
    if (color1 < color2)
    {
        return -1;
    }
    else if (color1 > color2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
// end RMBC

//Greedy 
u32 Greedy(Graph* G)
{
    u32** aux = G->vecinos; 
    u32 max_color = 0;
    u32 nVer = G->n;
    u32* color_vecinos = (u32*)malloc(sizeof(u32) * nVer);
    memset(color_vecinos,0,nVer*sizeof(u32));
    u32 indice = binarySearch(G->vertexes,0,nVer-1,G->order[0]);
    G->color[indice] = 0;
    G->visitados[indice] = 1;
    u32 indice2 = 0;
    u32 reset = 0; 
    for (u32 i = 1; i < nVer; ++i)
    {
        memset(color_vecinos,0,(reset+1)*sizeof(u32));
        indice = binarySearch(G->vertexes,0,nVer-1,G->order[i]);
        G->visitados[indice] = 1;
        u32 color = 0;
        reset = 0;
        for (u32 i = 0; i < G->grados[indice]; ++i)
        {
            indice2 = binarySearch(G->vertexes,0,nVer-1,aux[G->indEnVecinos[indice]+i][1]);
            if(G->visitados[indice2])
            {
                color_vecinos[G->color[indice2]] = 1;
                if(reset < G->color[indice2]) reset = G->color[indice2];
            }
        }
        for (u32 i = 0; i < nVer; ++i)
        {
            if(!color_vecinos[i])
            {
                color = i; 
                break;
            }
        }
        G->color[indice] = color;
        if(color > max_color) max_color = color;
        if(reset < color) reset = color;
        if(reset == nVer) reset--;
    }
    free(color_vecinos);
    printf("terminé Greedy\n");
    return max_color + 1;
}
//end Greedy

Ответы [ 2 ]

1 голос
/ 22 апреля 2019

Ваши цвета и вершины маленькие числа?

Кодировать пару в одно число, сортировать и декодировать 

//G->colour = [2,1,0,1,0,1,0,1,2];
//G->vertex = [1,2,3,4,5,6,7,8,9];

colour * 1000 + vertex // based on small values!!

// encode to
// [2001, 1002, 3, 1004, 5, 1006, 7, 1008, 2009]
// sort to
// [2001, 2009, 3, 5, 7, 1002, 1004, 1006, 1008]
// decode to
//G->colour = [2,2,0,0,0,1,1,1,1];
//G->vertex = [1,9,3,5,7,2,4,6,8];
0 голосов
/ 22 апреля 2019

Вы знаете, какие заказы уже есть, это те, на которые указывают v1 и v2 - сохраните их в переменной, а затем: 

int compColoresNormal(const void *v1, const void *v2) {
    u32 order1 = *(const u32 *)v1;
    u32 order2 = *(const u32 *)v2;
    u32 color1 = vert_color[order1 - 1];
    u32 color2 = vert_color[order2 - 1];
    if (color1 < color2) {
        return -1;
    }
    else if (color1 > color2) {
        return 1;
    }
    // same color, use the order
    else {
        // return 0;
        // branchless comparison expression
        return (order2 < order1) - (order1 < order2);
    }
}
...