testing::internal::MaxBipartiteMatchState Class Reference

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

Private Member Functions
bool	TryAugment (size_t ilhs,::std::vector< char > *seen)
	GTEST_DISALLOW_ASSIGN_ (MaxBipartiteMatchState)
bool	TryAugment (size_t ilhs,::std::vector< char > *seen)
	GTEST_DISALLOW_ASSIGN_ (MaxBipartiteMatchState)
bool	TryAugment (size_t ilhs,::std::vector< char > *seen)
	GTEST_DISALLOW_ASSIGN_ (MaxBipartiteMatchState)

Private Attributes
const MatchMatrix *	graph_
::std::vector< size_t >	left_
::std::vector< size_t >	right_

Static Private Attributes
static const size_t	kUnused = static_cast<size_t>(-1)

Detailed Description

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

Constructor & Destructor Documentation

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

inlineexplicit

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

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

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

inlineexplicit

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

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

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

inlineexplicit

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

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

Member Function Documentation

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

inline

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

References graph_, GTEST_CHECK_, kUnused, and seen.

Referenced by testing::internal::FindMaxBipartiteMatching(), and TryAugment().

                                {
    // '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;
  }

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

inline

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

References graph_, GTEST_CHECK_, kUnused, and seen.

                                {
    // '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;
  }

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

inline

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

References graph_, GTEST_CHECK_, kUnused, and seen.

                                {
    // '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;
  }

testing::internal::MaxBipartiteMatchState::GTEST_DISALLOW_ASSIGN_ ( MaxBipartiteMatchState  )

private

testing::internal::MaxBipartiteMatchState::GTEST_DISALLOW_ASSIGN_ ( MaxBipartiteMatchState  )

private

testing::internal::MaxBipartiteMatchState::GTEST_DISALLOW_ASSIGN_ ( MaxBipartiteMatchState  )

private

bool testing::internal::MaxBipartiteMatchState::TryAugment ( size_t  ilhs, ::std::vector< char > *  seen  )

inlineprivate

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

References graph_.

                                                      {
    for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) {
      if ((*seen)[irhs])
        continue;
      if (!graph_->HasEdge(ilhs, irhs))
        continue;
      // There's an available edge from ilhs to irhs.
      (*seen)[irhs] = 1;
      // Next a search is performed to determine whether
      // this edge is a dead end or leads to the sink.
      //
      // right_[irhs] == kUnused means that there is residual flow from
      // right node irhs to the sink, so we can use that to finish this
      // flow path and return success.
      //
      // Otherwise there is residual flow to some ilhs. We push flow
      // along that path and call ourselves recursively to see if this
      // ultimately leads to sink.
      if (right_[irhs] == kUnused || TryAugment(right_[irhs], seen)) {
        // Add flow from left_[ilhs] to right_[irhs].
        left_[ilhs] = irhs;
        right_[irhs] = ilhs;
        return true;
      }
    }
    return false;
  }

bool testing::internal::MaxBipartiteMatchState::TryAugment ( size_t  ilhs, ::std::vector< char > *  seen  )

inlineprivate

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

References Compute(), testing::internal::FindMaxBipartiteMatching(), g(), graph_, GTEST_API_, GTEST_DISALLOW_ASSIGN_, and kUnused.

                                                      {
    for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) {
      if ((*seen)[irhs])
        continue;
      if (!graph_->HasEdge(ilhs, irhs))
        continue;
      // There's an available edge from ilhs to irhs.
      (*seen)[irhs] = 1;
      // Next a search is performed to determine whether
      // this edge is a dead end or leads to the sink.
      //
      // right_[irhs] == kUnused means that there is residual flow from
      // right node irhs to the sink, so we can use that to finish this
      // flow path and return success.
      //
      // Otherwise there is residual flow to some ilhs. We push flow
      // along that path and call ourselves recursively to see if this
      // ultimately leads to sink.
      if (right_[irhs] == kUnused || TryAugment(right_[irhs], seen)) {
        // Add flow from left_[ilhs] to right_[irhs].
        left_[ilhs] = irhs;
        right_[irhs] = ilhs;
        return true;
      }
    }
    return false;
  }

bool testing::internal::MaxBipartiteMatchState::TryAugment ( size_t  ilhs, ::std::vector< char > *  seen  )

inlineprivate

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

References Compute(), testing::internal::FindMaxBipartiteMatching(), g(), graph_, GTEST_API_, GTEST_DISALLOW_ASSIGN_, and kUnused.

                                                      {
    for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) {
      if ((*seen)[irhs])
        continue;
      if (!graph_->HasEdge(ilhs, irhs))
        continue;
      // There's an available edge from ilhs to irhs.
      (*seen)[irhs] = 1;
      // Next a search is performed to determine whether
      // this edge is a dead end or leads to the sink.
      //
      // right_[irhs] == kUnused means that there is residual flow from
      // right node irhs to the sink, so we can use that to finish this
      // flow path and return success.
      //
      // Otherwise there is residual flow to some ilhs. We push flow
      // along that path and call ourselves recursively to see if this
      // ultimately leads to sink.
      if (right_[irhs] == kUnused || TryAugment(right_[irhs], seen)) {
        // Add flow from left_[ilhs] to right_[irhs].
        left_[ilhs] = irhs;
        right_[irhs] = ilhs;
        return true;
      }
    }
    return false;
  }

Member Data Documentation

const MatchMatrix * testing::internal::MaxBipartiteMatchState::graph_

private

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

const size_t testing::internal::MaxBipartiteMatchState::kUnused = static_cast<size_t>(-1)

staticprivate

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

std::vector< size_t > testing::internal::MaxBipartiteMatchState::left_

private

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

std::vector< size_t > testing::internal::MaxBipartiteMatchState::right_

private

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

---

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

• proxygen/fizz/build_/gtest/src/gtest/googlemock/src/gmock-matchers.cc