1

BGLのコンテキストでは、を繰り返す必要がありますin_edgesがout_edges、逆エッジの一部であるものを除外します。つまり、逆エッジの一部であるものを除外しますproperty_map。以下のコードは、私がやりたいことを示していますが、もちろん、メソッドはありproperty_mapません。findend

更新：考えられる解決策は、グラフの作成中に逆エッジを含むマップのような別の構造を維持することです。read_dimacs_max_flowこれは、グラフの作成を制御できた場合は機能しますが、関数を使用してDIMACS形式のグラフファイルを読み取るため、機能しません。だから私はBGLのアクセシビリティ方法だけに頼って何が何であるかを理解することができます。

グラフの定義：

typedef adjacency_list_traits<vecS, vecS, bidirectionalS> ttraits;  
typedef adjacency_list<vecS, vecS, bidirectionalS,
        // vertex properties
        property<vertex_index_t, int,
        property<vertex_color_t, default_color_type> >,
        // edge properties
        property<edge_capacity_t, int,
        property<edge_residual_capacity_t, int,
        property<edge_reverse_t, ttraits::edge_descriptor> > >, no_property, vecS> tbgl_adjlist_bidir;

typedef graph_traits<tbgl_adjlist_bidir>::vertex_descriptor     tvertex;
typedef graph_traits<tbgl_adjlist_bidir>::edge_descriptor       tedge;
typedef property_map<tbgl_adjlist_bidir, edge_capacity_t>::type tedge_capacity_map;
typedef property_map<tbgl_adjlist_bidir, edge_reverse_t>::type  treverse_edge_map;
typedef property_map<tbgl_adjlist_bidir, vertex_color_t>::type  tvertex_color_map;
typedef property_map<tbgl_adjlist_bidir, vertex_index_t>::type  tvertex_index_map;
typedef graph_traits<tbgl_adjlist_bidir>::vertex_iterator       tvertex_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::edge_iterator         tedge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::out_edge_iterator     tout_edge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::in_edge_iterator      tin_edge_iterator;

そして、私がやりたいことのスニペットの例（ただし、以下のエラーでコンパイルされません）：

tvertex_index_map indices = get(vertex_index, bgl_adjlist_bidir);
tedge_capacity_map capacities = get(edge_capacity, bgl_adjlist_bidir);
treverse_edge_map rev_edges = get(edge_reverse, bgl_adjlist_bidir);

// iterate all vertices in the right order
for (int current = 0; current < m_num_vertices; ++current) {
    printf("processing vertex=%d\n", current);
    tin_edge_iterator ei1, ei1_end;
    for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
        // exclude reverse edges <<<<<<<======= HOW DO I DO THIS??
        if (rev_edges.find(*ei1) != rev_edges.end()) {
            continue;
        }
        int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
        printf("in edge: %d <- %d \n", current, in);
    }
}

およびコンパイラエラー：

/Users/bravegag/code/fastcode_project/build_debug$ make 2> out ; grep -i "error" ./out
[  2%] Building CXX object CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:18: error: 'treverse_edge_map' has no member named 'find'
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:42: error: 'treverse_edge_map' has no member named 'end'
make[2]: *** [CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o] Error 1
make[1]: *** [CMakeFiles/submodularity.dir/all] Error 2
make: *** [all] Error 2
4

1 に答える 1

2

プロパティedge_reverseマップは、エッジ記述子をグラフの各エッジに関連付けます。したがって、「検索」関数は、すべてのエッジがそのプロパティマップに対応するエントリを持つため、意味がありません（このようなプロパティマップは必ずしもstd::mapオブジェクトとして実装されているわけではなく、実際にはそうではありません。内部プロパティの）。

できることとすべきことの1つは、各エッジのリバースエッジプロパティの値を、リバースエッジのエッジ記述子または無効なエッジ記述子（非リバースエッジの場合）になるように設定することです。次に、（「検索」の代わりに）チェックは、逆エッジプロパティが有効なエッジ記述子であるかどうかをチェックするためのチェックの1つにすぎません。

残念ながら、BGLはnull_edge()静的関数を提供しません（のようにnull_vertex()）。これはおそらく開発者による省略でした（私は独自のグラフ構造をいくつか開発し、null_edge()関数を含めましたが、Boostには含めませんでした）。これは、使用するための適切で移植性のある「ヌルエッジ」記述子値を思い付くのが難しい可能性があることを意味します。1つのオプションは、次のような特定のビットパターンを使用することです。

ttraits::edge_descriptor my_null_edge;
memset((char*)&my_null_edge, 0xFF, sizeof(ttraits::edge_descriptor));

次に、非逆エッジのすべての逆エッジプロパティがに設定されていることを確認してからmy_null_edge、次の比較を使用してループを実装します。

for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
    // exclude reverse edges
    if (rev_edges[*ei1] != my_null_edge) {
        continue;
    }
    int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
    printf("in edge: %d <- %d \n", current, in);
}

std::mapリバースエッジプロパティが非常にまばらな場合は、 （または）のようなマップクラスを使用して外部プロパティマップを作成することをお勧めしますstd::unordered_map。隣接リストクラステンプレートでEdgePropertyまたはVertexPropertyとして指定したものは、グラフの各頂点またはエッジの値（種類）ごとに格納されます。動作が必要な場合std::map（プロパティが割り当てられたサブセットのみを格納する）、隣接リストグラフの外部でこれを行うことができます。プロパティマップの優れた点は、内部プロパティに対応する必要がないことです。も便利です。だから、あなたはこれを行うことができます：

typedef std::map< tedge, tedge > treverse_edge_map;

treverse_edge_map rev_edges;

また、BGLプロパティマップとして使用する必要がある場合はrev_edges、次を使用できます。

typedef boost::associative_property_map< treverse_edge_map > tbgl_reverse_edge_map;

tbgl_reverse_edge_map bgl_rev_edges = boost::make_assoc_property_map(rev_edges);

ただし、もちろん、BGLスタイルのプロパティマップになると、「検索」メカニズムを使用して、特定のエッジにプロパティが設定されているかどうかを判断することはできなくなります。

于 2012-07-20T17:57:39.100 に答える