Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:document the interfaces forthe trader classes
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:6f9b6eeb0532d8c5b92c5fbbd6c97cea92e80f25
User & Date: ravenspoint 2016-05-29 11:49:12
Context
2016-05-30
13:47
fix handling of leaves in DFS check-in: 70b33f7e96 user: ravenspoint tags: trunk
2016-05-29
11:49
document the interfaces forthe trader classes check-in: 6f9b6eeb05 user: ravenspoint tags: trunk
00:19
problem 2 check-in: 9e6ffedda7 user: ravenspoint tags: trunk
Changes

Changes to trade.cpp.

10
11
12
13
14
15
16














































17
18
19
20
21
22
23
..
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
..
97
98
99
100
101
102
103







































































104
105
106
107
108
109
110
111
112
#include <boost/property_map/property_map.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;
using namespace boost;

#include "trade.h"















































void cVillage::AddTrader(
    eCommodity sell,
    eCommodity buy,
    float price )
{
    myGraph[ add_vertex( myGraph ) ] = cTrader( sell, buy, price );
................................................................................
            myGraph[ *vi ].Display();
        }
        index++;
    }
}
void cVillage::ConstructSensibleTrips()
{
    // A sensible trip betwee two traders:
    // the source is selling what the target is buying

    // loop over all pairs of traders

    graph_traits<trade_graph_t>::vertex_iterator svi, svi_end, tvi, tvi_end;
    for (boost::tie(svi, svi_end) = vertices(myGraph); svi != svi_end; ++svi)
    {
................................................................................
                if( myGraph[ *svi ].mySell == myGraph[ *tvi ].myBuy )
                    add_edge( *svi, *tvi, myGraph );
            }
            index++;
        }
    }
}







































































int main()
{
    cVillage village;
    village.ConstructProblem2();
    village.Display();
    village.Travel();

    return 0;
}







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>









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
...
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
...
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <boost/property_map/property_map.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;
using namespace boost;

#include "trade.h"

    void cTrader::Display()
    {
        if( myPrice >= 1 )
            cout << "Gives 1 " << Sell() << " For " << myPrice <<" "<< Buy() << endl;
        else
        {
            cout << "Gives " << 1 / myPrice <<" " << Sell() << " For 1 " << Buy() << endl;
        }
    }

    template < typename Vertex, typename Graph >
    void cTraveler::discover_vertex( Vertex u, Graph& g)
    {
        // check that we are on a trading trip
        if( ! myfTrading )
            return;

        // check that we have left the starting point
        if( u == 0)
            return;

        // tell user our status
        cout << "Trader " << u << " ";
        cout << g[ u ].Buy() << " -> " << g[ u ].Sell() << " now holding ";

        // Do the trade
        *myHold = g[ u ].mySell;
        *myQuantity = *myQuantity / g[u].myPrice;

        // Add to path
        myPath->push_back( u );

        // New status following trade
        Display();

        // check if we are now holding our original commodity
        if( IsSuccess() )
        {
            // the search is complete
            *dst = u;
            throw runtime_error( "init hold ");
        }

        *src = u;
    }

