1

我需要有效地在std::set<Edge>. 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. 这可能吗？

编辑：我想我应该使用mapormultimap而不是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;
}

一组有序

这更符合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。

于 2012-11-25T00:31:37.880 回答
0

出于什么原因，您应该为此类工作使用多图？我认为 Map 就足够了，如果我理解得很好，您不需要在图表上保留相同的节点。

如果您决定使用地图，很容易找到现有边缘以及您的第二个问题。您只需要搜索密钥并迭代您的地图。使用Set，元素以随机顺序插入，因此，这意味着您的搜索时间很长（O（N）。如果您将元素存储在地图中（我认为最好的方法是使用“from”作为键），插入将被订购，您的搜索使用 O(Log n) 的时间

如果您需要修改图表中的连接，如果它们在集合中，则无法修改集合元素，在地图中您可以。

于 2012-11-24T23:47:09.197 回答