lemon主要用于处理图论相关的算法，最短路径，最大流最小割。lemon代码库中大量使用模板，c++语言的black magic。躲病毒期间，对代码进行了阅读，将自己的理解记录在这里。
相关代码摘取自lemon中的dijkstra_test.cc。
图的表示方式：
char test_lgf[] =
"@nodes\n"
"label\n"
"0\n"
"1\n"
"2\n"
"3\n"
"4\n"
"@arcs\n"
" label length\n"
"0 1 0 1\n"
"1 2 1 1\n"
"2 3 2 1\n"
"0 3 4 5\n"
"0 3 5 10\n"
"0 3 6 7\n"
"4 2 7 1\n"
"@attributes\n"
"source 0\n"
"target 3\n";
阅读代码的目标，上述文本中表示edge长度的数据，是怎么解析到相应的数据结构中的？即下述run函数，怎么将数据处理到LengthMap中。
template <class Digraph>
void checkDijkstra() {
LengthMap length(G);
std::istringstream input(test_lgf);
digraphReader(G, input).
arcMap("length", length).
node("source", s).
node("target", t).
run();
}
文本中的"@arcs\n"一下的内容会在readArcs函数中处理。这里的map_num就是 表示的是" label length\n"这句话中token的个数。
void readArcs() {
while (readLine() && line >> c && c != '@') {
line.putback(c);
std::string source_token;
std::string target_token;
// the content in line,e,g: "0 1 0 1\n"
if (!_reader_bits::readToken(line, source_token))
throw FormatError("Source not found");
if (!_reader_bits::readToken(line, target_token))
throw FormatError("Target not found");
std::vector<std::string> tokens(map_num);
for (int i = 0; i < map_num; ++i) {
if (!_reader_bits::readToken(line, tokens[i])) {
std::ostringstream msg;
msg << "Column not found (" << i + 1 << ")";
throw FormatError(msg.str());
}
}
if (line >> std::ws >> c)
throw FormatError("Extra character at the end of line");
Arc a;
if (!_use_arcs) {
typename NodeIndex::iterator it;
it = _node_index.find(source_token);
if (it == _node_index.end()) {
std::ostringstream msg;
msg << "Item not found: " << source_token;
throw FormatError(msg.str());
}
Node source = it->second;
it = _node_index.find(target_token);
if (it == _node_index.end()) {
std::ostringstream msg;
msg << "Item not found: " << target_token;
throw FormatError(msg.str());
}
Node target = it->second;
a = _digraph.addArc(source, target);
if (label_index != -1)
_arc_index.insert(std::make_pair(tokens[label_index], a));
} else {
if (label_index == -1)
throw FormatError("Label map not found");
typename std::map<std::string, Arc>::iterator it =
_arc_index.find(tokens[label_index]);
if (it == _arc_index.end()) {
std::ostringstream msg;
msg << "Arc with label not found: " << tokens[label_index];
throw FormatError(msg.str());
}
a = it->second;
}
for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
_arc_maps[i].second->set(a, tokens[map_index[i]]);
}
}
if (readSuccess()) {
line.putback(c);
}
}
_arc_maps[i].second->set(a, tokens[map_index[i]])对arc与长度进行处理。_arc_maps就是在arcMap("length", length)注册的。
template <typename Map>
DigraphReader& arcMap(const std::string& caption, Map& map) {
checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
_reader_bits::MapStorageBase<Arc>* storage =
new _reader_bits::MapStorage<Arc, Map>(map);
_arc_maps.push_back(std::make_pair(caption, storage));
return *this;
}
MapStorage对象中对set函数进行追踪。
template <typename _Item, typename _Map,
typename _Converter = DefaultConverter<typename _Map::Value> >
class MapStorage : public MapStorageBase<_Item> {
public:
virtual void set(const Item& item ,const std::string& value) {
_map.set(_graph.direct(item, dir), _converter(value));
}
}
追踪LengthMap中的set函数。LengthMap的定义在lemon/bits/graph_extender.h
template <typename _Value>
class ArcMap
: public MapExtender<DefaultMap<Graph, Arc, _Value> >
template <typename _Graph, typename _Item, typename _Value>
class DefaultMap
: public DefaultMapSelector<_Graph, _Item, _Value>::Map
template <typename _Graph, typename _Item, typename _Value>
struct DefaultMapSelector {
typedef ArrayMap<_Graph, _Item, _Value> Map;
};
template <typename _Graph, typename _Item, typename _Value>
class ArrayMap
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
public:
const Value& operator[](const Key& key) const {
int id = Parent::notifier()->id(key);
return values[id];
}
void set(const Key& key, const Value& val) {
(*this)[key] = val;
}
private:
Value* values;// when this is allocated?
};
第二个问题出现，Value* values的内存空间是何时分配的？readArcs中的这句话a = _digraph.addArc(source, target)会通知(notifier)observer进行内存分配。这就是ArrayMap继承ObserverBase的作用。
class ListDigraph : public ExtendedListDigraphBase {
public:
Arc addArc(Node s, Node t) {
return Parent::addArc(s, t);
}
};
template <typename Base>
class DigraphExtender : public Base {
public:
Arc addArc(const Node& from, const Node& to) {
Arc arc = Parent::addArc(from, to);
notifier(Arc()).add(arc);
return arc;
}
typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
ArcNotifier& notifier(Arc) const {
return arc_notifier;
}
};
template <typename _Container, typename _Item>
class AlterationNotifier {
public:
void add(const Item& item) {
typename Observers::reverse_iterator it;
try {
for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
(*it)->add(item);
}
} catch (...) {
typename Observers::iterator jt;
for (jt = it.base(); jt != _observers.end(); ++jt) {
(*jt)->erase(item);
}
throw;
}
}
};
ArrayMap中的add函数进行内存分配。
template <typename _Graph, typename _Item, typename _Value>
class ArrayMap
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
protected:
// \brief Adds a new key to the map.
//
// It adds a new key to the map. It is called by the observer notifier
// and it overrides the add() member function of the observer base.
virtual void add(const Key& key) {
Notifier* nf = Parent::notifier();
int id = nf->id(key);
if (id >= capacity) {
int new_capacity = (capacity == 0 ? 1 : capacity);
while (new_capacity <= id) {
new_capacity <<= 1;
}
Value* new_values = allocator.allocate(new_capacity);
Item it;
for (nf->first(it); it != INVALID; nf->next(it)) {
int jd = nf->id(it);;
if (id != jd) {
allocator.construct(&(new_values[jd]), values[jd]);
allocator.destroy(&(values[jd]));
}
}
if (capacity != 0) allocator.deallocate(values, capacity);
values = new_values;
capacity = new_capacity;
}
allocator.construct(&(values[id]), Value());
}
};
这里分析的最短路径算法是dijkstra。这个算法里面的逻辑挺容易理解的。但是另一个最短路径算法floyd算法，代码五行，但是很不容易理解。
floyd算法
for(int k=1;k<=n;m++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
找了一些资料[2,3,4]，看了之后，也是迷迷糊糊的。
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
我觉得需要从这个推理公式理解，当k=1时，若在一次三层循环执行完毕后，Dis(i,1) + Dis(1,j) < Dis(i,j)成立，则i，j之间的最短路径必须进过m。接下来的循环就是遍历其他的k点，是否可以进一步使得i->1之间的距离进一步缩小（1->j同理）。
[1]lemon code
[2]最短路四大算法证明以及分析
[3]Floyd算法的证明
[4]最短路径—Dijkstra算法和Floyd算法
网友评论