void cVillage::AddTrader(
    eCommodity sell,
    eCommodity buy,
    float price )
{
    myGraph[ add_vertex( myGraph ) ] = cTrader( sell, buy, price );
................................................................................
            myGraph[ *vi ].Display();
        }
        index++;
    }
}
void cVillage::ConstructSensibleTrips()
{
    // A sensible trip between two traders:
    // the source is selling what the target is buying

    // loop over all pairs of traders

    graph_traits<trade_graph_t>::vertex_iterator svi, svi_end, tvi, tvi_end;
    for (boost::tie(svi, svi_end) = vertices(myGraph); svi != svi_end; ++svi)
    {
................................................................................
                if( myGraph[ *svi ].mySell == myGraph[ *tvi ].myBuy )
                    add_edge( *svi, *tvi, myGraph );
            }
            index++;
        }
    }
}

    void cVillage::Travel()
    {
        // Construct graph of potentiall profitable trips between traders
        ConstructSensibleTrips();

        // Yes, we are trading as we go along
        myTraveler.myfTrading = true;

        // The greatest profit found
        float bestQuantity = -1;

        // The path giving the greatest profit
        vector< int > bestpath;

        // The two most recent traders visited
        unsigned int src, dst;
        myTraveler.src = &src;
        myTraveler.dst = &dst;

        // Do a fixed number of searches
        int count = 0;
        while( count < 30 )
        {
            try
            {
                // go back to go
                myTraveler.Restart();

                // do a depth first search, trading as we go
                depth_first_search(
                    myGraph,
                    visitor( myTraveler )
                    .root_vertex( 0 ));

                // The search was completed without success
                // ( trading for the original commodity )
                break;
            }
            catch( runtime_error& e )
            {
                // Success!
                myTraveler.Display();
                if( myTraveler.IsSuccess() )
                {
                    // check for most progitable found so far
                    if( *(myTraveler.myQuantity) > bestQuantity )
                    {
                        // remember out most profitable path
                        bestQuantity = *(myTraveler.myQuantity);
                        bestpath = *(myTraveler.myPath);

                    }
                }

                // prevent repeating this same path
                // by removing the trip between the last two traders
                //cout << src << " - " << dst << endl;
                remove_edge( src, dst, myGraph );
                count++;
            }
        }

        // Display the most profitable path found
        cout << "\n=========================\n";
        cout << "Best: Holding " << bestQuantity << " from trades with ";
        for( auto v : bestpath )
            cout << v << " ";
        cout << endl;
    }

int main()
{
    cVillage village;
    village.ConstructProblem2();
    village.Display();
    village.Travel();

    return 0;
}

Changes to trade.h.

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
...
108
109
110
111
112
113
114







115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
...
157
158
159
160
161
162
163

164
165
166
167
168

169
170






171
172
173
174


175
176
177
178

179
180
181

182
183


184

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243


244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
enum class eCommodity
{
    wood,
    sand,
    gras,
};

vector< string > Names
{
    "wood",
    "sand",
    "gras",
};

/** A trader selling a commodity for another at a price */
class cTrader
{
public:


    eCommodity mySell;


    eCommodity myBuy;



    float myPrice;





    cTrader() {}






    cTrader( eCommodity sell,
             eCommodity buy,
             float price )
        : mySell( sell )
        , myBuy( buy )
        , myPrice( price )
    {

    }
    void Display()
    {
        if( myPrice >= 1 )
            cout << "Gives 1 " << Sell() << " For " << myPrice <<" "<< Buy() << endl;
        else
        {
            cout << "Gives " << 1 / myPrice <<" " << Sell() << " For 1 " << Buy() << endl;
        }
    }
    const string& Sell() const
    {
        return Names[(int)mySell];
    }
    const string& Buy() const
    {
        return Names[(int)myBuy];
    }
};


class cTrip
{
public:

    void Weight( int w )
    {
        myWeight = w;

    }
    int Weight()
    {



        return myWeight;
    }
    void negWeight()
    {
        myWeight = - myWeight;


    }



    int myWeight;

};


typedef adjacency_list<
vecS, vecS,  directedS,
      cTrader, cTrip  > trade_graph_t;











class cTraveler : public default_dfs_visitor
{
public:

    eCommodity * myHold;


    eCommodity myInitiallHold;


    float * myQuantity;


    float myInitialQuantity;


    unsigned int * src;


    unsigned int * dst;


    bool myfTrading;


    vector< int > * myPath;


    cTraveler() {}





