Модернизация компьютерной сети предприятия с целью достижения заданной пропускной способности

Приложение  Г

ФГБОУ ВПО «Саратовский государственный университет

 имени Н.Г.  Чернышевского»

Колледж радиоэлектроники имени П.Н. Яблочкова

 

643.КРЭ.00001-01 12

 

 

Модернизация  компьютерной сети предприятия с  целью достижения заданной пропускной способности.

 

Текст программы.

 

643.КРЭ.00001-01 12

Листов 7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2012

Листинг программы

Работа программы  базируется на использовании двух основных классов: Dinic.cs и MaxFlowMinCost.cs.

Класс Dinic.cs предназначен для реализации алгоритма Диница, которым находится максимальный поток всей сети. Исходный код класса:

 

public class Dinic

    {

        class Edge

        {

            public int t, rev, cap, f;

 

            public Edge(int t, int rev, int cap)

            {

                this.t = t;

                this.rev = rev;

                this.cap = cap;

            }

        }

 

        private List<Edge>[] graph;

 

        public int maxFlow(int src, int dest)

        {

            int[] ptr = new int[graph.Length];

            int[] Q = new int[graph.Length];

            int[] dist = new int[graph.Length];

            int flow = 0;

            while (dinic_bfs(dist, Q, src, dest))

            {

                Fill<int>(ptr, 0);

                while (true)

                {

                    int df = dinic_dfs(ptr, dist, dest, src, int.MaxValue);

                    if (df == 0)

                        break;

                    flow += df;

                }

            }

            return flow;

        }

 

        public void addEdge(int s, int t, int cap)

        {

            graph[s].Add(new Edge(t, graph[t].Count, cap));

            graph[t].Add(new Edge(t, graph[s].Count - 1, 0));

        }

 

        private bool dinic_bfs(int[] dist, int[] Q, int src, int dest)

        {

            Fill<int>(dist, -1);

            dist[src] = 0;

            int sizeQ = 0;

            Q[sizeQ++] = src;

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

            {

                int u = Q[i];

                foreach (Edge e in graph[u])

                {

                    if (dist[e.t] < 0 && e.f < e.cap)

                    {

                        dist[e.t] = dist[u] + 1;

                        Q[sizeQ++] = e.t;

                    }

                }

            }

            return dist[dest] >= 0;

        }

 

        private int dinic_dfs(int[] ptr, int[] dist, int dest, int u, int f)

        {

            if (u == dest)

                return f;

            for (; ptr[u] < graph[u].Count; ++ptr[u])

            {

                Edge e = graph[u].ElementAt(ptr[u]);

                if (dist[e.t] == dist[u] + 1 && e.f < e.cap)

                {

                    int df = dinic_dfs(ptr, dist, dest, e.t, Math.Min(f,e.cap - e.f));

                    if (df > 0)

                    {

                        e.f += df;

                        graph[e.t].ElementAt(e.rev).f -= df;

                        return df;

                    }

                }

            }

            return 0;

        }

 

        private void Fill<T>(T[] array, T value)

        {

            if (array == null)

            {

                throw new ArgumentNullException("array");

            }

            for (int i = 0; i < array.Length; i++)

            {

                array[i] = value;

            }

        }

}

 

Вызываемый  метод для получения решения  – MaxFlow() в который в качестве аргументов передаются номера вершин (истока src и  стока dest). За хранение связей отвечает поле graph, в котором хранятся экземпляры локального класса Edge. Однако, доступность  поля помечена идентификатором private, и оно не может изменяться извне. Чтобы добавить ребро объекту класса Dinic.cs, нужно вызвать его метод addEdge() со следующими аргументами:

1. Число типа int, начало ребра
2. Число типа int, конец ребра
3. Число типа int, пропускная способность ребра.

 

 

Класс MaxFlowMinCost.cs предназначен для определения максимального  потока минимальной стоимости, который  рассчитывается тривиальным перебором. Исходный код класса:

 

    public static class MaxFlowMinCost

    {

        private static int findPath(int[,] cap, bool[] vis, int u, int t, int f)

        {

            if (u == t)

            {

                return f;

            }

            vis[u] = true;

            for (int v = 0; v < vis.Length; v++)

            {

                if (!vis[v] && cap[u,v] > 0)

                {

                    int df = findPath(cap, vis, v, t, Math.Min(f, cap[u,v]));

                    if (df > 0)

                    {

                        cap[u,v] -= df;

                        cap[v,u] += df;

                        return df;

                    }

                }

            }

            return 0;

        }

 

        public static int maxFlow(int[,] cap, int s, int t, int n)

        {

            for (int flow = 0; ; )

            {

                int df = findPath(cap, new bool[n], s, t, int.MaxValue);

                if (df == 0)

                {

                    return flow;

                }

                flow += df;

            }

        }

}

 

Здесь, чтобы получить величину максимального потока, необходимо вызвать  статичный метод maxFlow()  с аргументами:

Двумерный массив типа int, размером n строк и n столбцов – матрица  пропускных способностей.

1. Число типа int, исток.
2. Число типа int, сток.
3. Число типа int, количество вершин.