Bibliothèque graphique Boost : insertion d'arêtes lente pour les grands graphes

Question

J'essaie d'utiliser un "ciseau intelligent" pour la segmentation interactive d'une image. Je dois donc créer un graphe orienté à partir d'une image où chaque sommet représente un seul pixel. Chaque sommet est ensuite relié à chacun de ses voisins par deux arêtes : une arête sortante et une arête entrante. Ceci est dû au fait que le coût d'une arête (a,b) peut être différent du coût de (b,a). J'utilise des images d'une taille de 512*512 pixels et je dois donc créer un graphe avec 262144 sommets et 2091012 arêtes. Actuellement, j'utilise le graphe suivant :

typedef property<vertex_index_t, int,
        property<vertex_distance_t, double,
        property<x_t, int, 
        property<y_t, int
        >>>> VertexProperty;

typedef property<edge_weight_t, double> EdgeProperty;

// define MyGraph
typedef adjacency_list<     
    vecS,           // container used for the out-edges (list)
    vecS,           // container used for the vertices (vector)
    directedS,      // directed edges (not sure if this is the right choice for incidenceGraph)
    VertexProperty,
    EdgeProperty
    > MyGraph;

J'utilise une classe supplémentaire Graphique (désolé pour le nom peu inspiré) qui gère le graphique :

class Graph
{
private:
    MyGraph *graph;
    property_map<MyGraph, vertex_index_t>::type indexmap;
    property_map<MyGraph, vertex_distance_t>::type distancemap;
    property_map<MyGraph, edge_weight_t>::type weightmap;
    property_map<MyGraph, x_t>::type xmap;
    property_map<MyGraph, y_t>::type ymap;
    std::vector<MyGraph::vertex_descriptor> predecessors;
public:
    Graph();
    ~Graph();

} ;

La création d'un nouveau graphe avec 262144 sommets est assez rapide, mais l'insertion des arêtes prend jusqu'à 10 secondes, ce qui est beaucoup trop lent pour l'application souhaitée. Pour l'instant, j'insère les arêtes de la manière suivante :

tie(vertexIt, vertexEnd) = vertices(*graph);
for(; vertexIt != vertexEnd; vertexIt++){
    vertexID = *vertexIt;
    x = vertexID % 512;
    y = (vertexID - x) / 512;
    xmap[vertexID] = x;
    ymap[vertexID] = y;
    if(y > 0){
        if(x > 0){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x-1)], *graph);    // upper left neighbour
        }
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x)], *graph);    // upper
        if(x < 511){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x+1)], *graph);    // upper right
        }
    }
    if(x < 511){    
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x+1)], *graph);    // right
    }
    if(y < 511){
        if(x > 0){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x-1)], *graph);    // lower left
        }
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x)], *graph);    // lower
        if(x < 511){
            tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x+1)], *graph);    // lower right
        }
    }
    if(x > 0){
        tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x-1)], *graph);    // left
    }
}

Y a-t-il quelque chose que je puisse faire pour améliorer la vitesse du programme ? J'utilise Microsoft Visual C++ 2010 Express en mode release avec optimisation (comme recommandé par Boost). J'ai pensé que je pourrais utiliser un listeS pour les sommets ou les arêtes, mais les sommets ne posent pas de problème et si j'utilise la fonction listeS pour les bords, il est encore plus lent.

Answer 1

adjacency_list est très général ; malheureusement, il ne sera jamais aussi efficace qu'une solution exploitant la régularité de votre cas d'utilisation particulier. BGL n'est pas magique.

La meilleure solution est probablement de trouver la représentation graphique efficace que vous utiliseriez en l'absence de BGL (indice : pour un graphique des pixels voisins d'une image, il s'agit de no va allouer explicitement tous ces objets nœuds et arêtes) et ensuite y adapter BGL ( exemple ) ou, de manière équivalente, de mettre en œuvre directement un équivalent de l'outil existant adjacency_list / adjacency_matrix modèles ( lignes directrices du concept ) en fonction de la régularité de votre système.

Par représentation optimisée, j'entends bien sûr une représentation dans laquelle vous ne stockez pas explicitement tous les nœuds et les arêtes, mais où vous disposez d'un moyen d'itérer sur des énumérations de nœuds et d'arêtes implicites résultant du fait que l'image est d'une taille particulière. La seule chose que vous devriez vraiment avoir besoin de stocker est un tableau de poids des arêtes.