RhodeCode

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

  ap.mandatoryGroup("gr");

  // Set the options of the group exclusive (only one option can be given)

  ap.onlyOneGroup("gr");

  // Add non-parsed arguments (e.g. input files)

  ap.other("infile", "The input file.")

    .other("...");

  // Perform the parsing process

  // (in case of any error it terminates the program)

  ap.parse();

  // Check each option if it has been given and print its value

  std::cout << "Parameters of '" << ap.commandName() << "':\n";

  if(ap.given("name")) std::cout << "  Value of -name: " << s << std::endl;

  if(ap.given("f")) std::cout << "  -f is given\n";

  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << nh << std::endl;

  if(ap.given("gra")) std::cout << "  -gra is given\n";

  if(ap.given("grb")) std::cout << "  -grb is given\n";

  if(ap.given("grc")) std::cout << "  -grc is given\n";

  switch(ap.files().size()) {

  case 0:

    std::cout << "  No file argument was given.\n";

    break;

  case 1:

    std::cout << "  1 file argument was given. It is:\n";

    break;

  default:

    std::cout << "  "

  }

  for(unsigned int i=0;i<ap.files().size();++i)

    std::cout << "    '" << ap.files()[i] << "'\n";

  return 0;

}

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

  // Create a small digraph

  ListDigraph g;

  typedef ListDigraph::Node Node;

  typedef ListDigraph::NodeIt NodeIt;

  typedef ListDigraph::Arc Arc;

  typedef dim2::Point<int> Point;

  Node n1=g.addNode();

  Node n2=g.addNode();

  Node n3=g.addNode();

  Node n4=g.addNode();

  Node n5=g.addNode();

  ListDigraph::NodeMap<Point> coords(g);

  ListDigraph::NodeMap<double> sizes(g);

  ListDigraph::NodeMap<int> colors(g);

  ListDigraph::NodeMap<int> shapes(g);

  ListDigraph::ArcMap<int> acolors(g);

  ListDigraph::ArcMap<int> widths(g);

  coords[n1]=Point(50,50);  sizes[n1]=1; colors[n1]=1; shapes[n1]=0;

  coords[n2]=Point(50,70);  sizes[n2]=2; colors[n2]=2; shapes[n2]=2;

  coords[n3]=Point(70,70);  sizes[n3]=1; colors[n3]=3; shapes[n3]=0;

  coords[n4]=Point(70,50);  sizes[n4]=2; colors[n4]=4; shapes[n4]=1;

  coords[n5]=Point(85,60);  sizes[n5]=3; colors[n5]=5; shapes[n5]=2;

  Arc a;

  a=g.addArc(n1,n2); acolors[a]=0; widths[a]=1;

  a=g.addArc(n2,n3); acolors[a]=0; widths[a]=1;

  a=g.addArc(n3,n5); acolors[a]=0; widths[a]=3;

  a=g.addArc(n5,n4); acolors[a]=0; widths[a]=1;

  a=g.addArc(n4,n1); acolors[a]=0; widths[a]=1;

  a=g.addArc(n2,n4); acolors[a]=1; widths[a]=2;

  a=g.addArc(n3,n4); acolors[a]=2; widths[a]=1;

  IdMap<ListDigraph,Node> id(g);

  // Create five .eps files showing the digraph with different options

  cout << "Create 'graph_to_eps_demo_out_1_pure.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_1_pure.eps").

    coords(coords).

    run();

  // Create an .eps file showing the colors of a default Palette

  ListDigraph h;

  ListDigraph::NodeMap<int> hcolors(h);

  ListDigraph::NodeMap<Point> hcoords(h);

  int cols=int(sqrt(double(palette.size())));

  for(int i=0;i<int(paletteW.size());i++) {

    Node n=h.addNode();

    hcoords[n]=Point(1+i%cols,1+i/cols);

    hcolors[n]=i;

  }

  cout << "Create 'graph_to_eps_demo_out_6_colors.eps'" << endl;

  graphToEps(h,"graph_to_eps_demo_out_6_colors.eps").

    scale(60).

    title("Sample .eps figure (Palette demo)").

    copyright("(C) 2003-2008 LEMON Project").

    coords(hcoords).

    absoluteNodeSizes().absoluteArcWidths().

    nodeScale(.45).

    distantColorNodeTexts().

    nodeTexts(hcolors).nodeTextSize(.6).

    nodeColors(composeMap(paletteW,hcolors)).

    run();

  return 0;

}

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

