1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
|
#ifndef GRAPH_NODE_HPP
#define GRAPH_NODE_HPP
#include <map>
#include <set>
#include <vector>
#include <iostream>
namespace graph
{
template<typename Value, typename Cost=long>
class Node
{
public:
typedef Value value_t;
typedef Cost cost_t;
typedef std::multimap<cost_t, std::pair<Node *, bool> > container_t;
typedef typename container_t::iterator iterator_t;
typedef typename container_t::const_iterator const_iterator_t;
typedef std::vector<std::pair<Node const *, cost_t> > path_t;
typedef std::set<Node const *> visited_t;
Node(Value const & val)
:value(val)
{}
virtual ~Node()
{
iterator_t it = _childs.begin();
while(it != _childs.end())
{
if(it->second.second) delete it->second.first;
++it;
}
}
Node * createChild (value_t const value, cost_t const & cost)
{
Node * node = new Node(value);
_childs.insert(std::make_pair(cost, std::make_pair(node, true)));
return node;
}
Node * addChild(Node * node, cost_t const & cost)
{
_childs.insert(std::make_pair(cost, std::make_pair(node, false)));
return node;
}
container_t const & getChilds() const
{
return _childs;
}
value_t value;
private:
container_t _childs;
};
template<typename Value, typename Cost>
void print(std::ostream & stream, Node<Value, Cost> const & node, long tabs, typename Node<Value, Cost>::visited_t & visited)
{
if(visited.find(&node)!=visited.end())
{
stream << node.value << " >>> " << std::endl;
}
else
{
stream << node.value << std::endl;
typename Node<Value, Cost>::const_iterator_t it = node.getChilds().begin();
while(it!=node.getChilds().end())
{
stream << std::string(tabs+1, '\t') << "(" << it->first << ") : ";
visited.insert(&node);
print(stream, *it->second.first, tabs+1, visited);
it++;
}
}
}
template<typename Value, typename Cost>
void print(std::ostream & stream, Node<Value, Cost> const & node)
{
typename Node<Value, Cost>::visited_t visited;
print(stream, node, 0, visited);
}
template<typename Node>
bool find(Node const & begin, Node const & end, typename Node::path_t & path, typename Node::visited_t & visited)
{
bool found = false;
if(&begin == &end)
{
found = true;
}
else
{
if(visited.find(&begin)==visited.end())
{
visited.insert(&begin);
typename Node::const_iterator_t it = begin.getChilds().begin();
while(it!=begin.getChilds().end() && !found)
{
path.push_back(std::make_pair(it->second.first, it->first));
found = find(*it->second.first, end, path, visited);
if(!found) path.pop_back();
it++;
}
}
}
return found;
}
template<typename Node>
bool find(Node const & begin, Node const & end, typename Node::path_t & path)
{
typename Node::visited_t visited;
path.clear();
path.push_back(std::make_pair(&begin, 0));
return find(begin, end, path, visited);
}
template<typename Path>
void print(std::ostream & stream, Path const & path)
{
typename Path::const_iterator it = path.begin();
while(it!=path.end())
{
stream << "(" << it->second << ") : " << it->first->value << std::endl;
++it;
}
}
template<typename Path, typename Cost>
Cost & cost(Path const & path, Cost & cost)
{
cost = Cost();
typename Path::const_iterator it = path.begin();
while(it!=path.end())
{
cost += it->second;
++it;
}
return cost;
}
}
#endif |
Partager