Category Archives: C#

C#.Поиск длиннейших путей во взвешенном ациклическом орграфе

Posted on 16.08.2018 by Stanislav_Panteleev

Аналогичен поиску кратчайших путей за разницей знаков при релаксации ребра.

Posted in C# | Comments Off

С#. Топологическая сортировка во взвешенном орграфе

Posted on 16.08.2018 by Stanislav_Panteleev

Класс

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WOrGraph
{

    class Topological
    {
        private Boolean[] marked; // marked[v] = true if v is reachable from source(s)        
        public Queue<int> Pre { get; }
        public Queue<int> Post { get; }
        public Stack<int> ReversePost { get; }

        public Topological(EdgeWeightedDigraph G)
        {
            Pre = new Queue<int>();
            Post = new Queue<int>();
            ReversePost = new Stack<int>();
            marked = new bool[G.GetVertices()];
            for (int v = 0; v < G.GetVertices(); v++)
                if (!marked[v]) Dfs(G, v);
        }
        public bool IsOrder()
        {
            return (ReversePost.Count > 0);
        }
        private void Dfs(EdgeWeightedDigraph G, int v)
        {
            marked[v] = true;
            Pre.Enqueue(v);
            foreach (DirectedEdge e in G.GetAdj(v))            
            {
                int w = e.To();
                if (!marked[w]) Dfs(G, w);
            }
            Post.Enqueue(v);
            ReversePost.Push(v);
        }

        // --- validation
        private void ValidateVertex(int v)
        {
            int V = marked.Length;
            if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); }
        }

    }

}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace WOrGraph

{

class Topological

{

private Boolean[] marked; // marked[v] = true if v is reachable from source(s)

public Queue<int> Pre { get; }

public Queue<int> Post { get; }

public Stack<int> ReversePost { get; }

public Topological(EdgeWeightedDigraph G)

{

Pre = new Queue<int>();

Post = new Queue<int>();

ReversePost = new Stack<int>();

marked = new bool[G.GetVertices()];

for (int v = 0; v < G.GetVertices(); v++)

if (!marked[v]) Dfs(G, v);

}

public bool IsOrder()

{

return (ReversePost.Count > 0);

}

private void Dfs(EdgeWeightedDigraph G, int v)

{

marked[v] = true;

Pre.Enqueue(v);

foreach (DirectedEdge e in G.GetAdj(v))

{

int w = e.To();

if (!marked[w]) Dfs(G, w);

}

Post.Enqueue(v);

ReversePost.Push(v);

}

// --- validation

private void ValidateVertex(int v)

{

int V = marked.Length;

if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); }

}

Posted in C# | Comments Off

С#. Поиск кратчайших путей во взвешенном ациклическом орграфе

Posted on 16.08.2018 by Stanislav_Panteleev

Git

Posted in C# | Comments Off

С#. Поиск циклов во взвешенном орграфе

Posted on 16.08.2018 by Stanislav_Panteleev

Git Ранее уже был пример для поиска цикла в орграфе, теперь поиск цикла во взвешенном орграфе. Отличие здесь в том, что мы перебираем ребра и берем вершину To(). В остальном класс точно такой же. При обнаружении цикла, он заносится в … Continue reading →

Posted in C# | Comments Off

C#. Дейкстера. Кратчайшие пути для всех пар вершин в орграфе

Posted on 15.08.2018 by Stanislav_Panteleev

