LEMON/LEMON-main Changeset - r330:5ba887b7def4

@@ -39,19 +39,19 @@

39

///

40

  /// \brief Edmonds' alternating forest maximum matching algorithm.

41

///

42

  /// This class provides Edmonds' alternating forest matching

43

  /// algorithm. The starting matching (if any) can be passed to the

44

  /// algorithm using some of init functions.

42

  /// This class implements Edmonds' alternating forest matching

43

  /// algorithm. The algorithm can be started from an arbitrary initial

44

  /// matching (the default is the empty one)

45

///

46

  /// The dual side of a matching is a map of the nodes to

46

  /// The dual solution of the problem is a map of the nodes to

47

  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c

48

  /// MATCHED/C showing the Gallai-Edmonds decomposition of the

49

  /// graph. The nodes in \c EVEN/D induce a graph with

50

  /// factor-critical components, the nodes in \c ODD/A form the

51

  /// barrier, and the nodes in \c MATCHED/C induce a graph having a

52

  /// perfect matching. The number of the fractor critical components

52

  /// perfect matching. The number of the factor-critical components

53

  /// minus the number of barrier nodes is a lower bound on the

54

  /// unmatched nodes, and if the matching is optimal this bound is

54

  /// unmatched nodes, and the matching is optimal if and only if this bound is

55

  /// tight. This decomposition can be attained by calling \c

56

  /// decomposition() after running the algorithm.

57

///

...

@@ -66,8 +66,7 @@

66

67

    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.

68

///

69

    ///Indicates the Gallai-Edmonds decomposition of the graph, which

70

    ///shows an upper bound on the size of a maximum matching. The

69

    ///Indicates the Gallai-Edmonds decomposition of the graph. The

71

70

    ///nodes with Status \c EVEN/D induce a graph with factor-critical

72

71

    ///components, the nodes in \c ODD/A form the canonical barrier,

73

72

    ///and the nodes in \c MATCHED/C induce a graph having a perfect

...

@@ -410,13 +409,13 @@

    /// \name Execution control

413

    /// The simplest way to execute the algorithm is to use the member

412

    /// The simplest way to execute the algorithm is to use the

414

413

    /// \c run() member function.

415

414

    /// \n

416

415

417

    /// If you need more control on the execution, first you must call

416

    /// If you need better control on the execution, you must call

418

417

    /// \ref init(), \ref greedyInit() or \ref matchingInit()

419

    /// functions, then you can start the algorithm with the \ref

418

    /// functions first, then you can start the algorithm with the \ref

420

419

    /// startParse() or startDense() functions.

    ///@{

...

@@ -433,9 +432,9 @@

    ///\brief Finds a greedy matching for initial matching.

435

    ///\brief Finds an initial matching in a greedy way

437

436

///

438

    ///For initial matchig it finds a maximal greedy matching.

437

    ///It finds an initial matching in a greedy way.

439

