- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我一直在努力弄清楚如何做到这一点。我对快速找到图形的切割集很感兴趣。我知道 BGL 支持通过对 colorMap 参数的迭代来查找切割集,例如 edmonds_karp_max_flow。 Gomory Hu算法需要多次调用最小割算法。
我希望的结果是拥有一个包含以下内容的 multimap :(颜色,顶点)
以下代码尝试重写 Boost Graph 库中的示例,以将 multimap 用于 associative_property_map。编译代码可以通过以下方式完成:clang -lboost_graph -o edmonds_karp edmonds_karp.cpp或 g++ 而不是 clang。我没有得到由此产生的错误。
#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>
int main()
{
using namespace boost;
typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < listS, vecS, directedS,
property < vertex_name_t, std::string >,
property < edge_capacity_t, long,
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
Graph g;
property_map < Graph, edge_capacity_t >::type
capacity = get(edge_capacity, g);
property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
property_map < Graph, edge_residual_capacity_t >::type
residual_capacity = get(edge_residual_capacity, g);
std::multimap<default_color_type, Traits::vertex_descriptor> colorMap;
boost::associative_property_map< std::map<default_color_type,
Traits::vertex_descriptor> >
color_map(colorMap);
Traits::vertex_descriptor s, t;
read_dimacs_max_flow(g, capacity, rev, s, t);
std::vector<Traits::edge_descriptor> pred(num_vertices(g));
long flow = edmonds_karp_max_flow
(g, s, t, capacity, residual_capacity, rev,
make_iterator_property_map(color_map.begin()),
&pred[0]);
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::cout << "c flow values:" << std::endl;
graph_traits < Graph >::vertex_iterator u_iter, u_end;
graph_traits < Graph >::out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (capacity[*ei] > 0)
std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
<< (capacity[*ei] - residual_capacity[*ei]) << std::endl;
// if using the original example, unedited, this piece of code works
// BOOST_FOREACH(default_color_type x, color){
// std::cout << x << std::endl;
// }
return EXIT_SUCCESS;
}
将不胜感激提示。谢谢。
最佳答案
这是一个基于 Boost BiMap 的快速 PoC
typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
smart_map colorMap;
boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);
我从 http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm 中提取了一小部分样本你可以看到它 Live On Coliru ,输出:
c The total flow:
s 15
c flow values:
f 0 1 5
f 0 2 10
f 1 3 5
f 1 4 0
f 2 3 5
f 2 4 5
f 3 5 10
f 4 5 5
ltr: 0 -> 5
ltr: 4 -> 0
ltr: 0 -> 1
ltr: 4 -> 2
ltr: 0 -> 3
ltr: 0 -> 4
rtl: 0 -> 4
rtl: 1 -> 0
rtl: 2 -> 4
rtl: 3 -> 0
rtl: 4 -> 0
rtl: 5 -> 0
#include <boost/foreach.hpp>
#include <boost/bimap.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>
int main() {
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
listS, vecS, directedS, property<vertex_name_t, std::string>,
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, Traits::edge_descriptor> > > > Graph;
Graph g;
property_map<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g);
property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);
property_map<Graph, edge_residual_capacity_t>::type residual_capacity = get(edge_residual_capacity, g);
typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
smart_map colorMap;
boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);
Traits::vertex_descriptor s, t;
read_dimacs_max_flow(g, capacity, rev, s, t);
std::vector<Traits::edge_descriptor> pred(num_vertices(g));
long flow = edmonds_karp_max_flow(
g, s, t, capacity, residual_capacity, rev,
color_map, &pred[0]);
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::cout << "c flow values:" << std::endl;
graph_traits<Graph>::vertex_iterator u_iter, u_end;
graph_traits<Graph>::out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (capacity[*ei] > 0)
std::cout << "f " << *u_iter << " " << target(*ei, g) << " " << (capacity[*ei] - residual_capacity[*ei])
<< std::endl;
for (auto const& e : colorMap.left) std::cout << "ltr: " << e.first << " -> " << e.second << "\n";
for (auto const& e : colorMap.right) std::cout << "rtl: " << e.first << " -> " << e.second << "\n";
return EXIT_SUCCESS;
}
使用 Boost MultiIndex 创建双向映射:
struct VertexColor {
Traits::vertex_descriptor vertex;
boost::default_color_type color;
};
typedef boost::multi_index_container<
VertexColor,
bmi::indexed_by<
bmi::hashed_non_unique<bmi::tag<struct by_color>, bmi::member<VertexColor, boost::default_color_type, &VertexColor::color> >,
bmi::ordered_unique <bmi::tag<struct by_vertex>, bmi::member<VertexColor, Traits::vertex_descriptor, &VertexColor::vertex> >
>
> smart_map;
现在,使用 Boost Property Map 为 ReadWritePropertyMap
建模:
struct bidi_color_map {
typedef smart_map::index<by_vertex>::type impl_t;
bidi_color_map(impl_t& ref) : ref_(&ref) {}
impl_t &get() { return *ref_; }
impl_t const &get() const { return *ref_; }
private:
impl_t* ref_;
};
namespace boost {
template <> struct property_traits<bidi_color_map> {
typedef default_color_type value_type;
typedef default_color_type reference;
typedef Traits::vertex_descriptor key_type;
typedef read_write_property_map_tag category;
};
}
boost::property_traits<bidi_color_map>::reference get(bidi_color_map const& idx, boost::property_traits<bidi_color_map>::key_type const& key) {
auto it = idx.get().find(key);
if (it != idx.get().end())
return it->color;
else
throw std::range_error("key not found in index");
}
void put(bidi_color_map& idx, boost::property_traits<bidi_color_map>::key_type const& key, boost::property_traits<bidi_color_map>::value_type val) {
auto it = idx.get().find(key);
if (it != idx.get().end())
idx.get().modify(it, [val](VertexColor& p) { p.color = val; });
else
idx.get().insert({key,val});
}
现在您可以将其作为颜色图传递:
smart_map colorMap;
bidi_color_map color_map(colorMap.get<by_vertex>());
查看 Live On Coliru 还有
关于c++ - 图的切集,Boost Graph Library,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26697477/
我对这两个概念感到困惑:In-graph replication和 Between-graph replication阅读 Replicated training 时在 tensorflow 的官方
我对这两个概念感到困惑:In-graph replication和 Between-graph replication阅读 Replicated training 时在 tensorflow 的官方
我正在尝试使用 https://graph.windows.net/{teantId}/users/[email protected]/thumbnailPhoto?api-version=1.6 访
我正在尝试使用 Graphs.jl 模块从 Julia 中的图中获取子图。我有图,并将其顶点和边存储到列表中,然后我的算法在该列表中移动并删除不属于新子图的节点和边。到这一部分,一切正常,在整个算法之
我是 Arangodb 的新手。我对使用哪个图形 API 感到困惑。我可以在 http://localhost:8529/ url 看到一张图。官方视频讨论了 Gremlin(我也安装了它)。然后就是
截至今天,文档建议使用 Microsoft Graph 而不是 Azure AD Graph API 来访问 Azure AD/B2C 资源。 之前,通过 Azure AD Graph API,我们可
我们希望将 .NET 应用从使用 Azure AD Graph 迁移到 Microsoft Graph API。目前我们正在使用包 Microsoft.WindowsAzure.Configurati
也许我遗漏了什么,但我不知道为什么 GraphQL 的标题中有 graph。 我猜这与 Graph Theory 有关和 graph并且可以看到某种联系,但如果有人能用简单的术语解释它就太好了。 最佳
我正在尝试使用API使用户的Facebook Pages具有已关联的Instagram企业帐户: https://graph.facebook.com/v2.7/me/accounts?field
如何导出我通过调用 GraphPlot 获得的输出的调整大小版本 (或 TreePlot 如果它们产生不同的输出)到 jpg 文件? 目前,我只是调用 Export[file_name, G]在哪里
如何在使用 gremlin 查询创建边缘之前检查边缘是否已存在?如何更新现有边缘而不是删除并重新创建? 最佳答案 我不确定您是否还在寻找答案;然而,简单的答案是 Cosmos DB 在 Gremlin
我使用的是 Xcode 10.2.1 和 macOS Catalina Developer Beta 2。每当我尝试使用内存图调试器时,我都会收到此错误: Memory Graph Debugger:
我正在设置一个机器人以在Facebook页面上自动发布。但是,当我运行脚本时,图形API会引发以下错误: Graph returned an error: (#200) Requires either
如何制定包含非英语字符(例如日耳曼语Umlauts)的Microsoft Graph /myOrganization/users OData查询? 例子: 我的租户中有一个名为“ThomasMülle
我正在寻找发布目标帖子时可以与Facebook Graph API一起使用的国家/州/城市列表。 我在this页面上找到了一个JSON文件,但是该文件无法正确解析,我也怀疑它是否可以用于发布目标,因为
关于 Graph API,帖子的分享数、帖子见解的分享数和页面上显示的分享数不相同。我假设这些代表相同的计数。我的假设错了吗? 来自帖子: https://graph.facebook.com/XXX
我正在尝试访问作为嵌套子站点一部分的列表的项目,如下所示: https://{mytenant}.sharepoint.com/ vendorSiteCollection/ v
我打算开发一个应用程序,但开发人员告诉我每个 IP 每 600 秒有 600 次调用的限制。该应用程序有很多场景,这还不够。有没有办法以某种方式增加限制?或者 Facebook 是否提供任何高级帐户或
我在 Neo4j 中创建了一张伦敦地铁 map 。站点通过 :CONNECTED_TO 关系连接,时间值表示停止之间需要多长时间(目前这些是我为测试输入的随机值)。位于多条线路上的车站每条线路都有一个
我正在尝试拉回所有用户的列表,我的预期结果将是大约 20,000 个用户。 图表似乎将我限制为 1000。 图调用https://graph.microsoft.com/v1.0/users返回 10
我是一名优秀的程序员,十分优秀!