Класс DijkstraAllPairsSP

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WOrGraph
{
    class DijkstraAllPairsSP
    {
        private DijkstraSP[] all;
        public DijkstraAllPairsSP(EdgeWeightedDigraph G)
        {
            all = new DijkstraSP[G.GetVertices()];
            for (int v = 0; v < G.GetVertices(); v++)
                all[v] = new DijkstraSP(G, v);
        }
        public IEnumerable<DirectedEdge> GetPath(int s, int t)
        {
            ValidateVertex(s);
            ValidateVertex(t);
            return all[s].GetPathTo(t);
        }
        private void ValidateVertex(int v)
        {
            int V = all.Length;
            if (v < 0 || v >= V)
                throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
        public double Dist(int s, int t)
        {
            ValidateVertex(s);
            ValidateVertex(t);
            return all[s].GetDistTo(t);
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace WOrGraph

{

class DijkstraAllPairsSP

{

private DijkstraSP[] all;

public DijkstraAllPairsSP(EdgeWeightedDigraph G)

{

all = new DijkstraSP[G.GetVertices()];

for (int v = 0; v < G.GetVertices(); v++)

all[v] = new DijkstraSP(G, v);

}

public IEnumerable<DirectedEdge> GetPath(int s, int t)

{

ValidateVertex(s);

ValidateVertex(t);

return all[s].GetPathTo(t);

}

private void ValidateVertex(int v)

{

int V = all.Length;

if (v < 0 || v >= V)

throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

public double Dist(int s, int t)

{

ValidateVertex(s);

ValidateVertex(t);

return all[s].GetDistTo(t);

}

Posted in C# | Comments Off

С#. Дейкстера. Поиск кратчайших путей из вершины в орграфе

Posted on 15.08.2018 by Stanislav_Panteleev

Поиск кратчайших путей из одного источника для взвешенных графов с неотрицательными весами. ДКП – дерево кратчайших путей

Posted in C# | Comments Off

С#. Взвешенный орграф

Posted on 15.08.2018 by Stanislav_Panteleev

Git Класс EdgeWeightedDigraph

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WOrGraph
{
    class EdgeWeightedDigraph
    {
        private int V; // vertices
        private int E; // edges
        private List<DirectedEdge>[] adj;
        private int[] Indegree;
        private void ValidateVertex(int v)
        {
            if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
        public void AddEdge(DirectedEdge e)
        {
            int v = e.From();
            int w = e.To();
            ValidateVertex(v);
            ValidateVertex(w);
            adj[v].Add(e);
            Indegree[w]++;
            E++;
        }
        public IEnumerable<DirectedEdge> GetAdj(int v)
        {
            ValidateVertex(v);
            return adj[v];
        }
        public int GetOutDegree(int v)
        {
            ValidateVertex(v);
            return adj[v].Count;
        }
        public int GetIndegree(int v)
        {
            ValidateVertex(v);
            return Indegree[v];
        }
        // -- init Graph from file        
        public EdgeWeightedDigraph(string filepath)
        {
            try
            {
                if (!File.Exists(filepath)) { throw new Exception("no file with such filepath"); }
                using (StreamReader sr = new StreamReader(filepath))
                {
                    int i = 0;
                    while (sr.Peek() >= 0)
                    {
                        // reading number of verticles
                        if (i == 0)
                        {
                            V = Convert.ToInt32(sr.ReadLine());
                            adj = new List<DirectedEdge>[V];
                            Indegree = new int[V];
                            for (int v = 0; v < V; v++)
                            {
                                adj[v] = new List<DirectedEdge>();
                            }
                            i++;
                        }
                        // reading number of edges
                        else
                            if (i == 1)
                        {
                            E = Convert.ToInt32(sr.ReadLine());
                            if (E < 0) throw new ArgumentException("number of edges in a Graph must be nonnegative");
                            i++;
                        }
                        else
                        {
                            string s = sr.ReadLine();
                            Char delimiter = ' ';
                            String[] substrings = s.Split(delimiter);
                            int v = Convert.ToInt32(substrings[0]);
                            int w = Convert.ToInt32(substrings[1]);
                            double weight = Convert.ToDouble(substrings[2]);
                            ValidateVertex(v);
                            ValidateVertex(w);
                            DirectedEdge e = new DirectedEdge(v, w, weight);
                            AddEdge(e);
                        }

                    }
                }
            }
            catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); };
        }
        public override string ToString()
        {            
            StringBuilder s = new StringBuilder();
            s.Append("Verticles: " + V + " " + "Edges: " + E / 2 + "\n"); // E%2 because each edge twice in verticle
            for (int v = 0; v < V; v++)
            {
                //s.Append(v + ": ");
                foreach (DirectedEdge e in adj[v])
                {
                    s.Append(e.From() +" -> "+e.To()+"  ");
                }
                s.Append("\n");
            }
            return s.ToString();
        }

    }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace WOrGraph

{

class EdgeWeightedDigraph

{

private int V; // vertices

private int E; // edges

private List<DirectedEdge>[] adj;

private int[] Indegree;

private void ValidateVertex(int v)

{

if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));

}

public void AddEdge(DirectedEdge e)

{

int v = e.From();

int w = e.To();

ValidateVertex(v);

ValidateVertex(w);

adj[v].Add(e);

Indegree[w]++;

E++;

}

public IEnumerable<DirectedEdge> GetAdj(int v)

{

ValidateVertex(v);

return adj[v];

}

public int GetOutDegree(int v)

{

ValidateVertex(v);

return adj[v].Count;

}

public int GetIndegree(int v)

{

ValidateVertex(v);

return Indegree[v];

}

// -- init Graph from file

public EdgeWeightedDigraph(string filepath)

{

try

{

if (!File.Exists(filepath)) { throw new Exception("no file with such filepath"); }

using (StreamReader sr = new StreamReader(filepath))

{

int i = 0;

while (sr.Peek() >= 0)

{

// reading number of verticles

if (i == 0)

{

V = Convert.ToInt32(sr.ReadLine());

adj = new List<DirectedEdge>[V];

Indegree = new int[V];

for (int v = 0; v < V; v++)

{

adj[v] = new List<DirectedEdge>();

}

i++;

}

// reading number of edges

else

if (i == 1)

{

E = Convert.ToInt32(sr.ReadLine());

if (E < 0) throw new ArgumentException("number of edges in a Graph must be nonnegative");

i++;

}

else

{

string s = sr.ReadLine();

Char delimiter = ' ';

String[] substrings = s.Split(delimiter);

int v = Convert.ToInt32(substrings[0]);

int w = Convert.ToInt32(substrings[1]);

double weight = Convert.ToDouble(substrings[2]);

ValidateVertex(v);

ValidateVertex(w);

DirectedEdge e = new DirectedEdge(v, w, weight);

AddEdge(e);

}

catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); };

}

public override string ToString()

{

StringBuilder s = new StringBuilder();

s.Append("Verticles: " + V + " " + "Edges: " + E / 2 + "\n"); // E%2 because each edge twice in verticle

for (int v = 0; v < V; v++)

{

//s.Append(v + ": ");

foreach (DirectedEdge e in adj[v])

{

s.Append(e.From() +" -> "+e.To()+" ");

}

s.Append("\n");

}

return s.ToString();

}

Posted in C# | Comments Off

C#. Алгоритм Прима. Энергичный вариант.

Posted on 13.08.2018 by Stanislav_Panteleev

Git Энергичный вариант алгоритма Прима отличается тем, что мы сразу же отсеиваем ребра, которые образуют цикл в минимальном остовном дереве.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WGraph
{
    class PrimMST
    {
        private static double FLOATING_POINT_EPSILON = 1E-12;
        private Edge[] edgeTo; // edgeTo[v] = shortest edge from tree vertex to non-tree vertex
        private double[] distTo;  // distTo[v] = weight of shortest such edge
        private bool[] marked;  // marked[v] = true if v on tree, false otherwise
        private IndexMinPQ<Double> pq;

        public PrimMST(EdgeWeightedGraph G)
        {
            edgeTo = new Edge[G.GetVertices()];
            distTo = new double[G.GetVertices()];
            marked = new bool[G.GetVertices()];
            Comparer<double> comparer = Comparer<double>.Default;
            pq = new IndexMinPQ<double>(G.GetVertices(), comparer);
            for (int v = 0; v < G.GetVertices(); v++)
                distTo[v] = Double.PositiveInfinity;
        }
        // run Prim's algorithm in graph G, starting from vertex s
        private void Prim(EdgeWeightedGraph G, int s)
        {
            distTo[s] = 0.0;
            pq.Insert(s, distTo[s]);
            while (!pq.IsEmpty())
            {
                pq.DelMin(out int v, out double dist);
                Scan(G, v);
            }
        }

        private void Scan(EdgeWeightedGraph G, int v)
        {
            marked[v] = true;
            foreach (Edge e in G.GetAdj(v))
            {
                int w = e.Other(v);
                if (marked[w]) continue;
                if (e.GetWeight() < distTo[w])
                {
                    distTo[w] = e.GetWeight();
                    edgeTo[w] = e;
                    if (pq.Contains(w)) pq.DecreaseKey(w, distTo[w]);
                    else pq.Insert(w, distTo[w]);
                }
            }
        }
        /**
         * Returns the edges in a minimum spanning tree (or forest).
         * @return the edges in a minimum spanning tree (or forest) as
         *    an iterable of edges
         */
        public IEnumerable<Edge> GetEdges()
        {
            Queue<Edge> mst = new Queue<Edge>();
            for (int v = 0; v < edgeTo.Length; v++)
            {
                Edge e = edgeTo[v];
                if (e != null)
                {
                    mst.Enqueue(e);
                }
            }
            return mst;
        }
        /**
         * Returns the sum of the edge weights in a minimum spanning tree (or forest).
         * @return the sum of the edge weights in a minimum spanning tree (or forest)
         */
        public double GetWeight()
        {
            double weight = 0.0;
            foreach (Edge e in GetEdges())
            {
                weight += e.GetWeight();
            }                           
            return weight;
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace WGraph

{

class PrimMST

{

private static double FLOATING_POINT_EPSILON = 1E-12;

private Edge[] edgeTo; // edgeTo[v] = shortest edge from tree vertex to non-tree vertex

private double[] distTo; // distTo[v] = weight of shortest such edge

private bool[] marked; // marked[v] = true if v on tree, false otherwise

private IndexMinPQ<Double> pq;

public PrimMST(EdgeWeightedGraph G)

{

edgeTo = new Edge[G.GetVertices()];

distTo = new double[G.GetVertices()];

marked = new bool[G.GetVertices()];

Comparer<double> comparer = Comparer<double>.Default;

pq = new IndexMinPQ<double>(G.GetVertices(), comparer);

for (int v = 0; v < G.GetVertices(); v++)

distTo[v] = Double.PositiveInfinity;

}

// run Prim's algorithm in graph G, starting from vertex s

private void Prim(EdgeWeightedGraph G, int s)

{

distTo[s] = 0.0;

pq.Insert(s, distTo[s]);

while (!pq.IsEmpty())

{

pq.DelMin(out int v, out double dist);

Scan(G, v);

}

private void Scan(EdgeWeightedGraph G, int v)

{

marked[v] = true;

foreach (Edge e in G.GetAdj(v))

{

int w = e.Other(v);

if (marked[w]) continue;

if (e.GetWeight() < distTo[w])

{

distTo[w] = e.GetWeight();

edgeTo[w] = e;

if (pq.Contains(w)) pq.DecreaseKey(w, distTo[w]);

else pq.Insert(w, distTo[w]);

}

/**

* Returns the edges in a minimum spanning tree (or forest).

* @return the edges in a minimum spanning tree (or forest) as

* an iterable of edges

public IEnumerable<Edge> GetEdges()

{

Queue<Edge> mst = new Queue<Edge>();

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

{

Edge e = edgeTo[v];

if (e != null)

{

mst.Enqueue(e);

}

return mst;

}

/**

* Returns the sum of the edge weights in a minimum spanning tree (or forest).

* @return the sum of the edge weights in a minimum spanning tree (or forest)

public double GetWeight()

{

double weight = 0.0;

foreach (Edge e in GetEdges())

{

weight += e.GetWeight();

}

return weight;

}

Тестовый клиент

Posted in C# | Comments Off

С#. Алгоритм Прима (lazy вариант)

Posted on 13.08.2018 by Stanislav_Panteleev

Git Своими словами. Обходятся все вершины. Для каждой вершины выбираются инцидентные ребра. Просматриваются противоположные вершины инцидентных ребер и добавляются в очередь. Просматривается очередь и выбирается ребро с наименьшим весом. Оно добавляется в финальную очередь. Также должна быть проверка на то, … Continue reading →

Posted in C# | Comments Off

C#. IEnumerable. Пример реализации

Posted on 10.08.2018 by Stanislav_Panteleev

Делал индексную очередь с приоритетами, понадобилось реализовывать интерфейс IEnumerable. Получилось так

class IndexMaxPQ<Key> : IEnumerable<Key>
{

}

class IndexMaxPQ<Key> : IEnumerable<Key>

{

}

Понадобилось реализовать 2 следующих метода

public IEnumerator<Key> GetEnumerator()
        {
            return new HeapIterator<Key>(comparer, Size(), n, keys);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

public IEnumerator<Key> GetEnumerator()

{

return new HeapIterator<Key>(comparer, Size(), n, keys);

}

IEnumerator IEnumerable.GetEnumerator()

{

return GetEnumerator();

}

В контексте логики класса был написан другой класс HeapIterator

Posted in C# | Comments Off

Category Archives: C#

C#.Поиск длиннейших путей во взвешенном ациклическом орграфе

С#. Топологическая сортировка во взвешенном орграфе

С#. Поиск кратчайших путей во взвешенном ациклическом орграфе

С#. Поиск циклов во взвешенном орграфе

C#. Дейкстера. Кратчайшие пути для всех пар вершин в орграфе

С#. Дейкстера. Поиск кратчайших путей из вершины в орграфе

С#. Взвешенный орграф

C#. Алгоритм Прима. Энергичный вариант.

С#. Алгоритм Прима (lazy вариант)

C#. IEnumerable. Пример реализации

MY PROJECTS

Recent Posts

Categories