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

Overview
Comment:check for stop condition
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:b91609e6889261e02cf05c0e30d9a040be129fa6
User & Date: ravenspoint 2016-05-30 15:21:04
Context
2016-05-30
16:20
Problem4 check-in: 100b488c1e user: ravenspoint tags: trunk
15:21
check for stop condition check-in: b91609e688 user: ravenspoint tags: trunk
14:20
construct large random village check-in: bd58c1ec81 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
..
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
...
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
...
218
219
220
221
222
223
224
225





226
227
228
229
230
231
232
...
240
241
242
243
244
245
246
247
248


249
250
251
252
253
254
255
256
...
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
...
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
        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();



    *src = *dst;
    *dst = u;

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

    // 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

        cout << "leaf at " << u << endl;
        throw runtime_error("leaf");
    }

}

void cVillage::AddTrader(
    eCommodity sell,
................................................................................
    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::ConstructProblem3()
{
    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::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);

    // Add some random traders
    for( int k = 0; k < 200; k++ )
        AddTrader( 200 );
}

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();





}

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

................................................................................
    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 < 500 )
    {
        try
        {
            // go back to go
            myTraveler.Restart();

            // do a depth first search, trading as we go
................................................................................

            // 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
................................................................................
                    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.ConstructProblem3();


    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
..
88
89
90
91
92
93
94

95
96
97
98
99
100
101
...
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
...
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
...
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
...
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
...
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
        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
................................................................................

    // 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,
................................................................................
    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::ConstructProblem3( int trader_count, int commodity_count )
{
    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);


    // Add some random traders
    for( int k = 0; k < trader_count; k++ )
        AddTrader( commodity_count );

    // add sample traders that give a successful route through the village
    // even if the random traders do not
    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();

................................................................................
    vector< int > bestpath;

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

    // number of searches
    int count = 0;

    // loop until seaching completes
    while( 1 )
    {
        try
        {
            // go back to go
            myTraveler.Restart();

            // do a depth first search, trading as we go
................................................................................

            // The search was completed without success
            // ( trading for the original commodity )
            break;
        }
        catch( runtime_error& e )
        {

            myTraveler.Display();
            if( myTraveler.IsSuccess() )
            {
                // check for most progitable found so far
                if( *(myTraveler.myQuantity) > bestQuantity )
                {
                    // remember out most profitable path
................................................................................
                    bestpath = *(myTraveler.myPath);

                }
            }

            // prevent repeating this same path
            // by removing the trip between the last two traders

            remove_edge( src, dst, myGraph );

            //cout << src << " - " << dst << endl;
            //DisplayGraph();

            count++;

            // check for search completed
            // that is we have eliminated the last
            // potentially profitable route through the village
            if( ! IsPotentiallyProfitablePath() )
                break;

        }
    }

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

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

    return 0;
}

Changes to trade.h.

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
...
226
227
228
229
230
231
232





233


234
235
236
237
238
239
240
...
245
246
247
248
249
250
251
252











253
    }

    /** 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;
        //Display();
    }
    bool IsSuccess()
    {
        return *myHold == myInitiallHold;
    }
};
................................................................................
    */
    void AddTrader( int count );

    /** Construct test problems */

    void ConstructProblem1();
    void ConstructProblem2();





    void ConstructProblem3();



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

    /** Display potentially profitable trips betwee traders */
    void DisplayGraph();

................................................................................

    */
    void ConstructSensibleTrips();

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












};







|
>
>
>









>
|
|





>

|







 







>
>
>
>
>
|
>
>







 








>
>
>
>
>
>
>
>
>
>
>

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
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
...
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
    }

    /** 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.

        Throws exception if leaf is reached without making a profit

    */
    template < typename Vertex, typename Graph >
    void discover_vertex( Vertex u, Graph& g);

    void Display()
    {
//        for( auto v : *myPath )
//            cout << v << " ";
//        cout << "\n";
//        if( IsSuccess() )
            cout << "holding " << *myQuantity
                 << " of " << cTrader::Name( *myHold ) << endl;
    }
    void Restart()
    {
        *myHold = myInitiallHold;
        *myQuantity = myInitialQuantity;
        *dst = 0;       // always start at zeroth trader ( dummy starting position )
        myPath->clear();
        //cout << endl;
        //Display();
    }
    bool IsSuccess()
    {
        return *myHold == myInitiallHold;
    }
};
................................................................................
    */
    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,
        int commodity_count);

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

    /** Display potentially profitable trips betwee traders */
    void DisplayGraph();

................................................................................

    */
    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

        These paths connect traders whose commodities match.
        ( The source trader is selling the commodity the target trader is busying )
        The paths will have to be traversed to determine if they are
        successful and profitable

    */
    bool IsPotentiallyProfitablePath();

};