Category Archives: C#

C#. Поиск путей в орграфах методом DepthFirstSearch

Posted on 26.07.2018 by Stanislav_Panteleev

Git Возьмем за основу алгоритм DFS для орграфов. И напишем поиск путей из одной вершины в другую. Конечный вариант будет выглядеть примерно так…

// Has path to ?            
            Console.WriteLine("Has path from 0 to 11 vertex? " + d.HasPathToDFS(d, 0, 11));
            // This is the path ?            
            Console.WriteLine("This is the path...?");
            Stack<int> path = new Stack<int>();
            d.GetPathToDFS(d, 0, 11, ref path);
            if (path.Count != 0)
            {
                foreach (int i in path)
                    Console.WriteLine(" > " + i.ToString());
            }
            else
                Console.WriteLine("no path...");

// Has path to ?

Console.WriteLine("Has path from 0 to 11 vertex? " + d.HasPathToDFS(d, 0, 11));

// This is the path ?

Console.WriteLine("This is the path...?");

Stack<int> path = new Stack<int>();

d.GetPathToDFS(d, 0, 11, ref path);

if (path.Count != 0)

{

foreach (int i in path)

Console.WriteLine(" > " + i.ToString());

}

else

Console.WriteLine("no path...");

Напишем небольшой класс для поиска путей, он будет выглядеть примерно так…

Posted in C# | Comments Off

С#. Достижимость в орграфах

Posted on 25.07.2018 by Stanislav_Panteleev

Git Существует ли ориентированный путь из s в указанную вершину v в орграфе? Для этого будем использовать поиск в глубину и напишем класс DirectedDFS. Для примера будем использовать граф tinyDG.txt

4 2

2 3

3 2

6 0

0 1

2 0

11 12

12 9

9 10

9 11

8 9

10 12

11 4

4 3

3 5

7 8

8 7

5 4

0 5

6 4

6 9

7 6

Posted in C# | Comments Off

C#. Digraph. Класс орграфа с примером чтения из файла

Posted on 25.07.2018 by Stanislav_Panteleev

Git Класс орграфа. В качестве списков смежности вершин используется самописный Bag on Linked List Пример применения и тест некоторых методов

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

