1

私は非常に新しい C++ プログラマーで、2 つの特定のノード (グラフ) 間のすべてのパスを見つけようとする次のコードを実装しようとしています。これは、接続されたエッジのペアと特定のノードのペアを使用して、それらの間のすべての可能なパスをコンソールからの入力として計算し、コンソールへの特定のノードペア間のすべての可能なパス。アルゴリズムは非常にうまく機能します。ただし、txtファイルからの入力/出力の読み取り/書き込みをしたいと思います。しかし、私はそれをすることができませんでした。正しい方法を示す人はいますか？

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;

vector<vector<int> >GRAPH(100);
inline void printPath(vector<int>path)
{
    cout<<"[ ";
    for(int i=0; i<path.size(); ++i)
    {
        cout<<path[i]<<" ";
    }
    cout<<"]"<<endl;
}

bool checksAdjacencyNode(int node,vector<int>path)
{
    for(int i=0; i<path.size(); ++i)
    {
        if(path[i]==node)
        {
            return false;
        }
    }
    return true;
}

int findpaths(int sourceNode ,int targetNode,int totalnode,int totaledge)
{
    vector<int>path;
    path.push_back(sourceNode);
    queue<vector<int> >q;
    q.push(path);
    while(!q.empty())
    {
        path=q.front();
        q.pop();
        int lastNodeOfPath=path[path.size()-1];
        if(lastNodeOfPath==targetNode)
        {
            printPath(path);
        }
        for(int i=0; i<GRAPH[lastNodeOfPath].size(); ++i)
        {
            if(checksAdjacencyNode(GRAPH[lastNodeOfPath][i],path))
            {
                vector<int>newPath(path.begin(),path.end());
                newPath.push_back(GRAPH[lastNodeOfPath][i]);
                q.push(newPath);
            }
        }
    }
    return 1;
}

int main()
{
    int T,totalNodes,totalEdges,u,v,sourceNode,targetNode;
    T=1;
    while(T--)
    {
        totalNodes=6;
        totalEdges=11;
        for(int i=1; i<=totalEdges; ++i)
        {
            scanf("%d%d",&u,&v);
            GRAPH[u].push_back(v);
        }
        sourceNode=1;
        targetNode=4;
        findpaths(sourceNode,targetNode,totalNodes,totalEdges);
    }
    return 0;
}

Input::
1 2 
1 3 
1 5 
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3

output:

[ 1 2 4 ]
[ 1 3 4 ]
[ 1 5 4 ]
[ 1 2 3 4 ]
[ 1 5 6 3 4 ]
4

2 に答える 2

0

出力に関しては、単純に a を使用して、使用するstd::ofstream場所を置き換えることができますstd::cout。

inline std::ostream& os printPath(std::ostream& os, vector<int>path)
{
    os <<"[ ";
    for(int i=0;i<path.size();++i)
    {
        os<<path[i]<<" ";
    }
    os<<"]"<<endl;
}

int main(int argc, char** argv)
{
    if(argc > 1)
    {
        std::ofstream ofs(argv{1]);

        // ...
        printPath(ofs,path)
    }
}

ファイルからこの形式を読み取ることに関しては、s.th をお勧めします。このような：

std::ifstream ifs("MyGraphFile.txt");

while(ifs && !ifs.eof())
{
    std::string line = std::string::getline(ifs);
    // strip the '[' and ']' characters
    line = line.substr(1,line.length() - 2);
    std::istringstream iss(line);

    std::vector<int> currentInputs;
    int value;
    while(iss >> value)
    {
        currentInputs.push_back(value);
    }

    GRAPH.push_back(currentInputs);
    currentInputs.clear();
}
于 2013-07-20T18:33:06.197 に答える
0

これは Boost Graph Library を使えば簡単にできると思いました。そして、ある意味ではそうです。

入力ファイルの解析:

std::vector<std::pair<int, int>> parse_input(const char* const fname, int& min_vertex, int& max_vertex)
{
    std::vector<std::pair<int, int>> data;

    min_vertex = std::numeric_limits<int>::max();
    max_vertex = std::numeric_limits<int>::min();

    std::ifstream ifs("input.txt");
    std::string line;
    while (std::getline(ifs, line))
    {
        int a, b;
        if (std::istringstream(line) >> a >> b)
        {
            data.emplace_back(a, b);

            if (a>b) std::swap(a,b);
            min_vertex = std::min(min_vertex, a);
            max_vertex = std::max(max_vertex, b);
        }
        else throw "oops";
    }
    return data;
}

次に、プログラムの単純なスタブは次のようになります。

struct my_visitor : boost::default_bfs_visitor 
{
    template < typename Vertex, typename Graph >
        void discover_vertex(Vertex const& u, const Graph & g) const
        {
            std::cout << "discover_vertex: " << u << "\n";
        }
};

int main() 
{
    typedef boost::adjacency_list<> Graph;
    typedef Graph::vertex_descriptor Vertex;

    int min_vertex, max_vertex;
    auto const lines = parse_input("input.txt", min_vertex, max_vertex);

    const Graph G(begin(lines), end(lines), max_vertex+1);
    print_graph(G);

    const auto source = vertex(min_vertex, G);

    breadth_first_search // visit ... needs explicit ColorMap
        (G, source, boost::visitor(my_visitor()));
}

これはコンパイルして動作します。Coliru でライブを参照してください。

ただし、BFS は既定ですべての頂点を 1 回だけ検索します (色分けを使用)。

0 --> 
1 --> 2 3 5 
2 --> 1 3 4 
3 --> 4 
4 --> 3 
5 --> 6 4 
6 --> 3 
discover_vertex: 1
discover_vertex: 2
discover_vertex: 3
discover_vertex: 5
discover_vertex: 4
discover_vertex: 6

実際にはbreadth_first_visit、すべてのパスを生成するために、各頂点の色を WHITE のままにして、代わりに使用する必要があります。

breadth_first_visit悲しいことに、適切なカスタムをフィードする方法を確認しようとすると、時間がなくなりましたColorMap。

入力の解析のみであれば、これが何らかの形で役立つことを願っています。

于 2013-07-20T20:26:46.463 に答える