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

Overview
Comment:Problem4
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:100b488c1e47afc1bdb9025b85a4b49801fbba33
User & Date: ravenspoint 2016-05-30 16:20:48
Context
2016-05-30
16:33
cRoute Leaf check-in: 073ecb6d90 user: ravenspoint tags: trunk
16:20
Problem4 check-in: 100b488c1e user: ravenspoint tags: trunk
15:21
check for stop condition check-in: b91609e688 user: ravenspoint tags: trunk
Changes

Changes to trade.cpp.

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
...
175
176
177
178
179
180
181


































182
183
184
185
186
187
188
...
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
...
317
318
319
320
321
322
323
324
325
326

327
328
329
330
331
        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();

    // remember our last trip
    // so it can be removed if it is a dead end, or if it is a scuccesful conclusion
    *src = *dst;
    *dst = u;

    // check if we are now holding our original commodity
    if( IsSuccess() )
    {
        // the search is complete

        throw runtime_error( "init hold ");




    }

    // check for leaf
    if( ! out_degree( u, g ) )
    {
        // we have reached a leaf of the graph tree
        // without successfully making a profit on our trades

        throw runtime_error("leaf");
    }

}

void cVillage::AddTrader(
    eCommodity sell,
    eCommodity buy,
................................................................................
    AddTrader( eCommodity::wood, eCommodity::sand, 2 );
    AddTrader( eCommodity::sand, eCommodity::gras, 0.5 );
    AddTrader( eCommodity::gras, eCommodity::sand, 1);
    AddTrader( eCommodity::sand, eCommodity::wood, 0.25);
    AddTrader( eCommodity::gras, eCommodity::wood, 0.3333);

}



































void cVillage::Display()
{
    int index = 0;
    graph_traits<trade_graph_t>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end) = vertices(myGraph); vi != vi_end; ++vi)
    {
................................................................................
                if( myGraph[ *svi ].mySell == myGraph[ *tvi ].myBuy )
                    add_edge( *svi, *tvi, myGraph );
            }
            index++;
        }
    }
    DisplayGraph();


}

bool cVillage::IsPotentiallyProfitablePath()
{
    return out_degree( 0, myGraph ) > 0;
}

































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;

    // number of searches
................................................................................
        cout << v << " ";
    cout << endl;
}

int main()
{
    cVillage village;
    village.ConstructProblem3(
        5,                         // traders
        2);                       // commodities

    village.Display();
    village.Travel();

    return 0;
}







|
|









|









<
>
|
>
>
>
>








|







 







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







 







>
>






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











>



>







 







|
|
|
>





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
...
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
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
...
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
        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();

    // remember our last trip
    // so it can be removed if it is a dead end, or if it is a scuccesful conclusion
    *src = *dst;
    *dst = u;

    // check if we are now holding our original commodity
    if( IsSuccess() )
    {


        if( *myQuantity > *myBestQuantity )
        {
            *myBestQuantity = *myQuantity;
            *myBestPath = *myPath;
        }
    }

    // check for leaf
    if( ! out_degree( u, g ) )
    {
        // we have reached a leaf of the graph tree
        // without successfully making a profit on our trades

        //throw runtime_error("leaf");
    }

}

void cVillage::AddTrader(
    eCommodity sell,
    eCommodity buy,
................................................................................
    AddTrader( eCommodity::wood, eCommodity::sand, 2 );
    AddTrader( eCommodity::sand, eCommodity::gras, 0.5 );
    AddTrader( eCommodity::gras, eCommodity::sand, 1);
    AddTrader( eCommodity::sand, eCommodity::wood, 0.25);
    AddTrader( eCommodity::gras, eCommodity::wood, 0.3333);

}

