Разработка абстрактного типа данных «Простой, статический граф», страница 16

                }

            }

        }

        public void Set(Graph<TypeWeight, TypeData> graf, int outVertex, int inVertex)

        {

            m_graf = graf;

            m_outVertex = outVertex;

            m_inVertex = inVertex;

            if (m_graf.IsVertex(m_outVertex) && m_graf.IsVertex(m_inVertex))

            {

                CalculateNumbersVertex();

                Calculate_W_and_P();

                CalculateSource();

            }

        }

        public void Restart(int outVertex, int inVertex)

        {

            m_outVertex = outVertex;

            m_inVertex = inVertex;

            if (m_graf.IsVertex(m_outVertex) && m_graf.IsVertex(m_inVertex))

            {

                CalculateNumbersVertex();

                Calculate_W_and_P();

                CalculateSource();

            }

        }

        public List<int> Result()

        {

            List<int> result = new List<int>();

            if (m_graf.IsVertex(m_outVertex) && m_graf.IsVertex(m_inVertex))

            {

                int begin = index(m_outVertex);

                int i = index(m_outVertex);

                int j = index(m_inVertex);

                if (m_P[i, j] == begin && !m_graf.IsEdge(m_outVertex, m_inVertex))

                {

                    return result;

                }

                result.Add(m_inVertex);

                while (m_P[i, j] != begin)

                {

                    result.Add(m_numbersVertex[m_P[i, j]]);

                    j = m_P[i, j];

                }

                result.Add(m_outVertex);

                result.Reverse();

                return result;

            }

            return result;    

        }

        private void CalculateSource()

        {

            int n = m_graf.GetCountVertex();

            for (int k = 0; k < n; k++)

            {

                for (int i = 0; i < n; i++)

                {

                    for (int j = 0; j < n; j++)

                    {

                        if (m_D[i, j] > m_D[i, k] + m_D[k, j] && m_D[i, k] < int.MaxValue && m_D[k, j] < int.MaxValue)

                        {

                            m_D[i, j] = m_D[i, k] + m_D[k, j];

                            m_P[i, j] = m_P[k, j];

                        }

                    }

                }

            }

        }

        private void Calculate_W_and_P()

        {

            int n = m_graf.GetCountVertex();

            m_D = new int[n, n];

            m_P = new int[n, n];

            for (int i = 0; i < n; i++)

            {

                for (int j = 0; j < n; j++)

                {

                    if (i != j)

                    {

                        m_D[i, j] = int.MaxValue;

                    }

                    m_P[i, j] = i;

                }

            }

            Graph<TypeWeight, TypeData>.IteratorEdge iterEdge = new Graph<TypeWeight, TypeData>.IteratorEdge(m_graf);

            iterEdge.Begin();

            while (!iterEdge.IsEnd())

            {

                m_D[index(iterEdge.Edge().VertexOut), index(iterEdge.Edge().VertexIn)] = 1;

                iterEdge.Next();

            }

        }

        private void CalculateNumbersVertex()

        {

            m_numbersVertex.Clear();

            Graph<TypeWeight, TypeData>.IteratorVertex iterVert = new Graph<TypeWeight, TypeData>.IteratorVertex(m_graf);

            iterVert.Begin();

            while (!iterVert.IsEnd())

            {

                m_numbersVertex.Add(iterVert.Number());

                iterVert.Next();

            }

        }

        private int index(int number)

        {

            for (int i = 0; i < m_numbersVertex.Count; i++)

            {

                if (m_numbersVertex[i] == number)

                {

                    return i;

                }

            }

            return -1;

        }

    }