438

    void greedyInit() {

440

439

      createStructures();

441

440

      for (NodeIt n(_graph); n != INVALID; ++n) {

...

@@ -459,7 +458,7 @@

    /// \brief Initialize the matching from the map containing a matching.

461

    /// \brief Initialize the matching from a map containing.

463

462

///

464

463

    /// Initialize the matching from a \c bool valued \c Edge map. This

465

464

    /// map must have the property that there are no two incident edges

...

@@ -507,7 +506,7 @@

507

506

    /// \brief Starts Edmonds' algorithm.

508

507

///

509

508

    /// It runs Edmonds' algorithm with a heuristic of postponing

510

    /// shrinks, giving a faster algorithm for dense graphs.

509

    /// shrinks, therefore resulting in a faster algorithm for dense graphs.

511

510

    void startDense() {

512

511

      for(NodeIt n(_graph); n != INVALID; ++n) {

513

512

        if ((*_status)[n] == UNMATCHED) {

...

@@ -538,13 +537,13 @@

538

537

    /// @}

    /// \name Primal solution

541

    /// Functions for get the primal solution, ie. the matching.

540

    /// Functions to get the primal solution, ie. the matching.

    /// @{

544

543

545

    ///\brief Returns the size of the actual matching stored.

544

    ///\brief Returns the size of the current matching.

546

545

///

547

    ///Returns the size of the actual matching stored. After \ref

546

    ///Returns the size of the current matching. After \ref

548

547

    ///run() it returns the size of the maximum matching in the graph.

549

548

    int matchingSize() const {

550

549

      int size = 0;

...

@@ -583,7 +582,7 @@

583

582

    /// @}

    /// \name Dual solution

586

    /// Functions for get the dual solution, ie. the decomposition.

585

    /// Functions to get the dual solution, ie. the decomposition.

    /// @{

589

588

...

@@ -645,7 +644,7 @@

645

644

  /// be asked with \c matching() or mate() functions. The dual

646

645

  /// solution can be get with \c nodeValue(), \c blossomNum() and \c

647

646

  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt

648

  /// "BlossomIt" nested class which is able to iterate on the nodes

647

  /// "BlossomIt" nested class, which is able to iterate on the nodes

649

648

  /// of a blossom. If the value type is integral then the dual

650

649

  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".

651

650

  template <typename _Graph,

...

@@ -1630,7 +1629,7 @@

    /// \name Execution control

1633

    /// The simplest way to execute the algorithm is to use the member

1632

    /// The simplest way to execute the algorithm is to use the

1634

1633

    /// \c run() member function.

    ///@{

...

@@ -1791,13 +1790,13 @@

1791

1790

    /// @}

    /// \name Primal solution

1794

    /// Functions for get the primal solution, ie. the matching.

1793

    /// Functions to get the primal solution, ie. the matching.

    /// @{

1797

1796

1798

    /// \brief Returns the matching value.

1797

    /// \brief Returns the weight of the matching.

1799

1798

///

1800

    /// Returns the matching value.

1799

    /// Returns the weight of the matching.

1801

1800

    Value matchingValue() const {

1802

1801

      Value sum = 0;

1803

1802

      for (NodeIt n(_graph); n != INVALID; ++n) {

...

@@ -1848,7 +1847,7 @@

1848

1847

    /// @}

    /// \name Dual solution

1851

    /// Functions for get the dual solution.

1850

    /// Functions to get the dual solution.

    /// @{

1854

1853

...

@@ -1898,17 +1897,17 @@

1898

1897

      return _blossom_potential[k].value;

    /// \brief Lemon iterator for get the items of the blossom.

1900

    /// \brief Iterator for obtaining the nodes of the blossom.

1902

1901

///

1903

    /// Lemon iterator for get the nodes of the blossom. This class

1904

    /// provides a common style lemon iterator which gives back a

1902

    /// Iterator for obtaining the nodes of the blossom. This class

1903

    /// provides a common lemon style iterator for listing a

1905

1904

    /// subset of the nodes.

1906

1905

    class BlossomIt {

1907

1906

    public:

      /// \brief Constructor.

1910

1909

///

1911

      /// Constructor for get the nodes of the variable.

1910

      /// Constructor to get the nodes of the variable.

1912

1911

      BlossomIt(const MaxWeightedMatching& algorithm, int variable)

1913

1912

        : _algorithm(&algorithm)

1914

1913

...

@@ -2817,7 +2816,7 @@

    /// \name Execution control

2820

    /// The simplest way to execute the algorithm is to use the member

2819

    /// The simplest way to execute the algorithm is to use the

2821

2820

    /// \c run() member function.

    ///@{

...

@@ -2955,7 +2954,7 @@

2955

2954

    /// @}

    /// \name Primal solution

2958

    /// Functions for get the primal solution, ie. the matching.

2957

    /// Functions to get the primal solution, ie. the matching.

    /// @{

2961

2960

...

@@ -2996,7 +2995,7 @@

2996

2995

    /// @}

    /// \name Dual solution

2999

    /// Functions for get the dual solution.

2998

    /// Functions to get the dual solution.

    /// @{

3002

3001

...

@@ -3046,17 +3045,17 @@

3046

3045

      return _blossom_potential[k].value;

    /// \brief Lemon iterator for get the items of the blossom.

3048

    /// \brief Iterator for obtaining the nodes of the blossom.

3050

3049

///

3051

    /// Lemon iterator for get the nodes of the blossom. This class

3052

    /// provides a common style lemon iterator which gives back a

3050

    /// Iterator for obtaining the nodes of the blossom. This class

3051

    /// provides a common lemon style iterator for listing a

3053

3052

    /// subset of the nodes.

3054

3053

    class BlossomIt {

3055

3054

    public:

      /// \brief Constructor.

3058

3057

///

3059

      /// Constructor for get the nodes of the variable.

3058

      /// Constructor to get the nodes of the variable.

3060

3059

      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)

3061

3060

        : _algorithm(&algorithm)

3062

3061

RhodeCode

Login to your account