///\ingroup demos

///\file

///\brief Demonstrating graph input and output

///

/// This program gives an example of how to read and write a digraph

/// \ref lgf-format "LGF" format.

///

/// The \c "digraph.lgf" file:

/// \include digraph.lgf

///

/// And the program which reads it and prints the digraph to the

using namespace lemon;

int main() {

  SmartDigraph g;

  SmartDigraph::ArcMap<int> cap(g);

  SmartDigraph::Node s, t;

  try {

    digraphReader("digraph.lgf", g). // read the directed graph into g

      arcMap("capacity", cap).       // read the 'capacity' arc map into cap

      node("source", s).             // read 'source' node to s

      node("target", t).             // read 'target' node to t

      run();

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * purpose.

 *

 */

/*!

\section naming_conv Naming Conventions

In order to make development easier we have made some conventions

according to coding style. These include names of types, classes,

functions, variables, constants and exceptions. If these conventions

\subsection cs-class Classes and other types

The name of a class or any type should look like the following.

\code

\endcode

\subsection cs-func Methods and other functions

The name of a function should look like the following.

\code

\endcode

\subsection cs-funcs Constants, Macros

The names of constants and macros should look like the following.

\code

\endcode

The names of class and instance member variables and auto variables (=variables used locally in methods) should look like the following.

\code

\endcode

\subsection pri-loc-var Private member variables

Private member variables should start with underscore

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

/**

\dir bits

\brief Implementation helper files

This directory contains some helper classes to implement graphs, maps and

files.

*/

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

/**

@defgroup graphs Graph Structures

@ingroup datas

\brief Graph structures implemented in LEMON.

The most efficient implementation of diverse applications require the

usage of different physical graph implementations. These differences

appear in the size of graph we require to handle, memory or time usage

limitations or in the set of operations through which the graph can be

accessed.  LEMON provides several physical graph structures to meet

the diverging requirements of the possible users.  In order to save on

running time or on memory usage, some structures may fail to provide

some graph features like arc/edge or node deletion.

arcs have to be hidden or the reverse oriented graph have to be used, then

You are free to use the graph structure that fit your requirements

the best, most graph algorithms and auxiliary data structures can be used

*/

/**

@defgroup semi_adaptors Semi-Adaptor Classes for Graphs

@ingroup graphs

\brief Graph types between real graphs and graph adaptors.

This group describes some graph types between real graphs and graph adaptors.

On the other hand they are not light-weight structures as the adaptors.

*/

/**

@ingroup datas

\brief Map structures implemented in LEMON.

This group describes the map structures implemented in LEMON.

LEMON provides several special purpose maps that e.g. combine

new maps from existing ones.

*/

/**

@ingroup maps

\brief Special graph-related maps.

This group describes maps that are specifically designed to assign

values to the nodes and arcs of graphs.

*/

    } else if (deg == 1) {

      return Color(1.0, 0.5, 1.0);

    } else {

      return Color(0.0, 0.0, 0.0);

    }

  }

  Digraph::NodeMap<int> degree_map(graph);

  digraphToEps(graph, "graph.eps")

    .coords(coords).scaleToA4().undirected()

    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

    .run();

The \c functorToMap() function makes an \c int to \c Color map from the

\e nodeColor() function. The \c composeMap() compose the \e degree_map

and the previously created map. The composed map is a proper function to

get the color of each node.

The usage with class type algorithms is little bit harder. In this

  typedef Digraph::ArcMap<double> DoubleArcMap;

  DoubleArcMap length(graph);

  DoubleArcMap speed(graph);

  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

  TimeMap time(length, speed);

  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

  dijkstra.run(source, target);

\endcode

