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

Overview
Comment:cRoute
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | trunk
Files: files | file ages | folders
SHA1:073ecb6d9018884bb5956bd1bee5a8d4af615732
User & Date: ravenspoint 2016-05-30 16:33:07
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
Changes

Changes to trade.cpp.

78
79
80
81
82
83
84
85
86
87
88
89
90

91
92
93
94
95
96
97
...
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
...
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
...
382
383
384
385
386
387
388
389
390
391
392

393
394
395
396
397
398
399
    // 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
................................................................................
    // 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
................................................................................
            // ( 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
                    bestQuantity = *(myTraveler.myQuantity);
                    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();
................................................................................

        }
    }

    // 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(
//        500,                         // traders







<
<
<
<
<
<
>







 







|
|
<
<
<
|







 







|
|
|
|
|
|
|
|
|
|
|







 







|
<
<
<
>







78
79
80
81
82
83
84






85
86
87
88
89
90
91
92
...
307
308
309
310
311
312
313
314
315



316
317
318
319
320
321
322
323
...
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
...
374
375
376
377
378
379
380
381



382
383
384
385
386
387
388
389
    // 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() )
    {






        myBestRoute->Compare( *myQuantity, *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
................................................................................
    // Construct graph of potentiall profitable trips between traders
    ConstructSensibleTrips();

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

    // The greatest profit found
    cRoute bestRoute;
    bestRoute.myFinalQuantity = -1;



    myTraveler.myBestRoute = &bestRoute;

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

    // number of searches
................................................................................
            // ( 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
//                    bestQuantity = *(myTraveler.myQuantity);
//                    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();
................................................................................

        }
    }

    // Display the most profitable path found
    cout << "\n=========================\n";
    //cout << count << " iterations\n";
    bestRoute.Display();




}

int main()
{
    cVillage village;
//    village.ConstructProblem3(
//        500,                         // traders

Changes to trade.h.

74
75
76
77
78
79
80

























81
82
83
84
85
86
87
...
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
...
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
            stringstream sst;
            sst << "c" << (int) c;
            ret = sst.str();
        }
        return ret;
    }
};

























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

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

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







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







 







|
<







 







|
|







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
...
155
156
157
158
159
160
161
162

163
164
165
166
167
168
169
...
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
            stringstream sst;
            sst << "c" << (int) c;
            ret = sst.str();
        }
        return ret;
    }
};

class cRoute
{
public:
    vector<int> myPath;
    float myFinalQuantity;

    bool Compare( float q, vector<int>& p )
    {
        if( q > myFinalQuantity )
        {
            myFinalQuantity = q;
            myPath = p;
            return true;
        }
        return false;
    }
    void Display()
    {
        cout << "Best: Holding " << myFinalQuantity << " from trades with ";
        for( auto v : myPath )
            cout << v << " ";
        cout << endl;
    }
};
/** 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.
................................................................................

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

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

    cRoute * myBestRoute;


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

    /** Constructor
        @param[in] hold commodity
        @param[in] quantity
................................................................................

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