Exécution d'une contraction de bord sur un graphique

Question

J'essaie de faire une contraction de bord sur un graphique. n est le nombre de sommets dans le graphique. Le vecteur f contenant des paires de sommets représentant une arête contient les arêtes à contracter.

Le graphique ne contient aucune auto-boucle.

Veuillez indiquer les éventuelles erreurs logiques dans le code. Si la méthode est entièrement fausse alors s'il vous plaît laissez-moi savoir l'algorithme correct.

void modify(vector<pair<int, int> > &f) 
{ 
    // sorting elements of each pair 
    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++) 
    { 
     if(it->first > it->second) 
     swap(it->first, it->second); 
    } 

    // sorting elements of set f 
    sort(f.begin(), f.end()); 
    reverse(f.begin(), f.end()); 

    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++) 
    { 
     int x, y; 
     x = it->first; 
     y = it->second; 

     for(int i = 0; i < n; i++) 
     if(x != i) 
     { 
      graph[x][i] = graph[y][i] = graph[x][i] + graph[y][i]; 
      graph[i][x] = graph[i][y] = graph[i][x] + graph[i][y]; 
     } 
    } 


    vector<bool> pos(n, false); // array of positions to be deleted 

    for(vector<pair<int, int> >::iterator it = f.begin(); it != f.end(); it++) 
     pos[it->second] = true; 

    // deleting rows 
    int count = 0; 
    for(int i = 0; i < n; i++) 
    { 
      for(int j = 0; j < n; j++) 
       graph[i-count][j] = graph[i][j]; 
      if(pos[i]) 
       count++; 
    } 

    // deleting columns 
    count = 0; 
    for(int j = 0; j < n; j++) 
    { 
      for(int i = 0; i < n; i++) 
       graph[i][j-count] = graph[i][j]; 
      if(pos[j]) 
       count++; 
    } 

    // finally dimension of the matrix becomes n - count 
    n = n - count; 
} 

Merci d'avance.

Answer 1

Étant donné le graphique exemple suivant:

a  d 
\ /
    b---e 
/ \ 
c  f

Est-ce que "contractant" le bord {b, e} les résultats suivants ?:

a d 
\/
    g 
/\ 
c f

"Oui, il est exactement cela" - amit. Thx, je voulais obtenir la spécification correcte, avant de répondre à votre question. D'autres hypothèses sont les suivantes:

• graphique est dirigé
• sommets sont représentés par des nombres entiers.
• Le graphique est stocké dans le tableau à deux dimensions , graph[x][y] étant le poids du bord (x, y); 0 indiquant qu'il n'y a pas de bord de x à y

permet de donner un essai avec quelques pseudocode:

void contractEdge(int v1, int v2) { 
    for (int i = 0; i < n; i++) { 
     if (graph[v2][i] > 0) { 
      graph[v1][i] = graph[v1][i] > 0 ? min(graph[v1][i], graph[v2][i]) : 
               graph[v2][i]; 
      graph[v2][i] = 0; 
     } 
     if (graph[i][v2] > 0) { 
      graph[i][v1] = graph[i][v1] > 0 ? min(graph[i][v1], graph[i][v2]) : 
               graph[i][v2]; 
      graph[i][v2] = 0; 
     } 
     graph[v1][v2] = graph[v2][v1] = 0; 
    } 
}

Le code fonctionne comme ceci: Compte tenu du bord {v1, v2}, v1 devient le vertex "contracté". Cela signifie qu'au lieu d'insérer un nouveau sommet ("g" dans mon premier exemple), v1 reste dans le graphe et v2 en est supprimé (en affectant 0 poids sur les arêtes à tous les autres sommets, le nombre de vertex réel ne change pas). De plus, toutes les arêtes qui contiennent v2 sont inclinées pour contenir v1.

Maintenant, on peut appeler cette méthode pour un ensemble d'arêtes. Le runtime sera O (n * #edges_to_contract). J'espère que c'est le comportement que vous souhaitiez.

Important: Si vous utilisez une représentation différente pour votre poids de pointe, à savoir 0 signifiant un bord avec 0 poids et ∞ (infini) indiquant l'absence d'un bord, alors votre problème devient trivial parce que tout ce que vous devez faire est:

graph[v1][v2] = graph[v2][v1] = 0

qui se contracte efficacement le bord {v1, v2}, puisque maintenant il ne coûte rien de se déplacer entre v1 et v2

Answer 2

C'est edge ne se contracte pas, mais les vertex contraction. Bien sûr, le bord reliant les sommets contractés disparaît et les poids des arêtes reliant les vertices d'origine à leurs voisins doivent être additionnés.