Boost Graph 边缘比较不起作用
Boost Graph edge comparison not working
我正在尝试用图表做一些统计(比较 2 个图表)。但是当我比较边缘时遇到问题。
因此,我创建了两个带有一些边的图,然后创建了一些用于顶点和边操作的模板。对于顶点它工作得很好,但对于边缘它不能正常工作。
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/graph_utility.hpp>
typedef boost::adjacency_list < boost::vecS, boost::vecS,
boost::undirectedS > Graph;
template <typename T> std::set<T> operator-(const std::set<T>& a,
const std::set<T>& b)
{
std::set<T> r;
std::set_difference(
a.begin(), a.end(),
b.begin(), b.end(),
std::inserter(r, r.end()));
return r;
}
template <typename T> std::set<T> operator/(const std::set<T>& a,
const std::set<T>& b)
{
std::set<T> r;
std::set_intersection(
a.begin(), a.end(),
b.begin(), b.end(),
std::inserter(r, r.end()));
return r;
}
void compare(const Graph& a, const Graph& b)
{
std::set<Graph::vertex_descriptor > av, bv, samev, extrav, missingv;
std::set<Graph::edge_descriptor> ae, be, re, samee, extrae, missinge;
BGL_FORALL_VERTICES_T(v, a, Graph) av.insert(v);
BGL_FORALL_VERTICES_T(v, b, Graph) bv.insert(v);
samev = (av / bv);
extrav = (bv - av);
missingv = (av - bv);
BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e);
BGL_FORALL_EDGES_T(e, b, Graph) be.insert(e);
samee = (ae / be);
extrae = (be - ae);
missinge = (ae - be);
// TODO(silgon): reverse_graph
// boost::reverse_graph<Graph> r(b);
// BGL_FORALL_EDGES_T(e, r, Graph) re.insert(e);
std::cout << "---- Vertices ----\n"
<< "same: " << samev.size() << std::endl
<< "extra: " << extrav.size() << std::endl
<< "missing: " << missingv.size() << std::endl;
std::cout << "---- Edges ----\n"
<< "same: " << samee.size() << std::endl
<< "extra: " << extrae.size() << std::endl
<< "missing: " << missinge.size() << std::endl;
}
int main()
{
Graph a;
{
boost::graph_traits<Graph>::vertex_descriptor v, u, y;
u = boost::vertex(1, a);
v = boost::vertex(2, a);
y = boost::vertex(3, a);
boost::add_edge(u, v, a);
}
Graph b;
{
boost::graph_traits<Graph>::vertex_descriptor v, u, y;
u = vertex(1, b);
v = vertex(2, b);
y = vertex(3, b);
boost::add_edge(u, v, b);
boost::add_edge(y, v, b);
}
const char* name = "123456";
std::cout << "---Graph1---" << "\n";
boost::print_graph(a);
std::cout << "Edges: ";
boost::print_edges(a,name);
std::cout << "---Graph2---" << "\n";
boost::print_graph(b);
std::cout << "Edges: ";
boost::print_edges(b,name);
compare(a,b);
}
至于程序的结果如下:
---Graph1---
0 <-->
1 <--> 2
2 <--> 1
Edges: (2,3)
---Graph2---
0 <-->
1 <--> 2
2 <--> 1 3
3 <--> 2
Edges: (2,3) (4,3)
---- Vertices ----
same: 3
extra: 1
missing: 0
---- Edges ----
same: 0
extra: 2
missing: 1
您可以看到其中一条边是相同的 (2,3),但是在执行操作时它没有考虑到它,因此在结果中它显示 same:0,并且是多余的还是缺失的结果无效。
作为我的问题的临时解决方案,而不是:
std::set<Graph::edge_descriptor> ae
BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e)
我为边缘做了以下代码。
std::set<std::pair<unsigned long, unsigned long> > ae;
BGL_FORALL_EDGES_T(e, ga, Graph) gae.insert(std::make_pair(e.m_source,
e.m_target));
问题是提升图的边缘有 "m_eproperty",我真的不知道为什么会在那里,它包含像 0x125d0c0
这样的值。然后我根据边缘的源和目标创建了一对,然后我以与上面相同的方式(使用模板)进行评估。
深入研究 Boost 的 edge_descriptor
实现(在 boost/graph/detail/edge.hpp
中,我们发现每个边描述符都存储源和目标 vertex_descriptor
s,但也存储指向边的指针 属性。对于 vertex_descriptor
在其他方面相同的两条边,此指针不同。
这意味着您需要定义自己的 edge_descriptor
比较器,用于 std::set
和 set_intersection
/set_difference
操作,例如像这样:
struct edge_cmp
{
bool operator () (const Graph::edge_descriptor& a, const Graph::edge_descriptor& b) const
{
if (a.m_source < b.m_source) { return true; }
if (a.m_source > b.m_source) { return false; }
return (a.m_target < b.m_target);
}
};
必须将此类型的比较器对象传递给您构建的所有集合,以及 intersection/difference 调用。
I've forked your code on ideone 并进行了相应的修改。输出:
---- Vertices ----
same: 3
extra: 1
missing: 0
---- Edges ----
same: 1
extra: 1
missing: 0
我正在尝试用图表做一些统计(比较 2 个图表)。但是当我比较边缘时遇到问题。
因此,我创建了两个带有一些边的图,然后创建了一些用于顶点和边操作的模板。对于顶点它工作得很好,但对于边缘它不能正常工作。
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/graph_utility.hpp>
typedef boost::adjacency_list < boost::vecS, boost::vecS,
boost::undirectedS > Graph;
template <typename T> std::set<T> operator-(const std::set<T>& a,
const std::set<T>& b)
{
std::set<T> r;
std::set_difference(
a.begin(), a.end(),
b.begin(), b.end(),
std::inserter(r, r.end()));
return r;
}
template <typename T> std::set<T> operator/(const std::set<T>& a,
const std::set<T>& b)
{
std::set<T> r;
std::set_intersection(
a.begin(), a.end(),
b.begin(), b.end(),
std::inserter(r, r.end()));
return r;
}
void compare(const Graph& a, const Graph& b)
{
std::set<Graph::vertex_descriptor > av, bv, samev, extrav, missingv;
std::set<Graph::edge_descriptor> ae, be, re, samee, extrae, missinge;
BGL_FORALL_VERTICES_T(v, a, Graph) av.insert(v);
BGL_FORALL_VERTICES_T(v, b, Graph) bv.insert(v);
samev = (av / bv);
extrav = (bv - av);
missingv = (av - bv);
BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e);
BGL_FORALL_EDGES_T(e, b, Graph) be.insert(e);
samee = (ae / be);
extrae = (be - ae);
missinge = (ae - be);
// TODO(silgon): reverse_graph
// boost::reverse_graph<Graph> r(b);
// BGL_FORALL_EDGES_T(e, r, Graph) re.insert(e);
std::cout << "---- Vertices ----\n"
<< "same: " << samev.size() << std::endl
<< "extra: " << extrav.size() << std::endl
<< "missing: " << missingv.size() << std::endl;
std::cout << "---- Edges ----\n"
<< "same: " << samee.size() << std::endl
<< "extra: " << extrae.size() << std::endl
<< "missing: " << missinge.size() << std::endl;
}
int main()
{
Graph a;
{
boost::graph_traits<Graph>::vertex_descriptor v, u, y;
u = boost::vertex(1, a);
v = boost::vertex(2, a);
y = boost::vertex(3, a);
boost::add_edge(u, v, a);
}
Graph b;
{
boost::graph_traits<Graph>::vertex_descriptor v, u, y;
u = vertex(1, b);
v = vertex(2, b);
y = vertex(3, b);
boost::add_edge(u, v, b);
boost::add_edge(y, v, b);
}
const char* name = "123456";
std::cout << "---Graph1---" << "\n";
boost::print_graph(a);
std::cout << "Edges: ";
boost::print_edges(a,name);
std::cout << "---Graph2---" << "\n";
boost::print_graph(b);
std::cout << "Edges: ";
boost::print_edges(b,name);
compare(a,b);
}
至于程序的结果如下:
---Graph1---
0 <-->
1 <--> 2
2 <--> 1
Edges: (2,3)
---Graph2---
0 <-->
1 <--> 2
2 <--> 1 3
3 <--> 2
Edges: (2,3) (4,3)
---- Vertices ----
same: 3
extra: 1
missing: 0
---- Edges ----
same: 0
extra: 2
missing: 1
您可以看到其中一条边是相同的 (2,3),但是在执行操作时它没有考虑到它,因此在结果中它显示 same:0,并且是多余的还是缺失的结果无效。
作为我的问题的临时解决方案,而不是:
std::set<Graph::edge_descriptor> ae
BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e)
我为边缘做了以下代码。
std::set<std::pair<unsigned long, unsigned long> > ae;
BGL_FORALL_EDGES_T(e, ga, Graph) gae.insert(std::make_pair(e.m_source,
e.m_target));
问题是提升图的边缘有 "m_eproperty",我真的不知道为什么会在那里,它包含像 0x125d0c0
这样的值。然后我根据边缘的源和目标创建了一对,然后我以与上面相同的方式(使用模板)进行评估。
深入研究 Boost 的 edge_descriptor
实现(在 boost/graph/detail/edge.hpp
中,我们发现每个边描述符都存储源和目标 vertex_descriptor
s,但也存储指向边的指针 属性。对于 vertex_descriptor
在其他方面相同的两条边,此指针不同。
这意味着您需要定义自己的 edge_descriptor
比较器,用于 std::set
和 set_intersection
/set_difference
操作,例如像这样:
struct edge_cmp
{
bool operator () (const Graph::edge_descriptor& a, const Graph::edge_descriptor& b) const
{
if (a.m_source < b.m_source) { return true; }
if (a.m_source > b.m_source) { return false; }
return (a.m_target < b.m_target);
}
};
必须将此类型的比较器对象传递给您构建的所有集合,以及 intersection/difference 调用。
I've forked your code on ideone 并进行了相应的修改。输出:
---- Vertices ----
same: 3
extra: 1
missing: 0
---- Edges ----
same: 1
extra: 1
missing: 0