dinic_algorithm/graph.h at master · bea231/dinic_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
 * Sergeev Artemiy, 33601/2
 * Dinic's algorithm
 */

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <vector>
#include <list>

namespace flow
{
  /* Flow network class */
  class network_t
  {
  private:
    /* Vertex neighbour class */
    struct neighbour_t
    {
      unsigned int _id;
      int _capacity, _flow;

      /* Default constructor */
      neighbour_t( unsigned int id, int capacity, int flow = 0 ) : _id(id), _capacity(capacity), _flow(flow)
      {
      }
    };

    typedef std::list<neighbour_t> neighbour_list_t;

    /*** Class fields ***/
    neighbour_list_t *_vertices;
    unsigned int      _verticesCount,
                      _edgesCount,
                      _source,
                      _sink;
    /* Default constructor */
    network_t( void ) { }

    neighbour_list_t::iterator placeFor( unsigned int id, unsigned int idWhere );

    /*** Helpful functions for Dinic's algorithm ***/
    bool network_t::dinicBFS( int *distances );
    int  dinicDFS( unsigned int id, int flow, unsigned int *pointers, int *distances  );
  public:
    /* Class constructor for users */
    network_t( unsigned int verticesCount, unsigned int source, unsigned int sink ) :
        _vertices(0), _verticesCount(verticesCount), _edgesCount(0),
        _source(source), _sink(sink)
    {
      if (verticesCount != 0)
      {
        _vertices = new neighbour_list_t[_verticesCount];
        if (source > _verticesCount || sink > _verticesCount)
          _source = 0, _sink = _verticesCount - 1;
      }
    }

    /* Class destructor */
    ~network_t( void )
    {
      if (_vertices)
        delete[] _vertices;
      _source = _sink = _verticesCount = 0;
    }

    /* Interface for user */
    void clear( void )
    {
      for (unsigned int i = 0; i < _verticesCount; ++i)
      {
        neighbour_list_t::iterator iter = _vertices[i].begin(),
                                   end = _vertices[i].end();

        while (iter != end)
        {
          iter->_flow = 0;
          ++iter;
        }
      }
    }

    /*** Gettters ***/
    unsigned int verticesCount( void ) const { return _verticesCount; }
    unsigned int edgesCount( void ) const { return _edgesCount; }

    /*** Functionality ***/
    int addEdge( unsigned int idFrom, unsigned int idTo, int capacity );
    int deleteEdge( unsigned int idFrom, unsigned int idTo );
    int setEdgeCapacity( unsigned int idFrom, unsigned int idTo, int capacity );
    int getEdgeCapacity( unsigned int idFrom, unsigned int idTo );

    int maximumFlow( void );
  };
}

#endif /* _GRAPH_H_ */