    cTraveler( eCommodity hold,
               int quantity )
        : myInitiallHold( hold )
        , myInitialQuantity( quantity )
        , myfTrading( false )
    {
        *myHold = hold;
................................................................................
    void back_edge( Edge e, Graph& g)
    {
        *src = source( e, g );
        *dst = target( e, g );
        throw runtime_error("cyclic");
    }








    template < typename Vertex, typename Graph >
    void discover_vertex( Vertex u, Graph& g)
    {
        if( ! myfTrading )
            return;
        if( u == 0)
            return;

        cout << "Trader " << u << " ";
        cout << g[ u ].Buy() << " -> " << g[ u ].Sell() << " now holding ";

        // Do the trade
        *myHold = g[ u ].mySell;
        *myQuantity = *myQuantity / g[u].myPrice;
        myPath->push_back( u );

        Display();

        if( g[ u ].mySell == myInitiallHold )
        {
            *dst = u;
            throw runtime_error( "init hold ");
        }

        *src = u;
    }

    void Display()
    {
//        for( auto v : *myPath )
//            cout << v << " ";
//        cout << "\n";
        cout << "holding " << *myQuantity
             << " of " << Names[ (int)*myHold ] << endl;
    }
    void Restart()
    {
        *myHold = myInitiallHold;
        *myQuantity = myInitialQuantity;
        myPath->clear();
        cout << endl;
................................................................................
    }
    bool IsSuccess()
    {
        return *myHold == myInitiallHold;
    }
};


class cVillage
{
public:
    cTraveler myTraveler;


    trade_graph_t myGraph;







    void AddTrader(
                   eCommodity sell,
                   eCommodity buy,
                   float price );



    void ConstructProblem1();
    void ConstructProblem2();


    void Display();

    void ConstructSensibleTrips();


     void Travel()


    {

        ConstructSensibleTrips();
        //ConvertToDAG();
        myTraveler.myfTrading = true;
        float bestQuantity = -1;
        vector< int > bestpath;
        unsigned int src, dst;
        myTraveler.src = &src;
        myTraveler.dst = &dst;
        int count = 0;
        while( count < 30 )
        {
            try
            {
                myTraveler.Restart();
                depth_first_search(
                    myGraph,
                    visitor( myTraveler )
                    .root_vertex( 0 ));
                break;
            }
            catch( runtime_error& e )
            {
                myTraveler.Display();
                if( myTraveler.IsSuccess() )
                {
                    if( *(myTraveler.myQuantity) > bestQuantity )
                    {
                        bestQuantity = *(myTraveler.myQuantity);
                        bestpath = *(myTraveler.myPath);

                    }
                }
                //cout << src << " - " << dst << endl;
                remove_edge( src, dst, myGraph );
                count++;
            }
        }

        cout << "\n=========================\n";
        cout << "Best: Holding " << bestQuantity << " from trades with ";
        for( auto v : bestpath )
            cout << v << " ";
        cout << endl;
    }
    void ConvertToDAG()
    {

        unsigned int src, dst;
        myTraveler.src = &src;
        myTraveler.dst = &dst;

        // loop while graph is still cyclic
        while( 1 )
        {
            try
            {
                // depth first search using back edge detecting visitor
                depth_first_search(
                    myGraph,


                    visitor(myTraveler)
                    .root_vertex( 0 ));

                // the seach found no cycles
                // so we can break out of the loop
                break;
            }
            catch( runtime_error& e )
            {
                // the search through an excepting indicating a cycle

                // remove back edge found
                cout << "removing " << src << " -> " << dst << endl;
                remove_edge( src, dst, myGraph );
            }
        }
    }
};







<
<
<
<
<
<
<




>
>

>
>

>
>
>

>
>
>
>
>

>
>
>
>
>
>









|
|
<
<
<
<
<
<
<


|



|

<
>
|
|
|
<
>
|
<
<
>
|
<
<
>
>
>
|
|
|
|
|
>
>
|
>
>
|
<
>


>




>
>
>
>
>
>
>
>
>
>



>

>
>

>
>

>
>

>
>

>
>

>
>

>
>

>
>

>
>
>
>
>







 







>
>
>
>
>
>
>

|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







|







 







>





>


>
>
>
>
>
>

|
|
|
>
>




>


<
>

<
>
>
|
>
|
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
>
>
|
<

<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
...
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
























165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
...
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

216
217

218
219
220
221
222









223
















































224
225
226

227



228











enum class eCommodity
{
    wood,
    sand,
    gras,
};








/** A trader selling a commodity for another at a price */
class cTrader
{
public:

    /**  The commodity being offered */
    eCommodity mySell;

    /** The commodity being sought */
    eCommodity myBuy;

    /** The amount of the buy commodity
    needed to purchase one unit of the sell commodity */
    float myPrice;

