graph - Graphlabs の Graphchi について: コミュニティ検出の例

Question

誰かが Graphchi を認識していて、communitydetection.cpp コードを理解しようとした場合、このコードが段階的に何をしているのかを理解するための助けが必要です。

 for(int i=0; i < vertex.num_edges(); i++) {
            bidirectional_label edgelabel = vertex.edge(i)->get_data();
            vid_t nblabel = neighbor_label(edgelabel, vertex.id(), vertex.edge(i)->vertex_id());
            std::map<vid_t, int>::iterator existing = counts.find(nblabel);
            int newcount = 0;
            if(existing == counts.end()) {
                counts.insert(std::pair<vid_t,int>(nblabel, 1));
                newcount = 1;
            } else {
                existing->second++;//map iterator
                newcount = existing->second;
            }
            if (newcount > maxcount || (maxcount == newcount && nblabel > maxlabel)) {
                maxlabel = nblabel;
                maxcount = newcount;
            }
        }
        newlabel = maxlabel;
    }

Answer 1

コミュニティ検出の例にコード コメントを追加しました: http://code.google.com/p/graphchi/source/browse/example_apps/communitydetection.cpp

          /* The basic idea is to find the label that is most popular among
           this vertex's neighbors. This label will be chosen as the new label
           of this vertex. */
        // This part could be optimized: STL map is quite slow.
        std::map<vid_t, int> counts;
        int maxcount=0;
        vid_t maxlabel=0;
        /* Iterate over all the edges */
        for(int i=0; i < vertex.num_edges(); i++) {
            /* Extract neighbor's current label. The edge contains the labels of
               both vertices it connects, so we need to use the right one. 
               (See comment for bidirectional_label above) */
            bidirectional_label edgelabel = vertex.edge(i)->get_data();
            vid_t nblabel = neighbor_label(edgelabel, vertex.id(), vertex.edge(i)->vertex_id());

            /* Check if this label (nblabel) has been encountered before ... */
            std::map<vid_t, int>::iterator existing = counts.find(nblabel);
            int newcount = 0;
            if(existing == counts.end()) {
                /* ... if not, we add this label with count of one to the map */
                counts.insert(std::pair<vid_t,int>(nblabel, 1));
                newcount = 1;
            } else {
                /* ... if yes, we increment the counter for this label by 1 */
                existing->second++;
                newcount = existing->second;
            }

            /* Finally, we keep track of the most frequent label */
            if (newcount > maxcount || (maxcount == newcount && nblabel > maxlabel)) {
                maxlabel = nblabel;
                maxcount = newcount;
            }
        }