void cVillage::ConstructProblem4()
{
    /* A small, tricky problem

    There are two paths

    1 - 2 - 3 which gives 4 woods

    and

    1 - 4 -2 - 3 which gives 6 woods

    Can we find the second, longer path that gives the better profit?

    */
    static eCommodity hold = eCommodity::wood;
    static float quantity = 1;
    myTraveler.myHold = &hold;
    myTraveler.myQuantity = &quantity;
    myTraveler.myInitiallHold = hold;
    myTraveler.myInitialQuantity = quantity;

    static vector<int> path;
    myTraveler.myPath = &path;

    AddTrader( eCommodity::wood,  eCommodity::wood, 1);

    AddTrader( eCommodity::sand, eCommodity::wood, 0.5 );
    AddTrader( eCommodity::gras, eCommodity::sand, 1 );
    AddTrader( eCommodity::wood, eCommodity::gras, 0.5 );
    AddTrader( eCommodity::sand, eCommodity::wood, 0.333 );

}

void cVillage::Display()
{
    int index = 0;
    graph_traits<trade_graph_t>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end) = vertices(myGraph); vi != vi_end; ++vi)
    {
................................................................................
                if( myGraph[ *svi ].mySell == myGraph[ *tvi ].myBuy )
                    add_edge( *svi, *tvi, myGraph );
            }
            index++;
        }
    }
    DisplayGraph();

    //ConvertToDAG();
}

bool cVillage::IsPotentiallyProfitablePath()
{
    return out_degree( 0, myGraph ) > 0;
}

void cVillage::ConvertToDAG()
{

    // visitor to detect back edges
    cTraveler vis;
    unsigned int src, dst;
    vis.src = &src;
    vis.dst = &dst;

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

            // 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 );
        }
    }
}

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;
    myTraveler.myBestQuantity = &bestQuantity;

    // The path giving the greatest profit
    vector< int > bestpath;
    myTraveler.myBestPath = &bestpath;

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

    // number of searches
................................................................................
        cout << v << " ";
    cout << endl;
}

int main()
{
    cVillage village;
//    village.ConstructProblem3(
//        500,                         // traders
//        200);                       // commodities
    village.ConstructProblem4();
    village.Display();
    village.Travel();

    return 0;
}

Changes to trade.h.

130
131
132
133
134
135
136



137
138
139
140
141
142
143
...
160
161
162
163
164
165
166


167
168
169
170
171
172
173
...
231
232
233
234
235
236
237

238
239
240
241
242
243
244
...
253
254
255
256
257
258
259


260
261
262
263
264
265
266

    /** 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
    */
................................................................................
        A back edge is one that returns the search to a previously found vertex,
        indicating a cycle.

        This will throw an exception when it occurrs
    */
    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
................................................................................
    */
    void AddTrader( int count );

    /** Construct test problems */

    void ConstructProblem1();
    void ConstructProblem2();


    /** Construct random village
        @param[in] trader_count number of random traders
        @param[in] commodity_count number ofcommodities
    */
    void ConstructProblem3(
        int trader_count,
................................................................................
    /** 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();

    /** Are there any proptentially profitable paths through the village
        @return true if there are such paths







>
>
>







 







>
>







 







>







 







>
>







130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
...
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
...
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

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

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

    float * myBestQuantity;
    vector< int > * myBestPath;

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

    /** Constructor
        @param[in] hold commodity
        @param[in] quantity
    */
................................................................................
        A back edge is one that returns the search to a previously found vertex,
        indicating a cycle.

        This will throw an exception when it occurrs
    */
    void back_edge( Edge e, Graph& g)
    {
        if( myfTrading )
            return;
        *src = source( e, g );
        *dst = target( e, g );
        throw runtime_error("cyclic");
    }

    /** Called by DFS when trader is visited
        @param[in] Vertex the trader
................................................................................
    */
    void AddTrader( int count );

    /** Construct test problems */

    void ConstructProblem1();
    void ConstructProblem2();
    void ConstructProblem4();

    /** Construct random village
        @param[in] trader_count number of random traders
        @param[in] commodity_count number ofcommodities
    */
    void ConstructProblem3(
        int trader_count,
................................................................................
    /** 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();

    void ConvertToDAG();

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

    /** Are there any proptentially profitable paths through the village
        @return true if there are such paths