1

の順序を効率的に定義する必要がありますstd::set<Edge>。エッジは、グラフのエッジを表します（マルチグラフではありません）。

class Edge
    {
        friend class Graph;
        string from;
        string to;
        EdgeInfo edge_length; //constructor is `EdgeInfo(int edge_length)`
    public:
        bool operator==(const Edge& rhs) {
            return (from==rhs.from && to==rhs.to);               
        }
    };

問題は効率的に見つけることです

  • std::set<Edge>に「from」と「to」が指定されたエッジが含まれているかどうか
  • 指定された「from」からいくつかの「to」に移動するエッジ。「to」は指定された内部にありません。set<string>

とを使用std::set.count()しstd::set.find()ます。で適切な順序を定義する必要がありますstd::set。これは可能ですか？

編集：私は私が使用するべきだった、mapまたはmultimapの代わりに考えましsetた。最終的に私は使用しmapました。このソリューションは、@tomの使用提案に触発されていますmap of maps。

解決策：

typedef int EdgeInfo; //just for the sake of this example (EdgeInfo can be length,price,...) 
map< string, map<string, EdgeInfo> > edges;

std::set<Edge>に「from」と「to」が指定されたエッジが含まれているかどうか

if (edges.count(from)!=0 && edges[from].count(to)!=0) {
        return true; 
}

または関数がconst

if (edges.count(from)!=0 && ((edges.find(top.second))->second).count(to)!=0) {
        return true; 
}

指定された「from」からいくつかの「to」に移動するエッジ。「to」は指定されたセット内にありません。

関数がconst

//if there are any edges from "from"
if (edges.count(from)!=0) {  

    //iterate over all edges from "from"
    for (map<string,EdgeInfo>::const_iterator
                 edge=((edges.find(from))->second).begin();
                 edge!=((edges.find(from))->second).end();
                 ++edge) {

        //if the edge goes to some vertex V that has not been discarded
        if (discarded.count(edge->first)==0) { //edge->first means "to"
4

2 に答える 2

3

隣接リスト

map< string, set<string> > edges;
// edges["a"] is the set of all nodes that can be reached from "a"

// O(log n)
bool exists(string from, string to)
{
    return edges[from].count(to) > 0;
}

// Ends of edges that start at 'from' and do not finish in 'exclude', O(n)
set<string> edgesExcept(string from, set<string>& exclude)
{
    set<string>& fromSet = edges[from];
    set<string> results;
    // set_difference from <algorithm>, inserter from <iterator>
    set_difference(fromSet.begin(), fromSet.end(),
            exclude.begin(), exclude.end(),
            inserter(results, results.end()));
    return results;
}

隣接行列

map< string, map<string, Edge*> > edgesMatrix;
// edgesMatrix["a"]["b"] is the Edge* from "a" to "b"
// e.g. Edge* e = new Edge(...); edgesMatrix[e->from][e->to] = e;

bool exists(string from, string to)
{
    return edgesMatrix[from].count(to) > 0;
}

vector<Edge*> edgesExcept(string from, set<string>& exclude)
{
    map<string, Edge*>& all = edgesMatrix[from];
    vector<Edge*> results;

    map<string, Edge*>::iterator allIt = all.begin();
    set<string>::iterator excludeIt = exclude.begin();

    while (allIt != all.end())
    {
        while (excludeIt != exclude.end() && *excludeIt < allIt->first)
        {
            ++excludeIt;
        }

        if (excludeIt == exclude.end() || allIt->first < *excludeIt)
        {
            results.push_back(allIt->second);
        }
        ++allIt;
    }

    return results;
}

1つの注文セット

これはOPの当初の要求に沿ったものですが、他のオプションよりもはるかに醜い感じがします。
完全を期すためにのみこれを含めました。

// sorted first by 'from', then by 'to'
class Edge {
    // ...
public:
    bool operator<(const Edge& r) const {
        return from < r.from || (from == r.from && to < r.to);
    }
};

set<Edge> edges;

bool exists(string from, string to) {
    Edge temp(from, to, -1);
    return edges.count(temp) > 0;
}

set<Edge> edgesExcept(string from, set<string>& exclude) {
    Edge first = Edge(from, "", -1); // ugly hack: "" sorts before other to's
    set<Edge> results;

    set<Edge>::iterator allIt = edges.lower_bound(first);
    set<string>::iterator excludeIt = exclude.begin();

    while (allIt != edges.end() && allIt->from == from) {
        while (excludeIt != exclude.end() && *excludeIt < allIt->to) {
            ++excludeIt;
        }
        if (excludeIt == exclude.end() || allIt->to < *excludeIt) {
            results.insert(results.end(), *allIt);
        }
        ++allIt;
    }
    return results;
}

の説明edgesExcept()

擬似コードバージョンは次のとおりです。

for each edge e in edges_of_interest (in sorted order)
    get rid of edges in exclude_edges that sort before e
    if e is equal to the first edge in exclude_edges
        e is in exclude_edges, so
        ignore e (i.e. do nothing)
    otherwise
        e is not in exclude_edges, so
        add e to good_edges

C ++バージョンでは、関連性がなくなったエッジを実際に削除する代わりにexclude_edges、イテレータを使用して、exclude_edges関連性がなくなったエッジ（まだ調べられていないすべての対象エッジよりも小さいエッジ）を記憶します。その中のすべてのエッジが削除/スキップされexclude_edgesたものよりも小さい場合、に表示されるeかどうかのチェックは、の最初の（最小の）要素と比較するだけで実行できます。eexclude_edgesexclude_edges

于 2012-11-25T00:31:37.880 に答える
0

この種の作業には、どのような理由でマルチマップを使用する必要がありますか？マップで十分だと思います。よく理解していれば、グラフ上で同じノードを維持する必要はありません。

マップを使用する場合は、既存のエッジと2番目の質問を簡単に見つけることができます。キーを検索してマップを繰り返すだけです。Setを使用すると、要素がランダムな順序で挿入されるため、検索に時間がかかります（O（N）。要素をマップに保存する場合（「from」をキーとして使用するのが最善の方法だと思います）、挿入が注文され、検索ではO（Log n）の時間が使用されます

グラフ内の接続を変更する必要がある場合、セット内にある場合はセット要素を変更できません。マップ内では変更できます。

于 2012-11-24T23:47:09.197 に答える