lemon/color.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 313 64f8f7cc6168
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@128
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@128
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@128
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@128
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@128
     8
 *
alpar@128
     9
 * Permission to use, modify and distribute this software is granted
alpar@128
    10
 * provided that this copyright notice appears in all copies. For
alpar@128
    11
 * precise terms see the accompanying LICENSE file.
alpar@128
    12
 *
alpar@128
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@128
    14
 * express or implied, and with no claim as to its suitability for any
alpar@128
    15
 * purpose.
alpar@128
    16
 *
alpar@128
    17
 */
alpar@128
    18
alpar@128
    19
#ifndef LEMON_COLOR_H
alpar@128
    20
#define LEMON_COLOR_H
alpar@128
    21
alpar@128
    22
#include<vector>
alpar@128
    23
#include<lemon/math.h>
alpar@128
    24
#include<lemon/maps.h>
alpar@128
    25
alpar@128
    26
alpar@128
    27
///\ingroup misc
alpar@128
    28
///\file
alpar@128
    29
///\brief Tools to manage RGB colors.
alpar@128
    30
alpar@128
    31
namespace lemon {
alpar@128
    32
alpar@128
    33
alpar@128
    34
  /// \addtogroup misc
alpar@128
    35
  /// @{
alpar@128
    36
alpar@128
    37
  ///Data structure representing RGB colors.
alpar@128
    38
alpar@128
    39
  ///Data structure representing RGB colors.
alpar@128
    40
  class Color
alpar@128
    41
  {
alpar@128
    42
    double _r,_g,_b;
alpar@128
    43
  public:
alpar@128
    44
    ///Default constructor
alpar@128
    45
    Color() {}
alpar@128
    46
    ///Constructor
alpar@128
    47
    Color(double r,double g,double b) :_r(r),_g(g),_b(b) {};
alpar@128
    48
    ///Set the red component
alpar@128
    49
    double & red() {return _r;}
alpar@128
    50
    ///Return the red component
alpar@128
    51
    const double & red() const {return _r;}
alpar@128
    52
    ///Set the green component
alpar@128
    53
    double & green() {return _g;}
alpar@128
    54
    ///Return the green component
alpar@128
    55
    const double & green() const {return _g;}
alpar@128
    56
    ///Set the blue component
alpar@128
    57
    double & blue() {return _b;}
alpar@128
    58
    ///Return the blue component
alpar@128
    59
    const double & blue() const {return _b;}
alpar@128
    60
    ///Set the color components
alpar@128
    61
    void set(double r,double g,double b) { _r=r;_g=g;_b=b; };
alpar@128
    62
  };
alpar@128
    63
alpar@128
    64
  /// White color constant
alpar@209
    65
  extern const Color WHITE;
alpar@128
    66
  /// Black color constant
alpar@128
    67
  extern const Color BLACK;
alpar@128
    68
  /// Red color constant
alpar@128
    69
  extern const Color RED;
alpar@128
    70
  /// Green color constant
alpar@128
    71
  extern const Color GREEN;
alpar@128
    72
  /// Blue color constant
alpar@128
    73
  extern const Color BLUE;
alpar@128
    74
  /// Yellow color constant
alpar@128
    75
  extern const Color YELLOW;
alpar@128
    76
  /// Magenta color constant
alpar@128
    77
  extern const Color MAGENTA;
alpar@128
    78
  /// Cyan color constant
alpar@128
    79
  extern const Color CYAN;
alpar@128
    80
  /// Grey color constant
alpar@128
    81
  extern const Color GREY;
alpar@128
    82
  /// Dark red color constant
alpar@128
    83
  extern const Color DARK_RED;
alpar@128
    84
  /// Dark green color constant
alpar@128
    85
  extern const Color DARK_GREEN;
alpar@128
    86
  /// Drak blue color constant
alpar@128
    87
  extern const Color DARK_BLUE;
alpar@128
    88
  /// Dark yellow color constant
alpar@128
    89
  extern const Color DARK_YELLOW;
alpar@128
    90
  /// Dark magenta color constant
alpar@128
    91
  extern const Color DARK_MAGENTA;
alpar@128
    92
  /// Dark cyan color constant
alpar@128
    93
  extern const Color DARK_CYAN;
alpar@128
    94
kpeter@313
    95
  ///Map <tt>int</tt>s to different <tt>Color</tt>s
alpar@128
    96
alpar@128
    97
  ///This map assigns one of the predefined \ref Color "Color"s to
alpar@128
    98
  ///each <tt>int</tt>. It is possible to change the colors as well as
alpar@128
    99
  ///their number. The integer range is cyclically mapped to the
alpar@128
   100
  ///provided set of colors.
alpar@128
   101
  ///
alpar@128
   102
  ///This is a true \ref concepts::ReferenceMap "reference map", so
alpar@128
   103
  ///you can also change the actual colors.
alpar@128
   104
alpar@128
   105
  class Palette : public MapBase<int,Color>
alpar@128
   106
  {
alpar@128
   107
    std::vector<Color> colors;
alpar@128
   108
  public:
alpar@128
   109
    ///Constructor
alpar@128
   110
kpeter@206
   111
    ///Constructor.
kpeter@206
   112
    ///\param have_white Indicates whether white is among the
alpar@133
   113
    ///provided initial colors (\c true) or not (\c false). If it is true,
alpar@133
   114
    ///white will be assigned to \c 0.
kpeter@206
   115
    ///\param num The number of the allocated colors. If it is \c -1,
alpar@133
   116
    ///the default color configuration is set up (26 color plus optionaly the
alpar@128
   117
    ///white).  If \c num is less then 26/27 then the default color
alpar@128
   118
    ///list is cut. Otherwise the color list is filled repeatedly with
alpar@128
   119
    ///the default color list.  (The colors can be changed later on.)
alpar@129
   120
    Palette(bool have_white=false,int num=-1)
alpar@128
   121
    {
alpar@128
   122
      if (num==0) return;
alpar@128
   123
      do {
alpar@128
   124
        if(have_white) colors.push_back(Color(1,1,1));
alpar@128
   125
alpar@128
   126
        colors.push_back(Color(0,0,0));
alpar@128
   127
        colors.push_back(Color(1,0,0));
alpar@128
   128
        colors.push_back(Color(0,1,0));
alpar@128
   129
        colors.push_back(Color(0,0,1));
alpar@128
   130
        colors.push_back(Color(1,1,0));
alpar@128
   131
        colors.push_back(Color(1,0,1));
alpar@128
   132
        colors.push_back(Color(0,1,1));
alpar@209
   133
alpar@128
   134
        colors.push_back(Color(.5,0,0));
alpar@128
   135
        colors.push_back(Color(0,.5,0));
alpar@128
   136
        colors.push_back(Color(0,0,.5));
alpar@128
   137
        colors.push_back(Color(.5,.5,0));
alpar@128
   138
        colors.push_back(Color(.5,0,.5));
alpar@128
   139
        colors.push_back(Color(0,.5,.5));
alpar@209
   140
alpar@128
   141
        colors.push_back(Color(.5,.5,.5));
alpar@128
   142
        colors.push_back(Color(1,.5,.5));
alpar@128
   143
        colors.push_back(Color(.5,1,.5));
alpar@128
   144
        colors.push_back(Color(.5,.5,1));
alpar@128
   145
        colors.push_back(Color(1,1,.5));
alpar@128
   146
        colors.push_back(Color(1,.5,1));
alpar@128
   147
        colors.push_back(Color(.5,1,1));
alpar@209
   148
alpar@128
   149
        colors.push_back(Color(1,.5,0));
alpar@128
   150
        colors.push_back(Color(.5,1,0));
alpar@128
   151
        colors.push_back(Color(1,0,.5));
alpar@128
   152
        colors.push_back(Color(0,1,.5));
alpar@128
   153
        colors.push_back(Color(0,.5,1));
alpar@128
   154
        colors.push_back(Color(.5,0,1));
alpar@128
   155
      } while(int(colors.size())<num);
alpar@128
   156
      if(num>=0) colors.resize(num);
alpar@128
   157
    }
alpar@128
   158
    ///\e
alpar@128
   159
    Color &operator[](int i)
alpar@128
   160
    {
alpar@128
   161
      return colors[i%colors.size()];
alpar@128
   162
    }
alpar@128
   163
    ///\e
alpar@128
   164
    const Color &operator[](int i) const
alpar@128
   165
    {
alpar@128
   166
      return colors[i%colors.size()];
alpar@128
   167
    }
alpar@128
   168
    ///\e
alpar@128
   169
    void set(int i,const Color &c)
alpar@128
   170
    {
alpar@128
   171
      colors[i%colors.size()]=c;
alpar@128
   172
    }
kpeter@206
   173
    ///Adds a new color to the end of the color list.
alpar@209
   174
    void add(const Color &c)
alpar@128
   175
    {
alpar@128
   176
      colors.push_back(c);
alpar@128
   177
    }
alpar@128
   178
kpeter@206
   179
    ///Sets the number of the existing colors.
alpar@128
   180
    void resize(int s) { colors.resize(s);}
alpar@128
   181
    ///Returns the number of the existing colors.
alpar@128
   182
    int size() const { return int(colors.size());}
alpar@128
   183
  };
alpar@128
   184
alpar@133
   185
  ///Returns a visibly distinct \ref Color
alpar@128
   186
alpar@128
   187
  ///Returns a \ref Color which is as different from the given parameter
alpar@128
   188
  ///as it is possible.
alpar@209
   189
  inline Color distantColor(const Color &c)
alpar@128
   190
  {
alpar@128
   191
    return Color(c.red()<.5?1:0,c.green()<.5?1:0,c.blue()<.5?1:0);
alpar@128
   192
  }
alpar@128
   193
  ///Returns black for light colors and white for the dark ones.
alpar@128
   194
alpar@128
   195
  ///Returns black for light colors and white for the dark ones.
alpar@128
   196
  inline Color distantBW(const Color &c){
alpar@128
   197
    return (.2125*c.red()+.7154*c.green()+.0721*c.blue())<.5 ? WHITE : BLACK;
alpar@128
   198
  }
alpar@128
   199
alpar@128
   200
  /// @}
alpar@128
   201
alpar@128
   202
} //END OF NAMESPACE LEMON
alpar@128
   203
alpar@128
   204
#endif // LEMON_COLOR_H