We have a length map and a maximum speed map on the arcs of a digraph.

The minimum time to pass the arc can be calculated as the division of

the two maps which can be done implicitly with the \c DivMap template

class. We use the implicit minimum time map as the length map of the

\c Dijkstra algorithm.

*/

/**

@ingroup datas

\brief Two dimensional data storages implemented in LEMON.

This group describes two dimensional data storages implemented in LEMON.

*/

/**

@defgroup search Graph Search

@ingroup algs

\brief Common graph search algorithms.

Breadth-first search (Bfs) and Depth-first search (Dfs).

*/

/**

@defgroup shortest_path Shortest Path algorithms

@ingroup algs

\brief Algorithms for finding shortest paths.

This group describes the algorithms for finding shortest paths in graphs.

*/

\brief Algorithms for finding maximum flows.

This group describes the algorithms for finding maximum flows and

feasible circulations.

The maximum flow problem is to find a flow between a single source and

\f[ 0 \le f_a \le c_a \f]

\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]

\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

LEMON contains several algorithms for solving maximum flow problems:

- \ref lemon::Preflow "Goldberg's Preflow algorithm"

- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

In most cases the \ref lemon::Preflow "Preflow" algorithm provides the

fastest method to compute the maximum flow. All impelementations

@defgroup min_cost_flow Minimum Cost Flow algorithms

@ingroup algs

\brief Algorithms for finding minimum cost flows and circulations.

This group describes the algorithms for finding minimum cost flows and

*/

/**

\brief Algorithms for finding minimum cut in graphs.

This group describes the algorithms for finding minimum cut in graphs.

The minimum cut problem is to find a non-empty and non-complete

\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]

LEMON contains several algorithms related to minimum cut problems:

- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

  calculate minimum cut in undirected graphs

- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

  pairs minimum cut in undirected graphs

If you want to find minimum cut just between two distinict nodes,

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains algorithm objects and functions to calculate

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the arcs which does not shares common endpoints.

There are several different algorithms for calculate matchings in

graphs.  The matching problems in bipartite graphs are generally

easier than in general graphs. The goal of the matching optimization

can be the finding maximum cardinality, maximum weight or minimum cost

matching. The search can be constrained to find perfect or

maximum cardinality matching.

Lemon contains the next algorithms:

  bipartite graphs

  and maximum weighted bipartite matching in bipartite graph

  matching in bipartite graph

- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm

  for calculate maximum cardinality matching in general graph

- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

  shrinking algorithm for calculate maximum weighted matching in general

  graph

This group describes Lp and Mip solver interfaces for LEMON. The

various LP solvers could be used in the same manner with this

interface.

*/

@ingroup lp_group

\brief Helper tools to the Lp and Mip solvers.

This group adds some helper tools to general optimization framework

implemented in LEMON.

*/

\brief Metaheuristics for LEMON library.

This group describes some metaheuristic optimization tools.

*/

/**

\brief Tools and utilities for programming in LEMON

Tools and utilities for programming in LEMON.

*/

/**

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

and graph related data. Now it supports the LEMON format, the

\c DIMACS format and the encapsulated postscript (EPS) format.

*/

/**

@defgroup lemon_io Lemon Input-Output

/**

@defgroup eps_io Postscript exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

*/

/**

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

This group describes the data/algorithm skeletons and concept checking

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

- These classes contain the documentations of the concepts. In order

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  implementation of the concepts should provide, however completely

build the library.

*/

/**

@defgroup tools Standalone utility applications

The standard compilation procedure (<tt>./configure;make</tt>) will compile

*/

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The @arcs section can

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

non-commercial applications under very permissive

\ref license "license terms".

</b>

\subsection howtoread How to read the documentation

take a look at our \ref quicktour

"Quick Tour to LEMON" which will guide you along.

\ref getstart "How to start using LEMON".

some \ref demoprograms "demo programs"!

If you know what you are looking for then try to find it under the

<a class="el" href="modules.html">Modules</a>

