Реализация эффективного контейнера для хранения ребер в графе
Мне нужно эффективно определить порядок на 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>содержит ребро с заданными «от» и «до» - ребра, которые идут от заданного «от» до некоторого «до», где «до» не находится внутри заданного
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>содержит ребро с заданным «от» и
«В»
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;
}
ребра, которые идут от заданного «от» до некоторого «до», где «до» не внутри
данный набор
в случае, если функция 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"Решение
Список смежности
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;
}
Один заказанный комплект
Это в большей степени согласуется с первоначальным запросом ОП, но я чувствую, что это намного хуже, чем другие варианты.
Я включил это только ради полноты.
// 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
Вместо того, чтобы фактически удалять края, которые больше не актуальны exclude_edges, версия C ++ использует итератор, чтобы запомнить, какие ребра в exclude_edges больше не актуальны (те, которые меньше всех интересующих сторон, которые еще предстоит изучить). После того, как все края в exclude_edges которые меньше чем e были удалены / пропущены, проверка, если e появляется в exclude_edges можно сделать, просто сравнив его с первым (наименьшим) элементом exclude_edges,
Другие решения
По какой причине вы должны использовать мультикарту для такого рода работы? Я думаю, что Map достаточно, если я хорошо понимаю, вам не нужно держать один и тот же узел на вашем графике.
Если вы решите использовать карту, легко найти существующее преимущество, а также ваш второй вопрос. Вам нужно только найти ключ и повторить вашу карту.
С помощью Set элементы вставляются в случайном порядке, поэтому это означает длительное время поиска (O (N).
Если вы сохраняете свои элементы на карте (я думаю, что лучше всего использовать «from» в качестве ключа), вставка будет упорядочена, ваш поиск использует время O (Log n)
Если вам нужно изменить соединения на вашем графике, элементы набора нельзя изменить, если они есть в наборе, на карте вы можете это сделать.