我有一个在节点上有值的图
value = A/B/C
values = { A , B , C }
目标:连接的节点必须在稳定后具有相同的值:
示例:
Pre settling :
node1 = { A, B }
node2 = { A, B, C }
node3 = { D }
Post settling :
node1 = { A, B ,C, D }
node2 = { A, B ,C, D }
node3 = { A, B ,C, D }
稳定算法:
制作成对的节点 (node1, node2) , (node2, node3) 等
didSomething = false
doWhile ( didSomething )
for ( iterate all pairs )
didSomething |= settle ( a-pair )
如果 ( node1.values != node2.values ) didSomething 为真
问题:某些图形集需要很长时间才能确定。
最好不要使用连接组件的想法,一些节点获取的值与其他节点不同
> **gprof** > > SkipAcrossBlocks::PortSpreader::settle() [12] [13] 56.1 0.09 > 48.77 7367012 SkipAcrossBlocks::EdgePair::settle() [13] > 0.03 45.78 7367012/7367012 bool std::operator= > <SkipAcrossBlocks::OneJumpRecord, > std::less<SkipAcrossBlocks::OneJumpRecord>, > std::allocator<SkipAcrossBlocks::OneJumpRecord> > >(std::set<SkipAcrossBlocks::OneJumpRecord, > std::less<SkipAcrossBlocks::OneJumpRecord>, > std::allocator<SkipAcrossBlocks::OneJumpRecord> > const&, > std::set<SkipAcrossBlocks::OneJumpRecord, > std::less<SkipAcrossBlocks::OneJumpRecord>, > std::allocator<SkipAcrossBlocks::OneJumpRecord> > const&) [14]
SkipAcrossBlocks::OneJumpRecord = "value"
std::set < SkipAcrossBlocks::OneJumpRecord > " values "
gprof 说
7*10^6 调用以比较“值”的相等性
占用大部分时间。
为了完整性而设置一对节点:
bool EdgePair::settle() {
// if edge is internalRailORglobal should not aquire other rails
if ( edge1->cannotAquire() && edge2->cannotAquire() ) {
return false;
}
else if ( !edge1->cannotAquire() && edge2->cannotAquire() ) {
if ( edge1->superSetOf( edge2 )) {
return false;
}
edge1->spreadValues.insert( edge2->spreadValues.begin(), edge2->spreadValues.end());
return true;
}
else if ( edge1->cannotAquire() && !edge2->cannotAquire() ) {
if ( edge2->superSetOf( edge1 )) {
return false;
}
edge2->spreadValues.insert( edge1->spreadValues.begin(), edge1->spreadValues.end());
return true;
}
else {
// neither are internalORglobal
if ( edge1->spreadValues == edge2->spreadValues ) {
return false;
}
edge1->spreadValues.insert( edge2->spreadValues.begin(), edge2->spreadValues.end());
edge2->spreadValues = edge1->spreadValues;
return true;
}
}
下面的相等比较似乎是比较花时间的:
if ( edge1->spreadValues == edge2->spreadValues ) {
return false;
}
我会感兴趣:
- 能否使集合比较更有效
- 其他算法/想法
- 最好不要使用连通分量的概念,一些节点获取的值与其他节点不同
谢谢
最佳答案
您实际上是在计算连通分量,但效率非常低。由于您的答案确实取决于连接的组件,因此您不太可能找到不使用它们的算法。
好消息是连通分量可以以非常快速和高效的方式计算,参见 Boost.Graph 库中的示例:http://www.boost.org/doc/libs/1_55_0/libs/graph/example/connected_components.cpp
你的整个流程可能是:
- numComponents = boost::connected_components(G, componentsMap);
- vector allValues(numComponents);
- 一次传递 componentsMap 来填充 allValues
- 一次传递 allValues 以将它们与顶点相关联
复杂度几乎是线性 w.r.t.到图形大小。
关于c++ - 在无向图上设置值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23941230/