section.

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 *

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

  }

  ArgParser::~ArgParser()

  {

    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)

      if(i->second.self_delete)

  }

  ArgParser &ArgParser::intOption(const std::string &name,

  {

    ParData p;

    p.int_p=new int(value);

    p.self_delete=true;

    p.help=help;

    p.type=INTEGER;

    p.mandatory=obl;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::doubleOption(const std::string &name,

  {

    ParData p;

    p.double_p=new double(value);

    p.self_delete=true;

    p.help=help;

    p.type=DOUBLE;

    p.mandatory=obl;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::boolOption(const std::string &name,

  {

    ParData p;

    p.bool_p=new bool(value);

    p.self_delete=true;

    p.help=help;

    p.type=BOOL;

    p.mandatory=obl;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::stringOption(const std::string &name,

  {

    ParData p;

    p.string_p=new std::string(value);

    p.self_delete=true;

    p.help=help;

    p.type=STRING;

    p.mandatory=obl;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::refOption(const std::string &name,

  {

    ParData p;

    p.int_p=&ref;

    p.self_delete=false;

    p.help=help;

    p.type=INTEGER;

    ref = false;

    return *this;

  }

  ArgParser &ArgParser::refOption(const std::string &name,

  {

    ParData p;

    p.string_p=&ref;

    p.self_delete=false;

    p.help=help;

    p.type=STRING;

    p.mandatory=obl;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::funcOption(const std::string &name,

  {

    ParData p;

    p.func_p.p=func;

    p.func_p.data=data;

    p.self_delete=false;

    p.help=help;

    p.mandatory=false;

    _opts[name]=p;

    return *this;

  }

  ArgParser &ArgParser::optionGroup(const std::string &group,

  {

    Opts::iterator i = _opts.find(opt);

    LEMON_ASSERT(i!=_opts.end(), "Unknown option: '"+opt+"'");

                 "Option already in option group: '"+opt+"'");

    GroupData &g=_groups[group];

    g.opts.push_back(opt);

    i->second.ingroup=true;

    return *this;

  }

    GroupData &g=_groups[group];

    g.only_one=true;

    return *this;

  }

  ArgParser &ArgParser::synonym(const std::string &syn,

  {

    Opts::iterator o = _opts.find(opt);

    Opts::iterator s = _opts.find(syn);

    LEMON_ASSERT(o!=_opts.end(), "Unknown option: '"+opt+"'");

    LEMON_ASSERT(s==_opts.end(), "Option already used: '"+syn+"'");

    ParData p;

    GroupData &g=_groups[group];

    g.mandatory=true;

    return *this;

  }

  ArgParser &ArgParser::other(const std::string &name,

  {

    _others_help.push_back(OtherArg(name,help));

    return *this;

  }

  void ArgParser::show(std::ostream &os,Opts::iterator i)

  {

    os << "-" << i->first;

    if(i->second.has_syn)

      for(Opts::iterator j=_opts.begin();j!=_opts.end();++j)

    switch(i->second.type) {

    case STRING:

      os << " str";

      break;

    case INTEGER:

      os << " int";

    while(o!=i->second.opts.end()) {

      show(os,_opts.find(*o));

      ++o;

      if(o!=i->second.opts.end()) os<<'|';

    }

  }

  void ArgParser::showHelp(Opts::iterator i)

  {

    if(i->second.help.size()==0||i->second.syn) return;

    std::cerr << "  ";

    show(std::cerr,i);

    std::cerr << std::endl;

    std::cerr << "     " << i->second.help << std::endl;

  }

  void ArgParser::showHelp(std::vector<ArgParser::OtherArg>::iterator i)

  {

    if(i->help.size()==0) return;

    std::cerr << "  " << i->name << std::endl

  }

  void ArgParser::shortHelp()

  {

    const unsigned int LINE_LEN=77;

    const std::string indent("    ");

    std::cerr << "Usage:\n  " << _command_name;

    int pos=_command_name.size()+2;

      std::ostringstream cstr;

      cstr << ' ';

      if(!g->second.mandatory) cstr << '[';

      show(cstr,g);

      if(!g->second.mandatory) cstr << ']';

      if(pos+cstr.str().size()>LINE_LEN) {

      }