    /** Default constructor

    Used by the STL for placeholders - do not use in application code
     */
    cTrader() {}

    /** Construct
        @param[in] sell commodity
        @param[in] buy commodity
        @param[in] price
    */
    cTrader( eCommodity sell,
             eCommodity buy,
             float price )
        : mySell( sell )
        , myBuy( buy )
        , myPrice( price )
    {

    }
    void Display();








    const string& Sell() const
    {
        return Name( mySell );
    }
    const string& Buy() const
    {
        return Name( myBuy );
    }

    static const string Name( eCommodity c )
    {
        static vector< string > Names
        {

            "wood",
            "sand",


            "gras",
        };


        return Names[ (int) c ];
    }
};
/** The trip between two traders.

There is nothing here.

This is represented by an edge in the graph.  The edge cannot be
assigned a weight, because the profit available from making
the trip between two edges cannot be known until the entire path is complete.

*/
class cTrip
{


};

/** define the graph with a trader at each vertex connected by trips */
typedef adjacency_list<
vecS, vecS,  directedS,
      cTrader, cTrip  > trade_graph_t;

/** A visitor which travels between traders hoping to make a profit

  This is propelled through the graph of traders by a depth first search (DFS).

  The DFS uses a private copy of the visitor,
  so many of the attributes are pointers
  so that the application code can access the values
  when the search is complete.

 */
class cTraveler : public default_dfs_visitor
{
public:
    /** The commodity currently held */
    eCommodity * myHold;

    /** The commodity held at the start */
    eCommodity myInitiallHold;

    /** The quantity currently held */
    float * myQuantity;

    /** The quantity held at the start */
    float myInitialQuantity;

    /** The trader we just left */
    unsigned int * src;

    /** The trader we just arrived at */
    unsigned int * dst;

    /** True if we are on a trading trip */
    bool myfTrading;

    /** Traders we have visited so far */
    vector< int > * myPath;

    /** default constructor */
    cTraveler() {}

    /** Constructor
        @param[in] hold commodity
        @param[in] quantity
    */
    cTraveler( eCommodity hold,
               int quantity )
        : myInitiallHold( hold )
        , myInitialQuantity( quantity )
        , myfTrading( false )
    {
        *myHold = hold;
................................................................................
    void back_edge( Edge e, Graph& g)
    {
        *src = source( e, g );
        *dst = target( e, g );
        throw runtime_error("cyclic");
    }

    /** Called by DFS when trader is visited
        @param[in] Vertex the trader
        @param[in] graph we are searching

        Throws exception if, after trading, we are holding our original
        commodity again - which completes this search
    */
    template < typename Vertex, typename Graph >
    void discover_vertex( Vertex u, Graph& g);

























    void Display()
    {
//        for( auto v : *myPath )
//            cout << v << " ";
//        cout << "\n";
        cout << "holding " << *myQuantity
             << " of " << cTrader::Name( *myHold ) << endl;
    }
    void Restart()
    {
        *myHold = myInitiallHold;
        *myQuantity = myInitialQuantity;
        myPath->clear();
        cout << endl;
................................................................................
    }
    bool IsSuccess()
    {
        return *myHold == myInitiallHold;
    }
};

/** A village of traders */
class cVillage
{
public:
    cTraveler myTraveler;

    /** The graph, which stores the traders and allows the traveller to move bewteen traders */
    trade_graph_t myGraph;

    /** Add trader
        @param[in] sell commodity offered
        @param[in] buy commodity sought
        @param[in] price The amount of the buy commodity
                            needed to purchase one unit of the sell commodity
     */
    void AddTrader(
        eCommodity sell,
        eCommodity buy,
        float price );

    /** Construct test problems */

    void ConstructProblem1();
    void ConstructProblem2();

    /** Display the traders ( problem statement ) */
    void Display();


    /** Construct potentialy profitable trips ( edges ) between traders


    There is no point in travelling between two traders
    unless the source is selling what the target is buying

    */
    void ConstructSensibleTrips();


























































    /** Search the village for the most profitable path betwee traders
    */
    void Travel();





};