gistfile1.txt

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace Nurmeev
{
    class Graph
    {
        #region variables declaration
        Dictionary<int, List<int>> graph;
        List<bool> visitedVertices;
        List<int> discoveryTime;
        List<int> lowTime;
        List<bool> ArticulationPoints;
        List<List<int>> components;


        int time = 0;


        List<bool> visitedVerticesConComp;

        List<bool> visvert;
        List<string> bic;


        List<int> bridgesFrom;
        List<int> bridgesTo;

        #endregion
        #region matrix and Adjacency list creation

        public int[,] createRandomMatrix(int columns, int rows)
        {
            int[,] matrix = new int[columns, rows];
            Random r = new Random();


            for (int i = 0; i < columns; i++)
            {
                for (int j = 0; j < rows; j++)
                {
                    int number = r.Next(0, 8);

                    if (number == 1 && i != j)
                    {
                        matrix[i, j] = 1;
                        matrix[j, i] = 1;


                    }

                }
            }
            //printing out this matrix
         /*   for (int k = 0; k < matrix.GetLength(0); k++)
            {
                Console.WriteLine();
                for (int n = 0; n < matrix.GetLength(1); n++)
                {
                    Console.Write(matrix[k, n] + " ");

                }
            }*/
            return matrix;



        }





        public Dictionary<int, List<int>> createRandomGraph(int[,] matrix)
        {
            graph = new Dictionary<int, List<int>>();
            visitedVertices = new List<bool>();


            //articulation points
            discoveryTime = new List<int>();
            lowTime = new List<int>();
            ArticulationPoints = new List<bool>();
            components = new List<List<int>>();
            visitedVerticesConComp = new List<bool>();
            bridgesFrom = new List<int>();
            bridgesTo = new List<int>();






            for (int k = 0; k < matrix.GetLength(0); k++)
            {
                //might be incorrect
                graph[k] = new List<int>();
                visitedVertices.Add(false);
                discoveryTime.Add(0);
                lowTime.Add(0);
                ArticulationPoints.Add(false);
                visitedVerticesConComp.Add(false);


                components.Add(new List<int>());

                for (int n = 0; n < matrix.GetLength(1); n++)
                {
                    if (matrix[k, n] != 0)
                    {
                        graph[k].Add(n);


                    }

                }
            }
         /* Console.WriteLine("\n\nconverted form");
            for (int a = 0; a < graph.Count(); a++)
            {

                Console.Write(a + " = ");
                for (int b = 0; b < graph[a].Count(); b++)
                {
                    Console.Write(graph[a][b]);
                }
                Console.WriteLine();
            }*/
            return graph;



        }


        #endregion


        #region searching for Bridges using low/disc values
        public void FindBridges()
        {
            /*
             * add here logic to reset the values of object
             */

            for (int i = 0; i < graph.Count(); i++)
            {
                if (visitedVertices[i] != true)
                {
                    DFSforBridges(i);
                }
            }
        }

        public void DFSforBridges(int vertex, int p = -1)
        {
            visitedVertices[vertex] = true;
            discoveryTime[vertex] = lowTime[vertex] = time++;
            for (int i = 0; i < graph[vertex].Count(); i++)
            {
                int to = graph[vertex][i];
                if (to == p) continue;
                if (visitedVertices[to])
                {
                    lowTime[vertex] = Math.Min(lowTime[vertex], discoveryTime[to]);
                }
                else
                {
                    DFSforBridges(to, vertex);
                    lowTime[vertex] = Math.Min(lowTime[vertex], discoveryTime[to]);
                    if (lowTime[to] > discoveryTime[vertex])
                    {
                        Console.WriteLine(vertex + " " + to);
                        bridgesFrom.Add(vertex);
                        bridgesTo.Add(to);

                    }
                }

            }
     
        }
        #endregion
        #region searching for articulation points using low/disc values
        public void ArticulationPointsSolve()
        {
            for (int i = 0; i < graph.Count(); i++)
            {
                if (visitedVertices[i] != true)
                {
                    searchForAP(i);
                }
            }
            for (int i = 0; i < ArticulationPoints.Count(); i++)
            {
                if (ArticulationPoints[i] == true)
                {
                    //  Console.WriteLine(i + " ");
                }
            }

        }

      

        public void searchForAP(int vertex, int parent = -1)
        {
            visitedVertices[vertex] = true;
            discoveryTime[vertex] = lowTime[vertex] = time++;
            int children = 0;
            for (int i = 0; i < graph[vertex].Count(); i++)
            {
                int to = graph[vertex][i];
                if (to == parent) continue;
                if (visitedVertices[to])
                {
                    lowTime[vertex] = Math.Min(lowTime[vertex], discoveryTime[to]);
                }
                else
                {
                    searchForAP(to, vertex);
                    lowTime[vertex] = Math.Min(lowTime[vertex], lowTime[to]);
                    if (lowTime[to] >= discoveryTime[vertex] && parent != -1)
                    {
                        ArticulationPoints[vertex] = true;
                    }
                    ++children;
                }
            }
            if (parent == -1 && children > 1)
            {
                ArticulationPoints[vertex] = true;
            }


        }

        #endregion
        #region searching for biconnected components using information about art points that exist
        public void findBIcomponentsBad() 
        {
            
            visvert = new List<bool>();
            bic = new List<string>();
            int counter = 0;
            int globalcounter = 0;
            for (int i = 0; i < graph.Count(); i++) 
            {
                visvert.Add(false);
                bic.Add("");

            }

            for (int i = 0; i < ArticulationPoints.Count(); i++)
            {
                if (ArticulationPoints[i] == true)
                {
                    counter = 0;
                    for (int d = 0; d < graph[i].Count; d++)
                    {
                        if (visvert[graph[i][d]] != true)
                        {
                            bic[globalcounter] += i;
                          //  Console.Write(i);

                            DFS(graph[i][d], i, bic[d]);
                            bic[counter] = bic[d];

                            counter++;
                            globalcounter++;
                        }
                        
                    }
                }
            }
        
            

        }

        public void DFS(int vertex,int root,string component)
           {
            visvert[vertex] = true;
            component += vertex;
           // Console.Write(vertex);
            for (int i = 0; i < graph[vertex].Count(); i++)
            {
                if (graph[vertex][i] == root)
                {
                    continue;
                }
                if (visvert[graph[vertex][i]]!= true) 
                {
                    for (int n = 0; n < ArticulationPoints.Count(); n++) 
                    {
                        if (ArticulationPoints[n] == true && n != root)
                        {
                            component += graph[vertex][i];
                         //   Console.Write(graph[vertex][i]);
                            visvert[graph[vertex][i]] = true;
                            return;

                        }
                    }
                    DFS(graph[vertex][i], root, component);
                }
            }
        }
        #endregion
        #region measuring amount of time that has passed
        public void doFullLoop(int startingVertex, int endingVertex) 
        {
            for (int i = startingVertex; i < endingVertex; i++) 
            {
                action(i);
            }
        }
        public void action(int verticesAmount)
        {
            var stopwatch = new Stopwatch(  );

            Graph g = new Graph();
            g.createRandomGraph(g.createRandomMatrix(verticesAmount, verticesAmount));
            stopwatch.Start();
            g.ArticulationPointsSolve();
            g.findBIcomponentsBad();
            Console.WriteLine(verticesAmount + " vertices in " + stopwatch.ElapsedTicks);
            stopwatch.Stop();
        }
        #endregion


       public void searchForArtPoints()
        {
            int initialComponents = this.searhchForConnectivityComponents(-1);

            for (int i = 0; i < graph.Count(); i++)
            {
                for (int k = 0; k < graph.Count(); k++) 
                {
                    visitedVerticesConComp[k] = false;

                }
                int currentComponent = this.searhchForConnectivityComponents(i);
                if (currentComponent > initialComponents) 
                {
                    Console.WriteLine("articulation points is"+ currentComponent);
                }
            }
        }
        public int searhchForConnectivityComponents(int verticeNotTogo)
        {
            int connectivityComponentsCounter = 0;

            for (int i = 0; i < graph.Count(); i++) 
            {
                if (visitedVerticesConComp[i] != true&&graph[i].Count!=0 && i!= verticeNotTogo) 
                {

                    DFSforConnComp(i,verticeNotTogo);
                    Console.WriteLine();
                    
                    connectivityComponentsCounter++;
                    Console.WriteLine("the amount of "+connectivityComponentsCounter);
                    return connectivityComponentsCounter;
                }
            }
            Console.WriteLine("the amount of " + connectivityComponentsCounter);
            return connectivityComponentsCounter;

        }
        public void DFSforConnComp(int vertex,int verticeNotToGO) 
        {
            visitedVerticesConComp[vertex] = true;

            for (int i = 0; i < graph[vertex].Count(); i++) 
            {
                if (!visitedVerticesConComp[graph[vertex][i]]&& graph[vertex][i]!= verticeNotToGO)
                { 
                    Console.Write(graph[vertex][i]);
                    DFSforConnComp(graph[vertex][i],verticeNotToGO);
                }

            }
        }

        





        public void biconnectedComponentsBridge()
        {
            for (int k = 0; k < visvert.Count(); k++) 
            {
                visvert[k] = false;

            }
            for (int i = 0; i < graph.Count(); i++) 
            {
                if (visvert[i] != true)
                {
                //    dfsForBicBridges(i);
                }
            }
        }
       public void dfsForBicBridges(int vertice) 
        {
            visvert[vertice] = true;


            for (int i = 0; i < graph[vertice].Count(); i++) 
            {
                if (vertice == bridgesFrom[i])
                {
                    for (int l = 0; l < graph[vertice].Count(); l++) 
                    {
                        if (visvert[graph[vertice][l]] != true && graph[vertice][l] != bridgesTo[i]) 
                        {
                            dfsForBicBridges(graph[vertice][l]);
                        }
                    }
              
                }
                if (!visvert[graph[vertice][i]]) 
                {
                    Console.Write(graph[vertice][i]);
                    dfsForBicBridges(graph[vertice][i]);
                }
            }
        }

        static void Main(string[] args)
        {
            Graph graph = new Graph();
           // graph.createRandomGraph(graph.createRandomMatrix(6,6));
            //graph.FindBridges();
           graph.doFullLoop(5,500);
            
        }
    }
}