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

Overview
Comment:fix handling of leaves in DFS
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:70b33f7e963a949788277876feeb0b5b8b31322d
User & Date: ravenspoint 2016-05-30 13:47:02
Context
2016-05-30
14:20
construct large random village check-in: bd58c1ec81 user: ravenspoint tags: trunk
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
Changes

Changes to trade.cpp.

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
...
121
122
123
124
125
126
127












128
129
130
131
132
133
134
...
142
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/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 );
................................................................................
        {
            cout << "Trader " << index << " ";
            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

................................................................................
            {
                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;
}







|
|
|
|
|
|
|
|
|

|
|
|
|
|
|

|
|
|

|
|
|

|
|
|

|
|

|
|

>
>
>
|
|
|
|
<
|
|

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







 







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







 







>


|
|
|
|

|
|

|
|

|
|

|
|
|
|

|
|
|
|
|
|
|
|

|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

|
|

|
|
|
|
|
|
|

|
|
|
|
|
|
|










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
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
...
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
#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();

    *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

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

}

void cVillage::AddTrader(
    eCommodity sell,
    eCommodity buy,
    float price )
{
    myGraph[ add_vertex( myGraph ) ] = cTrader( sell, buy, price );
................................................................................
        {
            cout << "Trader " << index << " ";
            myGraph[ *vi ].Display();
        }
        index++;
    }
}
void cVillage::DisplayGraph()
{
    cout << num_edges( myGraph ) <<" Trips\n";
    graph_traits<trade_graph_t>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(myGraph); ei != ei_end; ++ei)
    {
        std::cout << "(" << source(*ei, myGraph)
                  << "," << target(*ei, myGraph) << ") ";
    }
    cout << endl;
}

void cVillage::ConstructSensibleTrips()
{
    // A sensible trip between two traders:
    // the source is selling what the target is buying

    // loop over all pairs of traders

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

    // 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 < 5 )
    {
        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.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
...
208
209
210
211
212
213
214

215
216
217
218
219
220
221
        , 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
        {
................................................................................
    /** 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

    */







|



|







 







>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
...
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
        , 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
        {
................................................................................
    /** Construct test problems */

    void ConstructProblem1();
    void ConstructProblem2();

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

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

    */