Facebook
From Cukrowicz, 6 Years ago, written in C#.
This paste is a reply to Krawędzie grafu from Cukrowicz - view diff
Embed
Download Paste or View Raw
Hits: 356
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Threading;
  7. using System.Threading.Tasks;
  8.  
  9. namespace GraphEdgeCount
  10. {
  11.     class Program
  12.     {
  13.         static int MatrixSize = 10000;
  14.         static bool[,] Matrix = new bool[10000,10000];
  15.         static int Edges=0;
  16.        static Semaphore semaphoreObject = new Semaphore(initialCount: 1, maximumCount: 1, name: "Edge");
  17.         static void FillMatrix()
  18.         {
  19.             Random c = new Random();
  20.             for(int i=0;i<MatrixSize;i++)
  21.             {
  22.                 for(int j=0;j<i;j++)
  23.                 {
  24.                     if(c.Next(0,10)%2==0)
  25.                     {
  26.                         Matrix[i,j] = true;
  27.                         Matrix[j,i] = true;
  28.                     }                  
  29.                 }
  30.             }
  31.         }
  32.         static void AddToEdgesCount(int number)
  33.         {
  34.             semaphoreObject.WaitOne();
  35.             Edges += number;
  36.             semaphoreObject.Release();
  37.         }
  38.         static void CountEdgesFromNode(int NodeNumber)
  39.         {
  40.             int pom = 0;
  41.             for(int i=NodeNumber+1;i<MatrixSize;i++)
  42.             {
  43.                 if (Matrix[i, NodeNumber] == true)
  44.                     pom++;
  45.             }
  46.              AddToEdgesCount(pom);
  47.         }
  48.         static void CountAllEdges()
  49.         {
  50.             for (int i = 0; i < MatrixSize-1; i++)
  51.             {
  52.                 for(int j=i+1;j<MatrixSize;j++)
  53.                 {
  54.                     if (Matrix[i, j] == true)
  55.                         Edges++;
  56.                 }
  57.  
  58.             }
  59.         }
  60.         static void DisplayMatrix()
  61.         {
  62.             for (int i = 0; i < MatrixSize; i++)
  63.             {
  64.                 for (int j = 0; j <MatrixSize; j++)
  65.                 {
  66.                     if (Matrix[i,j]==true)
  67.                         Console.Write(1);
  68.                     else
  69.                         Console.Write(0);
  70.                 }
  71.                 Console.WriteLine();
  72.             }
  73.         }
  74.         static void Main(string[] args)
  75.         {
  76.             FillMatrix();
  77.             List<Thread> threadList = new List<Thread>();
  78.             //    DisplayMatrix();
  79.             Stopwatch parallel = new Stopwatch();
  80.             Stopwatch seq = new Stopwatch();
  81.  
  82.             parallel.Start();
  83.             for (int i=0;i<MatrixSize;i++)
  84.             {
  85.                 int n = i;
  86.                 Thread t = new Thread(() => CountEdgesFromNode(n));
  87.                 t.Start();
  88.                 threadList.Add(t);
  89.             }
  90.             foreach (var t in threadList)
  91.                 t.Join();
  92.  
  93.             parallel.Stop();
  94.             Console.WriteLine("{0} Edges counted in parallel, it took {1}",Edges, parallel.Elapsed);
  95.             Edges = 0;
  96.             seq.Start();
  97.             CountAllEdges();
  98.             seq.Stop();
  99.             Console.WriteLine("{0} Edges counted sequentially, it took {1}", Edges, seq.Elapsed);
  100.         }
  101.     }
  102. }
  103.