Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Graph Algorithms

Collaboration diagram for Graph Algorithms:


Detailed Description

This group describes the several graph algorithms implemented in LEMON.


Files

file  max_matching.h
 Maximum matching algorithm.

Modules

 General Graph Utilities
 This group describes some simple general graph utilities.
 Path and Flow Algorithms
 This group describes the algorithms for finding paths and flows in graphs.
 Minimum Cost Spanning Tree Algorithms
 This group containes the algorithms for finding a minimum cost spanning tree in a graph.

Classes

class  MaxMatching
 Edmonds' alternating forest maximum matching algorithm. More...

Functions

void lemon::MaxMatching::run ()
 Runs Edmonds' algorithm.
void lemon::MaxMatching::runEdmonds (int heur)
 Runs Edmonds' algorithm.
void lemon::MaxMatching::greedyMatching ()
 Finds a greedy matching starting from the actual matching.
int lemon::MaxMatching::size () const
 Returns the size of the actual matching stored.
void lemon::MaxMatching::resetMatching ()
 Resets the actual matching to the empty matching.


Function Documentation

void run  )  [inline, inherited]
 

Runs Edmonds' algorithm for sparse graphs (number of edges < 2*number of nodes), and a heuristical Edmonds' algorithm with a heuristic of postponing shrinks for dense graphs.

Definition at line 279 of file max_matching.h.

Here is the call graph for this function:

void runEdmonds int  heur  )  [inherited]
 

If heur=0 it runs Edmonds' algorithm. If heur=1 it runs Edmonds' algorithm with a heuristic of postponing shrinks, giving a faster algorithm for dense graphs.

Definition at line 288 of file max_matching.h.

Here is the call graph for this function:

void greedyMatching  )  [inherited]
 

Starting form the actual matching stored, it finds a maximal greedy matching.

Definition at line 452 of file max_matching.h.

int size  )  const [inherited]
 

Returns the size of the actual matching stored. After run() it returns the size of a maximum matching in the graph.

Definition at line 467 of file max_matching.h.

void resetMatching  )  [inherited]
 

Resets the actual matching to the empty matching.

Definition at line 478 of file max_matching.h.


Generated on Sat Mar 19 10:58:47 2005 for LEMON by  doxygen 1.4.1