namespace Digraph
{
    class Program
    {
        static void Main(string[] args)
        {
            Digraph d = new Digraph("tinyDG.txt");
            //how much vertices?
            Console.WriteLine("Vertices: "+ d.GetVertices());
            Console.WriteLine("Edges: " + d.GetEdges());
            Console.WriteLine("InDegree for 0 vertice: " + d.GetInDegree(0));
            Console.WriteLine("OutDegree for 0 vertice: " + d.GetOutDegree(0));
            Console.WriteLine("ToString(): " + d.ToString());
            Console.ReadLine();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Digraph

{

class Program

{

static void Main(string[] args)

{

Digraph d = new Digraph("tinyDG.txt");

//how much vertices?

Console.WriteLine("Vertices: "+ d.GetVertices());

Console.WriteLine("Edges: " + d.GetEdges());

Console.WriteLine("InDegree for 0 vertice: " + d.GetInDegree(0));

Console.WriteLine("OutDegree for 0 vertice: " + d.GetOutDegree(0));

Console.WriteLine("ToString(): " + d.ToString());

Console.ReadLine();

}

Posted in C# | Comments Off

C#. Орграфы. Теория.

Posted on 25.07.2018 by Stanislav_Panteleev

Теория графов, университет ИТМО Орграф – множество вершин и коллекция ориентированных ребер. Полустепень исхода Полустепень входа Ориентированный путь орграфа – последовательность вершин, в которой существует ориентированное ребро, указывающее из каждой вершины на след. вершину этой последовательности. Ориентированный цикл – ориентированный … Continue reading →

Posted in C# | Comments Off

C#. Aлгоритмы и структуры данных. Фиксированный стэк

Posted on 21.07.2018 by Stanislav_Panteleev

Класс стэка. Все максимально просто. Git

namespace _02_FixedStack
{
    class FixedStack<T>
    {
        private T[] Items; 
        public int Count { get; set; }
        public FixedStack(int aCount)
        {
            Items = new T[aCount];
            Count = 0;
        }
        public bool IsEmpty() { return Count == 0; }
        public void Push(T item)
        {
            Items[Count++] = item;
        }
        public T Pop()
        {
            return Items[--Count];
        }
    }
}

namespace _02_FixedStack

{

class FixedStack<T>

{

private T[] Items;

public int Count { get; set; }

public FixedStack(int aCount)

{

Items = new T[aCount];

Count = 0;

}

public bool IsEmpty() { return Count == 0; }

public void Push(T item)

{

Items[Count++] = item;

}

public T Pop()

{

return Items[--Count];

}

Пример использования

namespace _02_FixedStack
{
    class Program
    {
        static void Main(string[] args)
        {
            FixedStack<int> f = new FixedStack<int>(4);
            f.Push(1);
            f.Push(2);
            f.Push(3);
            //
            Console.WriteLine("Count is..." + f.Count);
            while (f.Count != 0)
            {
                Console.WriteLine(f.Pop().ToString());
            }
            Console.WriteLine("Count is..." + f.Count);
            Console.ReadLine();
        }
    }
}

namespace _02_FixedStack

{

class Program

{

static void Main(string[] args)

{

FixedStack<int> f = new FixedStack<int>(4);

f.Push(1);

f.Push(2);

f.Push(3);

Console.WriteLine("Count is..." + f.Count);

while (f.Count != 0)

{

Console.WriteLine(f.Pop().ToString());

}

Console.WriteLine("Count is..." + f.Count);

Console.ReadLine();

}

Posted in C# | Comments Off

Starting new life period…

Posted on 21.07.2018 by Stanislav_Panteleev

Posted in C# | Comments Off

C# Делегаты и события

Posted on 03.07.2018 by Stanislav_Panteleev

Понравилось видео

Posted in C# | Comments Off

C#. Undirected Graph Basics Altogether

Posted on 16.01.2018 by Stanislav_Panteleev

Git Graph

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

namespace GraphBasics
{
    public class Graph
    {
        public int V { get; set; }
        public int E { get; set; }
        public Bag<int>[] adj;
        public Graph(int V) // init empty graph with V verticles
        {
            if (V < 0)
            {
                throw new ArgumentException();
            }

            this.V = V;
            this.E = 0;
            adj = new Bag<int>[V];
            for (int v = 0; v <= V; v++)
            {
                adj[v] = new Bag<int>();
            }
        }
        public Graph(string aFilePath) // init graph from filePath
        {
       
            if (!File.Exists(aFilePath)) throw new Exception("file not exists");
            string[] ReadText = File.ReadAllLines(aFilePath);
            this.V = Convert.ToInt32(ReadText[0]);
            this.E = 0; //Convert.ToInt32(ReadText[1]);
            // init adj obj
            adj = new Bag<int>[V];
            for (int v = 0; v < V; v++)
            {
                adj[v] = new Bag<int>();
            }
            for (var i = 2; i < ReadText.Length; i++)
            {
                string[] splitted;
                splitted = ReadText[i].Split(' ');
                //if (splitted.Count<string> = 2)
                {
                    int v = Convert.ToInt32(splitted[0]);
                    int w = Convert.ToInt32(splitted[1]);
                    this.AddEdge(v, w);
                }

            }
        }
        // vertices and edges
        public int Vertices() { return V; }
        public int Edges() { return E; }
        public void ValidateVertex(int v)
        {
            if (v < 0 || v > V) { throw new ArgumentException(); }
        }
        // adding undirected edge to the graph
        public void AddEdge(int v, int w)
        {
            ValidateVertex(v);
            ValidateVertex(w);
            E++;
            adj[v].Push(w);
            adj[w].Push(v);
        }
        //returns vertices adjacent to vertex
        public Bag<int> AdjacentVerticles(int v)
        {
            ValidateVertex(v);
            return adj[v];
        }
        // returns degree of vertex
        public int Degree(int v)
        {
            ValidateVertex(v);
            return adj[v].Size();
        }
        // returns string representation of Graph
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append(V + " vertices, " + E + " edges " + "\n");
            for (var v = 0; v < V; v++)
            {
                sb.Append(v + ":");
                foreach (int w in adj[v])
                {
                    sb.Append(w + " ");
                }
                sb.AppendLine();
            }
            return sb.ToString();
        }
    }
}

100

101

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace GraphBasics

{

public class Graph

{

public int V { get; set; }

public int E { get; set; }

public Bag<int>[] adj;

public Graph(int V) // init empty graph with V verticles

{

if (V < 0)

{

throw new ArgumentException();

}

this.V = V;

this.E = 0;

adj = new Bag<int>[V];

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

{

adj[v] = new Bag<int>();

}

public Graph(string aFilePath) // init graph from filePath

{

if (!File.Exists(aFilePath)) throw new Exception("file not exists");

string[] ReadText = File.ReadAllLines(aFilePath);

this.V = Convert.ToInt32(ReadText[0]);

this.E = 0; //Convert.ToInt32(ReadText[1]);

// init adj obj

adj = new Bag<int>[V];

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

{

adj[v] = new Bag<int>();

}

for (var i = 2; i < ReadText.Length; i++)

{

string[] splitted;

splitted = ReadText[i].Split(' ');

//if (splitted.Count<string> = 2)

{

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

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

this.AddEdge(v, w);

}

// vertices and edges

public int Vertices() { return V; }

public int Edges() { return E; }

public void ValidateVertex(int v)

{

if (v < 0 || v > V) { throw new ArgumentException(); }

}

// adding undirected edge to the graph

public void AddEdge(int v, int w)

{

ValidateVertex(v);

ValidateVertex(w);

E++;

adj[v].Push(w);

adj[w].Push(v);

}

//returns vertices adjacent to vertex

public Bag<int> AdjacentVerticles(int v)

{

ValidateVertex(v);

return adj[v];

}

// returns degree of vertex

public int Degree(int v)

{

ValidateVertex(v);

return adj[v].Size();

}

// returns string representation of Graph

public override string ToString()

{

StringBuilder sb = new StringBuilder();

sb.Append(V + " vertices, " + E + " edges " + "\n");

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

{

sb.Append(v + ":");

foreach (int w in adj[v])

{

sb.Append(w + " ");

}

sb.AppendLine();

}

return sb.ToString();

}

Posted in C# | Comments Off

C#. BipartiteGraph

Posted on 03.10.2017 by Stanislav_Panteleev

Seidgwicksource Git Bipartite.cs

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

namespace BipartiteGraphExample
{
    public class Bipartite
    {
        public bool isBipartite { get; set; }   // is the graph bipartite?
        private bool[] color;       // color[v] gives vertices on one side of bipartition
        private bool[] marked;      // marked[v] = true if v has been visited in DFS
        private int[] edgeTo;          // edgeTo[v] = last edge on path to v
        public Stack<int> cycle;  // odd-length cycle

        /**
   * Determines whether an undirected graph is bipartite and finds either a
   * bipartition or an odd-length cycle.
   *
   * @param  G the graph
   */
        public Bipartite(Graph G)
        {
            isBipartite = true;
            color = new bool [G.V];
            marked = new bool [G.V];
            edgeTo = new int[G.V];

            for (int v = 0; v < G.V; v++)
            {
                if (!marked[v])
                {
                    dfs(G, v);
                }
            }
            Trace.Assert(check(G));
        }

        private void dfs(Graph G, int v)
        {
            marked[v] = true;
            foreach (int w in G.adjVerticles(v))
            {

                // short circuit if odd-length cycle found
                if (cycle != null) return;

                // found uncolored vertex, so recur
                if (!marked[w])
                {
                    edgeTo[w] = v;
                    color[w] = !color[v];
                    dfs(G, w);
                }

                // if v-w create an odd-length cycle, find it
                else if (color[w] == color[v])
                {
                    isBipartite = false;
                    cycle = new Stack<int>();
                    cycle.Push(w);  // don't need this unless you want to include start vertex twice
                    for (int x = v; x != w; x = edgeTo[x])
                    {
                        cycle.Push(x);
                    }
                    cycle.Push(w);
                }
            }
        }
        public bool getColor(int v)
        {
            validateVertex(v);
            if (!isBipartite)
                throw new ArgumentException("graph is not bipartite");
            return color[v];
        }
        /**
   * Returns an odd-length cycle if the graph is not bipartite, and
   * {@code null} otherwise.
   *
   * @return an odd-length cycle if the graph is not bipartite
   *         (and hence has an odd-length cycle), and {@code null}
   *         otherwise
   */
        public IEnumerable<int> oddCycle()
        {
            return cycle;
        }

        private bool check(Graph G)
        {
            // graph is bipartite
            if (isBipartite)
            {
                for (int v = 0; v < G.V; v++)
                {
                    foreach (int w in G.adjVerticles(v))
                    {
                        if (color[v] == color[w])
                        {
                            Console.WriteLine("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                            return false;
                        }
                    }
                }
            }
            // graph has an odd-length cycle
            else
            {
                // verify cycle
                int first = -1, last = -1;
                foreach (int v in oddCycle())
                {
                    if (first == -1) first = v;
                    last = v;
                }
                if (first != last)
                {
                    Console.WriteLine("cycle begins with %d and ends with %d\n", first, last);
                    return false;
                }
            }

            return true;
        }
        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        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));
        }
        public void showCycle()
        {
            foreach (var c in cycle) Console.WriteLine(c);
        }

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BipartiteGraphExample

{

public class Bipartite

{

public bool isBipartite { get; set; } // is the graph bipartite?

private bool[] color; // color[v] gives vertices on one side of bipartition

private bool[] marked; // marked[v] = true if v has been visited in DFS

private int[] edgeTo; // edgeTo[v] = last edge on path to v

public Stack<int> cycle; // odd-length cycle

/**

* Determines whether an undirected graph is bipartite and finds either a

* bipartition or an odd-length cycle.

* @param G the graph

public Bipartite(Graph G)

{

isBipartite = true;

color = new bool [G.V];

marked = new bool [G.V];

edgeTo = new int[G.V];

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

{

if (!marked[v])

{

dfs(G, v);

}

Trace.Assert(check(G));

}

private void dfs(Graph G, int v)

{

marked[v] = true;

foreach (int w in G.adjVerticles(v))

{

// short circuit if odd-length cycle found

if (cycle != null) return;

// found uncolored vertex, so recur

if (!marked[w])

{

edgeTo[w] = v;

color[w] = !color[v];

dfs(G, w);

}

// if v-w create an odd-length cycle, find it

else if (color[w] == color[v])

{

isBipartite = false;

cycle = new Stack<int>();

cycle.Push(w); // don't need this unless you want to include start vertex twice

for (int x = v; x != w; x = edgeTo[x])

{

cycle.Push(x);

}

cycle.Push(w);

}

public bool getColor(int v)

{

validateVertex(v);

if (!isBipartite)

throw new ArgumentException("graph is not bipartite");

return color[v];

}

/**

* Returns an odd-length cycle if the graph is not bipartite, and

* {@code null} otherwise.

* @return an odd-length cycle if the graph is not bipartite

* (and hence has an odd-length cycle), and {@code null}

* otherwise

public IEnumerable<int> oddCycle()

{

return cycle;

}

private bool check(Graph G)

{

// graph is bipartite

if (isBipartite)

{

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

{

foreach (int w in G.adjVerticles(v))

{

if (color[v] == color[w])

{

Console.WriteLine("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);

return false;

}

// graph has an odd-length cycle

else

{

// verify cycle

int first = -1, last = -1;

foreach (int v in oddCycle())

{

if (first == -1) first = v;

last = v;

}

if (first != last)

{

Console.WriteLine("cycle begins with %d and ends with %d\n", first, last);

return false;

}

return true;

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

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

}

public void showCycle()

{

foreach (var c in cycle) Console.WriteLine(c);

}

Graph.cs

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

namespace BipartiteGraphExample
{
    public class Graph
    {
        // private static final String NEWLINE = System.getProperty("line.separator");

        public int V { get; set; }
        public int E { get; set; }
        public Bag<int>[] adj { get; set; }


        /**
         * Initializes an empty graph with {@code V} vertices and 0 edges.
         * param V the number of vertices
         *
         * @param  V number of vertices
         * @throws IllegalArgumentException if {@code V < 0}
         */
        public Graph(int V)
        {
            if (V < 0) throw new ArgumentException("Number of vertices must be nonnegative");
            this.V = V;
            this.E = 0;
            adj = new Bag<int>[V];
            for (int v = 0; v < V; v++)
            {
                adj[v] = new Bag<int>();
            }
        }


        /**  
   * Initializes a graph from the specified input stream.
   * The format is the number of vertices <em>V</em>,
   * followed by the number of edges <em>E</em>,
   * followed by <em>E</em> pairs of vertices, with each entry separated by whitespace.
   *
   * @param  in the input stream
   * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range
   * @throws IllegalArgumentException if the number of vertices or edges is negative
   * @throws IllegalArgumentException if the input stream is in the wrong format
   */

        public Graph(string filepath)
        {
            try
            {
                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 Bag<int>[V];
                            for (int v = 0; v < V; v++)
                            {
                                adj[v] = new Bag<int>();
                            }
                            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
                        {
                            //  for (int j = 0; j < E; j++)
                            //   {
                            string s = sr.ReadLine();
                            Char delimiter = ' ';
                            String[] substrings = s.Split(delimiter);
                            int v = Convert.ToInt32(substrings[0]);
                            int w = Convert.ToInt32(substrings[1]);
                            validateVertex(v);
                            validateVertex(w);
                            addEdge(v, w);
                        }

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



        }
        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        public void validateVertex(int v)
        {
            if (v < 0 || v >= V)
                throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
        /**
 * Adds the undirected edge v-w to this graph.
 *
 * @param  v one vertex in the edge
 * @param  w the other vertex in the edge
 * @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
 */
        public void addEdge(int v, int w)
        {
            validateVertex(v);
            validateVertex(w);
            E++;
            adj[v].push(w);
            adj[w].push(v);
        }
        /**
   * Returns the vertices adjacent to vertex {@code v}.
   *
   * @param  v the vertex
   * @return the vertices adjacent to vertex {@code v}, as an iterable
   * @throws IllegalArgumentException unless {@code 0 <= v < V}
   */
        public IEnumerable<int> adjVerticles(int v)
        {
            validateVertex(v);
            return adj[v];
        }
        /**
   * Returns the degree of vertex {@code v}.
   *
   * @param  v the vertex
   * @return the degree of vertex {@code v}
   * @throws IllegalArgumentException unless {@code 0 <= v < V}
   */
        public int degree(int v)
        {
            validateVertex(v);
            return adj[v].size();
        }
        /**
 * Returns a string representation of this graph.
 *
 * @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>,
 *         followed by the <em>V</em> adjacency lists
 */
        public String toString()
        {
            StringBuilder s = new StringBuilder();
            s.Append(V + " vertices, " + E + " edges " + "\n");
            for (int v = 0; v < V; v++)
            {
                s.Append(v + ": ");
                foreach (int w in adj[v])
                {
                    s.Append(w + " ");
                }
                s.Append("\n");
            }
            return s.ToString();
        }

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BipartiteGraphExample

{

public class Graph

{

// private static final String NEWLINE = System.getProperty("line.separator");

public int V { get; set; }

public int E { get; set; }

public Bag<int>[] adj { get; set; }

/**

* Initializes an empty graph with {@code V} vertices and 0 edges.

* param V the number of vertices

* @param V number of vertices

* @throws IllegalArgumentException if {@code V < 0}

public Graph(int V)

{

if (V < 0) throw new ArgumentException("Number of vertices must be nonnegative");

this.V = V;

this.E = 0;

adj = new Bag<int>[V];

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

{

adj[v] = new Bag<int>();

}

/**

* Initializes a graph from the specified input stream.

* The format is the number of vertices V,

* followed by the number of edges E,

* followed by E pairs of vertices, with each entry separated by whitespace.

* @param in the input stream

* @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range

* @throws IllegalArgumentException if the number of vertices or edges is negative

* @throws IllegalArgumentException if the input stream is in the wrong format

public Graph(string filepath)

{

try

{

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 Bag<int>[V];

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

{

adj[v] = new Bag<int>();

}

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

{

// for (int j = 0; j < E; j++)

// {

string s = sr.ReadLine();

Char delimiter = ' ';

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

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

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

validateVertex(v);

validateVertex(w);

addEdge(v, w);

}

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

}

// throw an IllegalArgumentException unless {@code 0 <= v < V}

public void validateVertex(int v)

{

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

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

}

/**

* Adds the undirected edge v-w to this graph.

* @param v one vertex in the edge

* @param w the other vertex in the edge

* @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V}

public void addEdge(int v, int w)

{

validateVertex(v);

validateVertex(w);

E++;

adj[v].push(w);

adj[w].push(v);

}

/**

* Returns the vertices adjacent to vertex {@code v}.

* @param v the vertex

* @return the vertices adjacent to vertex {@code v}, as an iterable

* @throws IllegalArgumentException unless {@code 0 <= v < V}

public IEnumerable<int> adjVerticles(int v)

{

validateVertex(v);

return adj[v];

}

/**

* Returns the degree of vertex {@code v}.

* @param v the vertex

* @return the degree of vertex {@code v}

* @throws IllegalArgumentException unless {@code 0 <= v < V}

public int degree(int v)

{

validateVertex(v);

return adj[v].size();

}

/**

* Returns a string representation of this graph.

* @return the number of vertices V, followed by the number of edges E,

* followed by the V adjacency lists

public String toString()

{

StringBuilder s = new StringBuilder();

s.Append(V + " vertices, " + E + " edges " + "\n");

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

{

s.Append(v + ": ");

foreach (int w in adj[v])

{

s.Append(w + " ");

}

s.Append("\n");

}

return s.ToString();

}

Bag.cs

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

namespace BipartiteGraphExample
{
    public class Bag<T> : IEnumerable<T>
    {

        Node<T> first;
        private int N;
        class Node<T>
        {
            public T item;
            public Node<T> next;
        }

        public bool isEmpty() { return (first == null) || (N == 0); }
        public int size() { return N; }
        public void push(T item)
        {
            // adding to the begining
            Node<T> oldfirst = first;
            first = new Node<T>();
            first.item = item;
            first.next = oldfirst;
            N++;
        }

        /* // no pop in stack method
        public T pop()
        {
            T item = first.item;
            first = first.next;
            N--;
            return item;
        }
        */

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

        public IEnumerator<T> GetEnumerator()
        {
            var node = first;
            while (node != null)
            {
                yield return node.item;
                node = node.next;
            }
        }

    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BipartiteGraphExample

{

public class Bag<T> : IEnumerable<T>

{

Node<T> first;

private int N;

class Node<T>

{

public T item;

public Node<T> next;

}

public bool isEmpty() { return (first == null) || (N == 0); }

public int size() { return N; }

public void push(T item)

{

// adding to the begining

Node<T> oldfirst = first;

first = new Node<T>();

first.item = item;

first.next = oldfirst;

N++;

}

/* // no pop in stack method

public T pop()

{

T item = first.item;

first = first.next;

N--;

return item;

}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

{

return GetEnumerator();

}

public IEnumerator<T> GetEnumerator()

{

var node = first;

while (node != null)

{

yield return node.item;

node = node.next;

}

test

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

namespace BipartiteGraphExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph("tinyG.txt");
            Console.WriteLine(g.toString());
            Bipartite b = new Bipartite(g);
            if (b.isBipartite) Console.WriteLine("Yes! Bipartite!");
            else Console.WriteLine("Not Bipartite");
            b.showCycle();
            Console.ReadLine();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BipartiteGraphExample

{

class Program

{

static void Main(string[] args)

{

Graph g = new Graph("tinyG.txt");

Console.WriteLine(g.toString());

Bipartite b = new Bipartite(g);

if (b.isBipartite) Console.WriteLine("Yes! Bipartite!");

else Console.WriteLine("Not Bipartite");

b.showCycle();

Console.ReadLine();

}

Posted in C# | Comments Off

C#. DegreeOfSeparation

Posted on 03.10.2017 by Stanislav_Panteleev

Source in Sagewick Git strange thing but realized it…, shows shortest ways from source to other points, using BFS

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

namespace SymbolGraphExample
{
    class DegreesOfSeparation
    {
        String filepath { get; set; }
        char delimiter { get; set; }
        String source { get; set; }
        SymbolGraph sg;
        Graph G;


        public DegreesOfSeparation(string afilename, char adelimiter, string asource)
        {
            filepath = afilename;
            delimiter = adelimiter;
            source = asource;
            sg = new SymbolGraph(filepath, delimiter);
            G = sg.getGraph();

        }

        public void Execute()
        {
            if (!sg.contains(source))
            {
                Console.WriteLine(source + " not in database.");
                return;
            }
            int s = sg.indexOf(source);
            BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);

            using (StreamReader sr = new StreamReader(filepath))
            {
                Queue<string> alreadyProcessed = new Queue<string>();
                while (sr.Peek() >= 0)
                {
                    String sink = sr.ReadLine();
                    String[] substrings = sink.Split(delimiter);
                   
                    foreach (string substring in substrings)
                    {
                        if (sg.contains(substring))
                        {
                            int t = sg.indexOf(substring);
                            if (bfs.hasPathTo(t)&&(substring!=source)&&(!alreadyProcessed.Contains(substring)))
                            {
                                Console.WriteLine("");
                                Console.Write("path to "+substring+" : ");
                                alreadyProcessed.Enqueue(substring);
                                foreach (int v in bfs.pathTo(t))
                                {
                                    Console.Write("   " + sg.nameOf(v));
                                }
                            }
                        }

                    }
                }
            }
        }

    }
}

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace SymbolGraphExample

{

class DegreesOfSeparation

{

String filepath { get; set; }

char delimiter { get; set; }

String source { get; set; }

SymbolGraph sg;

Graph G;

public DegreesOfSeparation(string afilename, char adelimiter, string asource)

{

filepath = afilename;

delimiter = adelimiter;

source = asource;

sg = new SymbolGraph(filepath, delimiter);

G = sg.getGraph();

}

public void Execute()

{

if (!sg.contains(source))

{

Console.WriteLine(source + " not in database.");

return;

}

int s = sg.indexOf(source);

BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);

using (StreamReader sr = new StreamReader(filepath))

{

Queue<string> alreadyProcessed = new Queue<string>();

while (sr.Peek() >= 0)

{

String sink = sr.ReadLine();

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

foreach (string substring in substrings)

{

if (sg.contains(substring))

{

int t = sg.indexOf(substring);

if (bfs.hasPathTo(t)&&(substring!=source)&&(!alreadyProcessed.Contains(substring)))

{

Console.WriteLine("");

Console.Write("path to "+substring+" : ");

alreadyProcessed.Enqueue(substring);

foreach (int v in bfs.pathTo(t))

{

Console.Write(" " + sg.nameOf(v));

}

Posted in C# | Comments Off

Category Archives: C#

C#. Поиск путей в орграфах методом DepthFirstSearch

С#. Достижимость в орграфах

C#. Digraph. Класс орграфа с примером чтения из файла

C#. Орграфы. Теория.

C#. Aлгоритмы и структуры данных. Фиксированный стэк

Starting new life period…

C# Делегаты и события

C#. Undirected Graph Basics Altogether

C#. BipartiteGraph

C#. DegreeOfSeparation

MY PROJECTS

Recent Posts

Categories