fork(2) download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<ctime>
  4. #include<cmath>
  5. #include<vector>
  6. #include<deque>
  7. using namespace std;
  8.  
  9. //隣接行列がgraphであるようなグラフにおいて、startからgoalまで幅優先探索を行う。
  10. //goalまでたどりつけばtrue、たどりつけなければfalseを返す。
  11. //trueが返るときには、prevに「直前の頂点」の情報が入っている。
  12. bool bfs(const vector<vector<int> > &graph, int start, int goal, vector<int> &prev)
  13. {
  14.   const int n = graph.size(); //n:グラフの頂点数
  15.  
  16.   //「直前の頂点」の情報をクリア
  17.   for(int i = 0; i < n; ++i){
  18.     prev[i] = -1;
  19.   }
  20.   //アルゴリズムの都合上、出発点の「直前」は出発点自身とする:
  21.   prev[start] = start;
  22.  
  23.   //「まだたどってない頂点」をキューで管理する。最初は出発点だけ。
  24.   deque<int> frontier;
  25.   frontier.push_back(start);
  26.  
  27.   //キューに頂点が残っていたらループ
  28.   while(! frontier.empty()){
  29.     int vertex = frontier[0];
  30.     frontier.pop_front();
  31.  
  32.     //目的地に到達していれば終わり
  33.     if(vertex == goal){
  34.       return true;
  35.     }
  36.  
  37.     //「次にたどるべき頂点」をキューに追加する
  38.     for(int next = 0; next < n; ++next){
  39.       //はじめて見る頂点で今の頂点から行けるものをキューに追加
  40.       if(prev[next] == -1 && graph[vertex][next] > 0){
  41.     prev[next] = vertex;
  42.     frontier.push_back(next);
  43.       }
  44.     }
  45.   }
  46.  
  47.   //目的地にたどりつかなかったのでfalse.
  48.   return false;
  49. }
  50.  
  51. //辺(i,j)の容量がgraph[i][j]であるようなグラフにおけるsourceからsinkへの最大フローを求める。
  52. //求めた最大フローはflowに入る。
  53. //最大フローの値を返す。
  54. int maxFlow(vector<vector<int> > graph, int source, int sink, vector<vector<int> > &flow)
  55. {
  56.   const int n = graph.size(); //n:グラフの頂点数
  57.  
  58.   //フローflowと値valueを初期化
  59.   for(int i = 0; i < n; ++i){
  60.     for(int j = 0; j < n; ++j){
  61.       flow[i][j] = 0;
  62.     }
  63.   }
  64.   int value = 0;
  65.  
  66.   //幅優先探索の準備
  67.   vector<int> prev(n);
  68.  
  69.   //経路が見付かる限りフローを更新
  70.   while(bfs(graph,source,sink,prev)){
  71.     //prevに従って,見付けた経路の容量の最小値を求める.
  72.     int capacity = graph[prev[sink]][sink];
  73.  
  74.     for(int v = sink; v != source; v = prev[v]){
  75.       if(capacity > graph[prev[v]][v]){
  76.     capacity = graph[prev[v]][v];
  77.       }
  78.     }
  79.  
  80.     //フローと残余ネットワークを更新
  81.     for(int v = sink; v != source; v = prev[v]){
  82.       int pv = prev[v];
  83.       flow[pv][v] += capacity;
  84.       graph[pv][v] -= capacity;
  85.       graph[v][pv] += capacity;
  86.     }
  87.     value += capacity;
  88.   }
  89.  
  90.   return value;
  91. }
  92.  
  93. double exprand(double average)
  94. {
  95.   double r = rand() / (RAND_MAX + 1.0);
  96.   return -log(1-r) * average;
  97. }
  98.  
  99. struct Packet {
  100.   int source; //入力ポート
  101.   int dest; //出力ポート
  102.   int arriveTime; //ハブへの到着時刻
  103.   int deliverTime; //ハブからの排出時刻
  104. };
  105.  
  106. typedef deque<Packet> PacketQueue;
  107.  
  108. //ハブに届いたパケットを生成する.
  109. Packet makePacket(int in_port, int current, int ports)
  110. {
  111.   Packet packet;
  112.  
  113.   packet.source = in_port;
  114.   packet.dest = int(rand() / (RAND_MAX + 1.0) * (ports-1));
  115.   if(packet.dest >= packet.source){
  116.     ++packet.dest;
  117.   }
  118.   packet.arriveTime = current;
  119.   packet.deliverTime = -1;
  120.  
  121.   return packet;
  122. }
  123.  
  124. //ポート数Ports,スイッチ転送量xppcパケット/クロックのハブのシミュレーションを行う.
  125. //パケットの平均到着時間間隔はTa,シミュレーション時間はdurationとする.
  126. void runSimulation(int Ports, int xppc, double Ta, int duration)
  127. {
  128.   //入力バッファは入力ポートごとかつ出力ポートごと
  129.   vector<vector<PacketQueue> > inputBuffer(Ports, vector<PacketQueue>(Ports));
  130.  
  131.   //次に各入力ポートにパケットがくるタイミング
  132.   vector<int> nextPacketTime(Ports);
  133.  
  134.   //最初のパケットのタイミングを設定して....
  135.   for(int in_port = 0; in_port < Ports; ++in_port){
  136.     nextPacketTime[in_port] = int(exprand(Ta));
  137.   }
  138.  
  139.   //シミュレーション開始
  140.   printf("Simulation start\n");
  141.   for(int current = 0; current < duration; ++current){
  142.     //まず入力パケットをもらう
  143.     for(int in_port = 0; in_port < Ports; ++in_port){
  144.       while(current == nextPacketTime[in_port]){
  145.     Packet packet = makePacket(in_port, current, Ports);
  146.     inputBuffer[in_port][packet.dest].push_back(packet);
  147.     nextPacketTime[in_port] += int(exprand(Ta));
  148.       }
  149.     }
  150.  
  151.     //グラフを作って
  152.     const int Vertices = 2*Ports+2;
  153.     const int Source = 2*Ports;
  154.     const int Sink = 2*Ports+1;
  155.     vector<vector<int> > graph(Vertices, vector<int>(Vertices));
  156.     for(int in_port = 0; in_port < Ports; ++in_port){
  157.       for(int out_port = 0; out_port < Ports; ++out_port){
  158.     graph[in_port][Ports+out_port] = inputBuffer[in_port][out_port].size();
  159.       }
  160.     }
  161.     for(int in_port = 0; in_port < Ports; ++in_port){
  162.       graph[Source][in_port] = xppc;
  163.     }
  164.     for(int out_port = 0; out_port < Ports; ++out_port){
  165.       graph[Ports+out_port][Sink] = xppc;
  166.     }
  167.  
  168.     //最大フローを求め
  169.     vector<vector<int> > flow(Vertices, vector<int>(Vertices));
  170.     maxFlow(graph, Source, Sink, flow);
  171.  
  172.     //それに従ってパケットを送り出す
  173.     for(int in_port = 0; in_port < Ports; ++in_port){
  174.       for(int out_port = 0; out_port < Ports; ++out_port){
  175.     for(int p = 0; p < flow[in_port][Ports+out_port]; ++p){
  176.       inputBuffer[in_port][out_port][0].deliverTime = current;
  177.       inputBuffer[in_port][out_port].pop_front();
  178.     }
  179.       }
  180.     }
  181.   }
  182.  
  183.   //時間がきたのでシミュレーション終了
  184.   printf("Simulation finished\n");
  185. }
  186.  
  187. //テスト用のmain
  188. int main()
  189. {
  190.   const int Ports = 4; //ポート数
  191.  
  192.   const double Ta = 2; //平均到着時間間隔
  193.   const int T = 1000; //シミュレートする時間数
  194.   const int P = 1; //1ポートあたり転送パケット数
  195.  
  196.   srand(time(NULL));
  197.   runSimulation(Ports, P, Ta, T);
  198.   return 0;
  199. }
Success #stdin #stdout 0.02s 2820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Simulation start
Simulation finished
https://ideone.com/T3e0j
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!