Based on the Python answer here, I translated the same code in C++
#include<set>
#include<vector>
#include<map>
#include<array>
#include<algorithm>
using namespace std;
typedef vector<vector<set<int> > > fl;
fl fw(int n, vector<array<float,4>> edge)
{
vector<vector<float> > cost(n);
vector<vector<set<int> > > next_node(n);
for(int i=0;i<n;i++)
{
next_node[i]=vector<set<int> >(n);
cost[i]=vector<float>(n,INT_MAX);
cost[i][i]=0;
}
for(auto &i:edge)
{
if(i[2]<cost[i[0]][i[1]])
{
cost[i[0]][i[1]]=i[2];
next_node[i[0]][i[1]]=set<int>{i[1]};
}
else if(i[2]==cost[i[0]][i[1]] && i[0]<INT_MAX)
{
(next_node[i[0]][i[1]]).insert(i[1]);
}
}
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
float cost_ik_kj = cost[i][k]+cost[k][j];
if(cost_ik_kj < cost[i][j])
{
cost[i][j]=cost_ik_kj;
next_node[i][j]=set<int>{next_node[i][k]};
}
else if(cost_ik_kj==cost[i][j] && cost_ik_kj<MAX)
{
(next_node[i][j]).insert((next_node[i][k]).begin(),(next_node[i][k]).end())
}
}
}
}
return next_node;
}
But for the all_paths function mentioned in the above answer, I'm not finding any appropriate method to translate the Python code. Also, can the same translated code can be run as an iterable? What will be the C++11 equivalent of all_paths function since there will be exponential number of such paths and I want something similar to a on-the-fly generator function to minimize the memory usage?
Note that the input dataset is in the form of edge list.
Aucun commentaire:
Enregistrer un commentaire