c++ - 实现一个高效的容器来存储图中的边

Question

我需要有效地定义 std::set<Edge> 上的顺序. Edge 表示图中的一条边(不是 multimap )。

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;

whether the std::set<Edge> contains an edge with given "from" and "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; 
}

edges that go from given "from" to some "to", where "to" is not inside a given set

假设函数是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"

Answer 1

邻接表

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;
}

一个有序集

这个比较符合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 的边都被删除/跳过，检查 e 是否出现在 exclude_edges 可以简单地通过将它与 exclude_edges 的第一个(最小)元素进行比较来完成。