c++ - 在无向图上设置值

Question

我有一个在节点上有值的图

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;
          }

我会感兴趣:

• 能否使集合比较更有效
• 其他算法/想法
• 最好不要使用连通分量的概念，一些节点获取的值与其他节点不同

谢谢

Answer 1

您实际上是在计算连通分量，但效率非常低。由于您的答案确实取决于连接的组件，因此您不太可能找到不使用它们的算法。

好消息是连通分量可以以非常快速和高效的方式计算，参见 Boost.Graph 库中的示例:http://www.boost.org/doc/libs/1_55_0/libs/graph/example/connected_components.cpp

你的整个流程可能是:

1. numComponents = boost::connected_components(G, componentsMap);
2. vector allValues(numComponents);
3. 一次传递 componentsMap 来填充 allValues
4. 一次传递 allValues 以将它们与顶点相关联

复杂度几乎是线性 w.r.t.到图形大小。