It is necessary to make a random sequence of the route

Question

I have 3 databases in Base(1) containing data about cities FROM which I need to make a trip. For simplicity, let's call them POINTS FROM. There is also Base(2) which contains cities TO which I need to make a trip. Let's call them POINTS TO for simplicity. And there is Base(3) which contains the names of BUSES that can be used for traveling between cities, but each bus has its own list of cities FROM which it can depart and cities TO which it can arrive.

The task is to create a sequence of BUSES in such a way that all buses are used, and each POINT FROM and POINT TO is visited. Ideally, we should use each BUS at most once, but if necessary, a BUS can be used multiple times. The initial city is randomly selected from the list in Base(1). After the first trip, the city at the end of the previous round is taken as the initial city for the next round. The sequence should always be as random as possible while striving to minimize the number of steps. A sequence is considered successful if all BUSES are used and all cities FROM in Base(1) are left and all cities TO in Base(2) are reached. Additionally, a BUS cannot depart from and arrive at the same city.

Here's an example of the data from the databases:

Base(1) in the format "City1,City2,City3..." - "CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,MOONSTONE,RIVERDALE,CEDARVILLE,MAPLEWOOD"
Base(2) in the format "City1,City2,City3..." - "CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,MOONSTONE,RIVERDALE,CEDARVILLE,MAPLEWOOD"
Base(3) in the format "BusName1:CityFROM1,CityFROM2,CityFROM3...@CityTO1,CityTO2,CityTO3...
BusName2:CityFROM1,CityFROM2,CityFROM3...@CityTO1,CityTO2,CityTO3..." 
"TransLink:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
GoBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
SwiftRide:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
SpeedyBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE
CityHopper:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@MOONSTONE
RouteMasters:MOONSTONE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW
MetroTrans:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE
MegaBus:MAPLEWOOD,CRYSTALVILLE@MAPLEWOOD,CRYSTALVILLE"

Here's a small excerpt of the desired sequence:

Starting with the city CRYSTALVILLE,
CRYSTALVILLE (CityHopper) - MOONSTONE,
MOONSTONE (RouteMasters) - HARMONYVILLE,
HARMONYVILLE (SpeedyBus) - WILLOWBROOK,
WILLOWBROOK (MetroTrans) - RIVERDALE,
RIVERDALE (MetroTrans) - CEDARVILLE,
CEDARVILLE (MetroTrans) - OCEANVIEW,
OCEANVIEW (GoBus) - SILVERLAKE,
and so on until all BUSES and cities from Base(1) and Base(2) are used.

I have very little experience in creating such sequences or programming. I tried to solve this task on my own, but I always ended up with either an infinite sequence or it broke at steps 3-11. As I understand it, everything breaks because either the BUSES run out or there are no available cities since I used a scheme where using a BUS or Cities from Base(1) and Base(2) removes them from the base, and in the absence of 1-2 databases, it took data from additional UNCHANGED bases that completely copied the used bases at the beginning of the path that satisfy the conditions but took randomly, which made the sequence either infinite or not satisfying the condition of the minimum number of steps, and I got stuck.

Answer 1

This looks like an unusual formulation of the travelling salesman problem. The "buses" define the directed edges, and the cities define the vertices. If you ignore the requirement that all the "buses" be used, than it IS the travelling salesman problem.

So the algorithm would be:

• generate directed graph ( buses define edges, cities are vertices )
• apply travelling salesman algorithm
• LOOP over edges in solution
  • SELECT bus that covers edge, if possible bus that has not previously been used.

Here is the graph from your example

Here is the route with buses used

MAPLEWOOD ->(MegaBus)-> CRYSTALVILLE ->(MegaBus)-> WILLOWBROOK ->(TransLink)-> HARMONYVILLE ->(GoBus)-> SILVERLAKE ->(SwiftRide)-> OCEANVIEW ->(MetroTrans)-> MOONSTONE ->(CityHopper)-> CRYSTALVILLE ->(RouteMasters)-> RIVERDALE ->(MetroTrans)-> CEDARVILLE ->(MetroTrans)-> MAPLEWOOD

Here is the C++ code that implements this

main()
{
    std::string buses =
    "TransLink:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "GoBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "SwiftRide:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "SpeedyBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE\n"
    "CityHopper:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@MOONSTONE\n"
    "RouteMasters:MOONSTONE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "MetroTrans:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE\n"
    "MegaBus:MAPLEWOOD,CRYSTALVILLE@MAPLEWOOD,CRYSTALVILLE\n";

    raven::graph::cGraph g;
    g.directed();
    std::map<std::pair<std::string, std::string>, std::vector<std::string>> mpBus;
    std::stringstream ss(buses);
    std::string line;
    while (getline(ss, line))
    {
        // std::cout << line << "\n";
        int p1 = line.find(":");
        int p2 = line.find("@", p1);
        std::string busName = line.substr(0, p1);
        std::string srcs = line.substr(p1 + 1, p2 - p1 - 1);
        std::string dsts;
        dsts = line.substr(p2 + 1);
        auto vs = ParseCSV(srcs);
        auto vd = ParseCSV(dsts);
        for (auto &s : vs)
            for (auto &d : vd)
            {
                // std::cout << s << " -> " << d  << "\n";
                g.add(s, d);
                auto it = mpBus.find(std::make_pair(s, d));
                if (it == mpBus.end())
                {
                    std::vector<std::string> vb{busName};
                    mpBus.insert(
                        std::make_pair(
                            std::make_pair(s, d),
                            vb));
                }
                else
                    it->second.push_back(busName);
            }
    }

    // for( auto& s : g.edgeList() )
    //     std::cout <<"l " << g.userName(s.first) <<" "<< g.userName(s.second) << " 1\n";

    raven::graph::cTourNodes T;
    T.calculate(g);

    std::set<std::string> setUsed;

    std::string src, dst;
    std::string tourText;
    bool first = true;
    for (int v : T.getTour())
    {
        if (first)
        {
            first = false;
            src = g.userName(v);
            continue;
        }
        dst = g.userName(v);
        auto vBus = mpBus.find(std::make_pair(src, dst))->second;
        std::string busUsed;
        for (auto &b : vBus)
        {
            auto itUsed = setUsed.find(b);
            if (itUsed == setUsed.end())
            {
                busUsed = b;
                setUsed.insert(b);
                break;
            }
        }
        if( busUsed.empty() )
            busUsed = vBus[0];

        tourText += g.userName(v) + " ->(" + busUsed + ")-> ";
        src = dst;
    }
    std::cout << tourText << "\n";

    return 0;
}

Complete application code at https://github.com/JamesBremner/so76373906