Hi Lars,
Lars Gullik Bjønnes wrote:
> Hmm...
>
> Why use back_inserter?
That's the point, I cannot. I want to copy a set to a queue, and I was
looking for the std:: way to do it. I was surprised by the fact that
std::copy would work for copying a set to a list, vector or map, but not to
a queue.
> std::queue<int> q;
> std::foreach(c.begin(), c.end(), boost::bind(&std::queue<int>::push, &q,
> _1));
>
> I wonder if this would work...
I was looking to something like this indeed, thanks.
So there's no simple way using the standard template library?
> But it is hard to tell the correct approach if we do not know what you
> indend to do with the queue.
I am trying to revamp a little converter.[Ch]. So far I've splitted it up
into converter.[Ch] + format.[Ch] + graph.[Ch].
Now I'm working on graph.[Ch], I want to clean it from lyx-specific code
(that should go to converter.C) and to add weights to the shortpath search
(to give preferences to converters, by speed or accuracy). The particular
piece of code in question was:
Graph::IntSet const
Graph::bfsOut(IntSet s) const
{
std::queue<int> q;
IntSet::const_iterator it = s.begin();
IntSet::const_iterator end = s.end();
for(; it != end; ++it) {
q.push(*it);
}
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ up to here
while(!q.empty()) {
int const v = q.front();
q.pop();
vector<int>::const_iterator cit =
vertices_[v].out_vertices.begin();
vector<int>::const_iterator end =
vertices_[v].out_vertices.end();
for (; cit != end; ++cit) {
if(s.insert(*cit).second) {
q.push(*cit);
}
}
}
return s;
}
I'm attaching also the full graph.[Ch]. I would be very thanksful for
corrections, advices and/or coments of any type.
Note that modifications to converter.C, format.C are missing so this
obviously doesn't work at all with current cvs.
Thanks,
Alfredo
/**
* \file graph.C
* This file is part of LyX, the document processor.
* Licence details can be found in the file COPYING.
*
* \author Dekel Tsur
* \author André Poënitz
* \author Alfredo Braunstein
*
* Full author contact details are available in file CREDITS
*/
#include <config.h>
#include "graph.h"
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using std::vector;
Graph::IntSet const
Graph::bfsOut(IntSet s) const
{
std::queue<int> q;
IntSet::const_iterator it = s.begin();
IntSet::const_iterator end = s.end();
for(; it != end; ++it) {
q.push(*it);
}
while(!q.empty()) {
int const v = q.front();
q.pop();
vector<int>::const_iterator cit =
vertices_[v].out_vertices.begin();
vector<int>::const_iterator end =
vertices_[v].out_vertices.end();
for (; cit != end; ++cit) {
if(s.insert(*cit).second) {
q.push(*cit);
}
}
}
return s;
}
Graph::IntSet const
Graph::bfsIn(IntSet s) const
{
std::queue<int> q;
IntSet::const_iterator it = s.begin();
IntSet::const_iterator end = s.end();
for(; it != end; ++it) {
q.push(*it);
}
while(!q.empty()) {
int const v = q.front();
q.pop();
vector<int>::const_iterator cit =
vertices_[v].in_vertices.begin();
vector<int>::const_iterator end =
vertices_[v].in_vertices.end();
for (; cit != end; ++cit) {
if(s.insert(*cit).second) {
q.push(*cit);
}
}
}
return s;
}
Graph::IntSet const
Graph::getReachableTo(int to) const
{
IntSet t;
t.insert(to);
return bfsIn(t);
}
Graph::IntSet const
Graph::getReachableTo(IntSet to) const
{
return bfsIn(to);
}
Graph::IntSet const
Graph::getReachableFrom(IntSet from) const
{
return bfsOut(from);
}
bool Graph::isReachable(int from, int to) const
{
IntSet f;
f.insert(from);
return bfsOut(f).count(to);
}
Graph::PathSet const
Graph::shortPathsTo(IntSet const & to, vector<int> const & W) const
{
const double infty = 1e30;
vector<double> h(vertices_.size()); //costs
std::fill(h.begin(), h.end(), infty);
PathSet p;
//nodes already seen
IntSet U(to);
//adjust cost in U and neighbors.
IntSet::iterator sit = U.begin();
IntSet::iterator send = U.end();
for (; sit != send; ++sit) {
h[*sit] = 0;
int const v = *sit;
vector<int>::const_iterator
cit = vertices_[v].in_vertices.begin();
vector<int>::const_iterator
cend = vertices_[v].in_vertices.end();
vector<int>::const_iterator
eit = vertices_[v].in_edges.begin();
for (; cit != cend; ++cit, ++eit) {
if (W[*eit] < h[*cit]) {
h[*cit] = W[*eit];
}
}
}
while (true) {
double hmin = infty;
int v;
vector<double>::iterator hit = h.begin();
vector<double>::iterator hend = h.end();
//v = (adyacent) node with min cost
for (int i = 0; hit != hend; ++i, ++hit) {
if( *hit < hmin && !U.count(i) ) {
hmin = *hit;
v = i;
}
}
//end of the course
if(hmin == infty)
break;
U.insert(v);
//adjust cost in neighbors of v
vector<int>::const_iterator
cit = vertices_[v].in_vertices.begin();
vector<int>::const_iterator
cend = vertices_[v].in_vertices.end();
vector<int>::const_iterator
eit = vertices_[v].in_edges.begin();
for (; cit != cend; ++cit, ++eit) {
double const c = W[*eit] + h[v];
if (! U.count(*cit) && c < h[*cit]) {
h[*cit] = c;
p[*cit] = pair<int,int>(v,*eit);
}
}
}
return p;
}
Graph::EdgePath const
Graph::buildPath(int from, PathSet const & p) const
{
EdgePath r;
PathSet::const_iterator it;
do {
it = p.find(from);
r.push_back(it->first.second);
} while (it != p.end());
return r;
}
Graph::EdgePath const
Graph::getPath(int from, int to, vector<int> const & W) const
{
IntSet toSet;
toSet.insert(to);
return buildPath(from, shortPathsTo(toSet, W));
}
Graph::EdgePath const
Graph::getPath(int from, IntSet to, vector<int> const & W) const
{
return buildPath(from, shortPathsTo(to, W));
}
void Graph::init(int size)
{
vertices_ = vector<Vertex>(size);
}
void Graph::addEdge(int s, int t, int id)
{
vertices_[t].in_vertices.push_back(s);
vertices_[s].out_vertices.push_back(t);
vertices_[t].in_edges.push_back(id);
}
// -*- C++ -*-
#ifndef GRAPH_H
#define GRAPH_H
/**
* \file graph.h
* This file is part of LyX, the document processor.
* Licence details can be found in the file COPYING.
*
* \author Dekel Tsur
* \author André Poënitz
* \author Alfredo Braunstein
*
* Full author contact details are available in file CREDITS
*/
#include <queue>
#include <vector>
#include <set>
#include <map>
class Graph {
public:
typedef std::set<int> IntSet;
typedef std::vector<int> EdgePath;
typedef std::map<int,pair<int,int> > PathSet;
Graph() {};
///
const IntSet
getReachableTo(int to) const;
///
const IntSet
getReachableTo(IntSet To) const;
///
const IntSet
getReachableFrom(int from) const;
///
const IntSet
getReachableFrom(IntSet From) const;
///
bool isReachable(int from, int to) const;
///
EdgePath const
getPath(int from, int to, vector<int> const & W) const;
///
EdgePath const
getPath(int from, IntSet to, vector<int> const & W) const;
///
void addEdge(int from, int to, int id);
///
void init(int size);
private:
///
IntSet const bfsOut(IntSet s) const;
///
IntSet const bfsIn(IntSet s) const;
///
PathSet const
shortPathsTo(IntSet const & to, vector<int> const & W) const;
///
EdgePath const
buildPath(int from, PathSet const & p) const;
///
struct Vertex {
std::vector<int> in_vertices;
std::vector<int> out_vertices;
std::vector<int> in_edges;
};
///
std::vector<Vertex> vertices_;
};
#endif //GRAPH_H
