# Разработка абстрактного типа данных «Простой, статический граф», страница 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;

}

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

{

j = m_P[i, j];

}

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())

{

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;

}

}