testing::internal::MaxBipartiteMatchState Class Reference

Public Member Functions
	MaxBipartiteMatchState (const MatchMatrix &graph)
ElementMatcherPairs	Compute ()

Detailed Description

Definition at line 121 of file gmock-matchers.cc.

Constructor & Destructor Documentation

MaxBipartiteMatchState()

testing::internal::MaxBipartiteMatchState::MaxBipartiteMatchState ( const MatchMatrix &  graph )

inlineexplicit

Definition at line 123 of file gmock-matchers.cc.

      : graph_(&graph),
        left_(graph_->LhsSize(), kUnused),
        right_(graph_->RhsSize(), kUnused) {}

Member Function Documentation

Compute()

ElementMatcherPairs testing::internal::MaxBipartiteMatchState::Compute ( )

inline

Definition at line 129 of file gmock-matchers.cc.

                                {
    // 'seen' is used for path finding { 0: unseen, 1: seen }.
    ::std::vector<char> seen;
    // Searches the residual flow graph for a path from each left node to
    // the sink in the residual flow graph, and if one is found, add flow
    // to the graph. It's okay to search through the left nodes once. The
    // edge from the implicit source node to each previously-visited left
    // node will have flow if that left node has any path to the sink
    // whatsoever. Subsequent augmentations can only add flow to the
    // network, and cannot take away that previous flow unit from the source.
    // Since the source-to-left edge can only carry one flow unit (or,
    // each element can be matched to only one matcher), there is no need
    // to visit the left nodes more than once looking for augmented paths.
    // The flow is known to be possible or impossible by looking at the
    // node once.
    for (size_t ilhs = 0; ilhs < graph_->LhsSize(); ++ilhs) {
      // Reset the path-marking vector and try to find a path from
      // source to sink starting at the left_[ilhs] node.
      GTEST_CHECK_(left_[ilhs] == kUnused)
          << "ilhs: " << ilhs << ", left_[ilhs]: " << left_[ilhs];
      // 'seen' initialized to 'graph_->RhsSize()' copies of 0.
      seen.assign(graph_->RhsSize(), 0);
      TryAugment(ilhs, &seen);
    }
    ElementMatcherPairs result;
    for (size_t ilhs = 0; ilhs < left_.size(); ++ilhs) {
      size_t irhs = left_[ilhs];
      if (irhs == kUnused) continue;
      result.push_back(ElementMatcherPair(ilhs, irhs));
    }
    return result;
  }

---

The documentation for this class was generated from the following file:

• /media/home/debian/src/github/tesseract-ocr/tesseract/unittest/third_party/googletest/googlemock/src/gmock-matchers.cc