Shortest path with Dijkstra and C#

Introducing to Graphs

Graphs as restructures like trees or you prefer tress are a kind of graph, perhaps the main difference is the usage, in computer programming graphs are used in different way to trees. Binary trees are good to search for data and insert new elements, the edges usually represents quick ways to reach the nodes in all levels. The graphs, on the other hand, usually are modeled to solver physical problem; a classical example is node is a graph which represents cities and the edges which represents routes between the cities.

Just to use the same nomenclature, nodes in graphs are called vertices or one vertex, yet

Adjacency

When two vertices are connected by a single edge we say they are adjacent.

Path

A path is just a sequence of edges.

Non-Directed Graphs

That means that the edges don’t have a direction; you can go either way on them.

Directed Graphs

You can go in only one direction along an edge. This one are

Weighted Graphs

In some case you can give a weight to the edges. This number can represent physical distances between two vertices, or the time it takes to gets from one vertex to another or even the cost to travel between these two nodes.

Representing Graphs

Vertices

In most situations a vertex represents some real-world object, for example if it represents a city it may need store the name of the city. Thus, it is convenient tp represent a vertex by object of a vertex class.

public class Vertex {

public string id; // Label

public float x; // Horizontal location on screen

public float y; // Vertical location on screen

// Construcutor

public Vertex(string id, float x, float y)

{

this.id = id;

this.x = x;

this.y = y;

}

public override string ToString()

{

return (id + ” – “ + x.ToString() + ” – “ + y.ToString());

}

}

Vertex object can be places in an array; however in our case I will use a list collection. The List<T> class has properties very similar to C# arrays, one key advantage is it can grow and shrink as the number of stored objects changes. The List<T> class is contained with the System.Collections.Generic namespace. The declaration would be something like this:

public List<Vertex> Vertices;

Edges

As you noticed graphs doesn’t have a rigid organization as a tree. In a binary tree each node has a maximum two children, a graph each vertex can be connected to several other vertices. To model this free-form organization we need a different approach, two methods are commonly used for graphs: the adjacency matrix and the adjacency list. I chosen the second option for obvious reasons, it is simply dynamic. An easy way to implement an edge object is to model a class that the two vertices and the distance and additional cost between them. You can understand the cost as heuristic information, for example the one edge which represents an avenue with tree traffic lights can have a cost great than another one representing a parallel avenue with the same distance however with only one traffic light.

public class Edge

{

public Vertex Vertex1; // Vertex one

public Vertex Vertex2; // Vertex two

public float Distance; // DIstance or similar

public float Cost; // Cost or multiplier factor

// Contructor

public Edge(Vertex Vertex1, Vertex Vertex2, float distance, float cost)

{

this.Vertex1 = Vertex1;

this.Vertex2 = Vertex2;

this.Distance = distance;

this.Cost = cost;

}

}

Adjacency List

The list in adjacency list is nothing more than a linked list. Each vertex element contains the pointer for the first element to its adjacency list.

Don’t confuse the adjacency list with paths. The adjacency list shows which vertices are adjacent to—that is, one edge away

From—a given vertex, not paths from vertex to vertex.

 

The Shortest Problem

One of the most common operations performed on weighted and directed graphs is finding the shortest path from one vertex to another. Consider the following example: For vacation, you are going to travel to 10 major league baseball cities to watch games over a two-week period. You want to minimize the number of miles you have to drive to visit all 10 cities using a shortest-path algorithm. Another shortest-path problem involves creating a network of computers, where the cost could be the time to transmit between two computers or the cost of establishing and maintaining the connection. A shortest-path algorithm can determine the most effective way you can build the network.

Dijkstra’s Algorithm

One of the most famous algorithms in computer science is Dijkstra’s algorithm for determining the shortest path of a weighted graph, named for the late computer scientist Edsger Dijkstra, who invented the algorithm in the late 1950s.

Dijkstra’s algorithm finds the shortest path from any specified vertex to any other vertex and, it turns out, to all the other vertices in the graph. It does this by using what is commonly termed a greedy strategy or algorithm. A greedy algorithm breaks a problem into pieces, or stages, determining the best solution at each stage, with each sub-solution contributing to the final solution. A classic example of a greedy algorithm is making change with coins. For example, if you buy something at the store for 74 cents using a dollar bill, the cashier, if he or she is using a greedy algorithm and wants to minimize the number of coins returned, will return to you a quarter and a penny. Of course, there are other solutions to making change for 26 cents, but a quarter and a penny is the optimal solution.

We use Dijkstra’s algorithm by creating a table to store known distances from the starting vertex to the other vertices in the graph. Each vertex adjacent to the original vertex is visited, and the table is updated with information about the weight of the adjacent edge. If a distance between two vertices is known, but a shorter distance is discovered by visiting a new vertex, that information is changed in the table. The table is also updated by indicating which vertex leads to the shortest path.

Below I show how a Dikstra’s algorithm class would be implemented.
class Dijkstra

{

   public List<Vertex> Vertices;

   public List<Edge> edges;

   // Constructor

   public Dijkstra()

   {

         Vertices = new List<Vertex>(); // Holds the Vertices

         edges = new List<Edge>(); // Holds the connections

    }

    // Dijkstra calculation algorithm

    public void Execute()

    {

          while (Vertices.Count > 0)

          {

              // For each smallset Vertex

              Vertex smallest = ExtractSmallest();

             // Get the adjacents

 

             List<Vertex> adjacentVertices = AdjacentRemainingVertices(smallest);

             // for each adjacent Vertex calculate the distance

             int size = adjacentVertices.Count;

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

             {

                 Vertex adjacent = adjacentVertices.ElementAt(i);

                 float distance = Distance(smallest, adjacent) + smallest.distanceFromStart;

                 if (distance < adjacent.distanceFromStart)
                 {

                     adjacent.distanceFromStart = distance;

                     adjacent.previous = smallest;

                  }

               }

            }

         }

    …

MyApplication

Sometime ago I built an application which implements the Dijkstra’s algorithm. I used Visual Studio 2008 and of course C#. I implemented with the classes I explained before, actually this application was the reason for this posting. I tried to become it user-friendly and coder-friendly as well. If this blog has made sense for you and you do need application like that I think would be a good idea you take a look the application running and its code behind.

The application allow the user chose the vertices, each vertex has a label and a coordinate pair (X,Y). The user can either enter thought to X and Y text boxes or by clicking on the panel area. Upon the vertices defined the user has to define the linking of each vertex. The origin and destination combo boxes have the updated list of vertices; the user needs to chose the origin vertex and the destination vertex and click on the Add Connection button. A blue line showing the linking between the vertices will be plotted as well the cost between these two vertices. In this case the cost is a multiplier factor that will be used to add some kind of heuristic on the solution. The distance between the vertices in fact is measurement for shortest-path calculations. The distance is calculated automatically by calculating the distance between two Cartesian coordinates.

With the set of vertices and connections (edges) defined the user can calculate the shortest path choosing the origin vertex, the destination vertex and clicking on the Find Shortest Path button. A report with the total distance and path found will be shown. The yellow line will be plotted tracing the path among the nodes. The user can save and load the map to a text file called vertices.txt. This file has a very simple format and it can be edited by a simple text editor like Notepad.

Download

Link to ZIP file with the Executable file and the Vertices.TXT file.

If you wish the fully commented source code send me by paypal to patrick_faria@hotmail.com US$9.99 operating cost fee and I will reply a ZIP file with the whole visual studio project folder. You don’t get any restrictions to use, modify or distribute the source code or pieces of it.

String Class

In C#, the string type is used for processing multiple character Unicode character data. (The char type, by comparison, is a value type that handles single characters.)

The type name string is a shortened name for the System.String class. The compiler can process this shortened form; therefore string and System.String can be used interchangeably.

The String class represents an immutable string of characters. An instance of String is immutable: the text of a string cannot be modified after it has been created. Methods that might appear at first sight to modify a string value actually return a new instance of string that contains the modification.

The StringBuilder class is often used in partnership with the String class. A StringBuilder builds an internally modifiable string that can be converted into an immutable String when complete. StringBuilder removes the need to repeatedly create temporary immutable Strings and can provide improved performance.

The System.String class has many methods. I will list some of the more useful methods. For further details, consult the .NET Framework software development kit (SDK) Help documents.

Common String Methods, Operators, and Properties

Brackets [ ]

You can extract a single character at a given position in a string by using the string name followed by the index in brackets ([ and ]). This process is similar to using an array. The first character in the string has an index of zero. The following code provides an example:

string s = “Alphabet”;

char firstchar = s[2]; // ‘p’

Strings are immutable, so assigning a character by using brackets is not permitted. Any attempt to assign a character to a string in this way will generate a compile-time error, as shown:

s[2] = ‘*’; // Not valid

Insert Method

If you want to insert characters into a string variable, use the Insert instance method to return a new string with a specified value inserted at a specified position in this string. This method takes two parameters: the position of the start of the insertion and the string to insert. The following code provides an example:

string s = “C is great!”;

s = s.Insert(2, “Sharp “);

Console.WriteLine(s); // C Sharp is great!

Length Property

The Length property returns the length of a string as an integer, as shown:

string msg = “Hello”;

int slen = msg.Length; // 5

Copy Method

The Copy class method creates a new string by copying another string. The Copy method makes a duplicate of a specified string. The following code provides an example:

string s1 = “Hello”;

string s2 = String.Copy(s1);

Concat Method

The Concat class method creates a new string from one or more strings or objects represented as strings. The following code provides an example:

string s3 = String.Concat(“a”, “b”, “c”, “d”, “e”, “f”, “g”);

The + operator is overloaded for strings, so the example above can be re-written as follows:

string s = “a” + “b” + “c” + “d” + “e” + “f” + “g”;

Console.WriteLine(s);

Trim Method

The Trim instance method removes all of the specified characters or white space from the beginning and end of a string. The following code provides an example:

string s = ” Hello “;

s = s.Trim();

Console.WriteLine(s); // “Hello”

ToUpper and ToLower Methods

The ToUpper and ToLower instance methods return a string with all characters converted to uppercase and lowercase, respectively, as shown:

string sText = “How to Succeed “;

Console.WriteLine(sText.ToUpper()); // HOW TO SUCCEED

Console.WriteLine(sText.ToLower()); // how to succeed

String Comparisons

You can use the == and != operators on string variables to compare string contents.

Equals Method

The System.String class contains an instance method called Equals, which can be used to compare two strings for equality. The method returns a bool value that is true if the strings are the same and false otherwise. This method is overloaded and can be used as an instance method or a static method. The following example shows both forms.

string s1 = “Welcome”;

string s2 = “Welcome”;

if (s1.Equals(s2))

Console.WriteLine(“The strings are the same”);

if (String.Equals(s1,s2))

Console.WriteLine(“The strings are the same”);

Compare Method

The Compare method compares two strings lexically; that is, it compares the strings according to their sort order. The return value from Compare is as follows:

• A negative integer if the first string comes before the second
• 0 if the strings are the same
• A positive integer if the first string comes after the second

string s1 = “Tintinnabulation”;

string s2 = “Velocipede”;

int comp = String.Compare(s1,s2); // Negative return

By definition, any string, including an empty string, compares greater than a null reference, and two null references compare equal to each other. Compare is overloaded. There is a version with three parameters, the third of which is a bool value that specifies whether the case should be ignored in the comparison. The following example shows a case-insensitive comparison:

s1 = “cabbage”;

s2 = “Cabbage”;

comp = String.Compare(s1, s2, true); // Ignore case

Locale-Specific Compare Options

The Compare method has overloaded versions that allow string comparisons based on language-specific sort orders. This can be useful when writing applications for an international market. Further discussion of this feature is beyond the scope of the course. For more information, search for “System.Globalization namespace” and “CultureInfo class” in the .NET ramework SDK Help documents.

String Comparison Operators

The == and != operators are overloaded for the String class. You can use these operators to examine the contents of strings.

string a = “Test”;

string b = “Test”;

if (a == b) … // Returns true

The following operators and methods are equivalent:

• The == operator is equivalent to the String.Equals method.
• The != operator is equivalent to the !String.Equals method.

The other relational operators (<, >, <=, and >=) are not overloaded for the String class.

Using the this Keyword

The this keyword implicitly refers to the object that is making an object method call.

In the following code, the statement name = name would have no effect at all. This is because the identifier name on the left side of the assignment does not resolve to the private BankAccount field called name. Both identifiers resolve to the method parameter, which is also called name.

class BankAccount

{

          private string name;

          public void SetName(string name)

         {

name = name;

         }

}

The C# compiler does not emit a warning for this bug.

Using the this Keyword

You can solve this reference problem by using the this keyword, as illustrated on the image. The this keyword refers to the current object for which the method is called. Static methods cannot use this as they are not called by using an object.

Changing the Parameter Name

You can also solve the reference problem by changing the name of the parameter, as in the following example:

class BankAccount

{

          private string name;

          public void SetName(string newName)

         {

name = newName;

}

}

Using this when writing constructors is a common C# idiom. The following code provides an example:

struct Time

{

          public Time(int hour, int minute)

         {

this.hour = hour;

this.minute = minute;

}

           private int hour, minute;

}

The this keyword is also used to implement call chaining. Notice in the following class that both methods return the calling object:

class Book

{

          private string author, title;

          public Book SetAuthor(string author)

         {

this.author = author;

return this;

          }

          public Book SetTitle(string title)

        {

this.title = title;

return this;

        }

}

Returning this allows method calls to be chained together, as follows:

class Usage

{

          static void Chained(Book good)

         {

good.SetAuthor(” Fowler”).SetTitle(” Refactoring”);

         }

        static void NotChained(Book good)

       {

good.SetAuthor(“Fowler”);

good.SetTitle(” Refactoring”);

       }

}

A static method exists at the class level and is called against the class and not against an object. This means that a static method cannot use the this operator.

Why Is Main Static?

Making Main static allows it to be invoked without the runtime needing to create an instance of the class. Non-static methods can only be called on an object, as shown in the following code:

class Example

{

     void NonStatic( ) { … }

     static void Main( )

    {

Example eg = new Example( );

eg.NonStatic( ); // Compiles

NonStatic( ); // compile-time error

    }

    …

}

This means that if Main is non-static, as in the following code, the runtime needs to create an object in order to call Main.

class Example

{

    void Main( )

     {

…

      }

}

In other words, the runtime would effectively need to execute the following code:

Example run = new Example( );

run.Main( );

C# Array Unleashed

Arrays provide an important means for grouping data. To make the most of C#, it is important to understand how to use and create arrays effectively.

Arrays are sequences of data of the same type. For example, a sequence of houses naturally group together to form a street. You can access an individual element of an array by using its integer position, which is called an index.

Arrays allow random access. The elements of an array are located in contiguous memory. This means a program can access all array elements equally quickly.

Array Notation in C#

In C#, array notation is very similar to the notation used by C and C++, although it differs in two subtle-but-important ways:

• You cannot write square brackets to the right of the name of the variable.
• You do not specify the size of the array when declaring an array variable.

The following are examples of allowed and disallowed notation in C#:

type[ ]name; // Allowed

type name[ ]; // Disallowed in C#

type[4] name; // Also disallowed in C#

Array Rank

To declare a one-dimensional array variable, you use unadorned square brackets as shown on the slide. Such an array is also called an array of rank 1 because one integer index associates with each element of the array.

To declare a two-dimensional array, you use a single comma inside the square brackets, as shown on the slide. Such an array is called an array of rank 2 because two integer indexes associate with each element of the array. This notation extends in the obvious way: each additional comma between the square brackets increases the rank of the array by one.

Accessing Array Elements

To access an element inside an array of rank 1, use one integer index. To access an element inside an array of rank 2, use two integer indexes separated by a comma. This notation extends in the same way as the notation for declaring variables. To access an element inside an array of rank n, use n integer indexes separated by commas.

Array indexes (for all ranks) start from zero. To access the first element inside a row, use the expression:

row[0]

rather than the expression:

row[1]

Some programmers use the phrase “initial element” rather than “first element” to try to avoid any potential confusion. Indexing from 0 means that the last element of an array instance containing size elements is found at [size-1] and not at [size]. Accidentally using [size] is a common off-by-one error, especially for programmers used to a language that indexes from one, such as Visual Basic.

Checking Array Bounds

In C#, an array element access expression is automatically checked to ensure that the index is valid. This implicit bounds check cannot be turned off. Bounds checking is one of the ways of ensuring that C# is a type-safe language

Even though array bounds are automatically checked, you should still make sure that integer indexes are always in bounds. To do this, you should manually check the index bounds, often using a for statement termination condition, as follows:

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

Console.WriteLine(row[i]);

}

The Length property is the total length of the array, regardless of the rank of the array. To determine the length of a specific dimension, you can use the GetLength method, as follows:

for (int r = 0; r < grid.GetLength(0); r++)

{

for (int c = 0; c < grid.GetLength(1); c++)

{

Console.WriteLine(grid[r,c]);

}

}

Comparing Arrays to Collections

The size of an array instance and the type of its elements are permanently fixed when the array is created. To create an array that always contains exactly 42 elements of type int, use the following syntax:

int[ ] rigid = new int [ 42 ];

The array will never shrink or expand, and it will never contain anything other than ints. Collections are more flexible; they can expand or contract as elements are removed and added. Arrays are intended to hold elements of a single type, but collections were designed to contain elements of many different types. You can achieve this flexibility by using boxing, as follows:

ArrayList flexible = new ArrayList( );

flexible.Add(“one”); // Add a string here

…

flexible.Add(99); // And an int here!

You cannot create an array instance with read-only elements. The following code will not compile:

const int[ ] array = {0, 1, 2, 3};

readonly int[ ] array = {4,2};

However, you can create a read-only collection as follows:

ArrayList flexible = new ArrayList( );

…

ArrayList noWrite = ArrayList.ReadOnly(flexible);

noWrite[0] = 42; // Causes run-time exception

Creating Array Instances

Declaring an array variable does not actually create an array instance. This is because arrays are reference types and not value types. You use the new keyword to create an array instance, also referred to as an array creation expression. You must specify the size of all rank lengths when creating an array instance. The following code will result in a compile-time error:

long[ ] row = new long[ ]; // Not allowed

int[,] grid = new int[,]; // Not allowed

The C# compiler implicitly initializes each array element to a default value dependent on the array element type: integer array elements are implicitly initialized to 0, floating-point array elements are implicitly initialized to 0.0, and Boolean array elements are implicitly initialized to false. In other words, the C# code:

long[ ] row = new long[4];

will execute the following code at run-time:

long[ ] row = new long[4];

row[0] = 0L;

row[1] = 0L;

row[2] = 0L;

row[3] = 0L;

The compiler always allocates arrays in contiguous memory, regardless of the base type of the array and the number of dimensions. If you create an array with an expression such as new int[2,3,4], it is conceptually 2 x 3 x 4, but the underlying memory allocation is a single block of memory large enough to contain 2*3*4 elements.

Initializing Array Elements

You can use an array initializer to initialize the values of the array instance elements. An array initializer is a sequence of expressions enclosed by curly braces and separated by commas. Array initializers are executed from left to right and can include method calls and complex expressions, as in the following example:

int[ ] data = new int[4]{a, b( ), c*d, e( )+f( )};

You can also use array initializers to initialize arrays of structs:

struct Date { … }

Date[ ] dates = new Date[2];

You can only use this convenient shorthand notation when you initialize an array instance as part of an array variable declaration and not as part of an ordinary assignment statement.

int[ ] data1 = new int[4]{0, 1, 2, 3}; // Allowed

int[ ] data2 = {0, 1, 2, 3}; // Allowed

data2 = new int[4]{0, 1, 2, 3}; // Allowed

data2 = {0, 1, 2, 4}; // Not allowed

When initializing arrays, you must explicitly initialize all array elements. It is not possible to let trailing array elements revert back to their default value of zero:

int[ ] data3 = new int[2]{}; // Not allowed

int[ ] data4 = new int[2]{42}; // Still not allowed

int[ ] data5 = new int[2]{42,42}; // Allowed

Initializing Multidimensional Array Elements

You must explicitly initialize all array elements regardless of the array dimension:

int[,] data = new int[2,3] { // Allowed

{42, 42, 42},

{42, 42, 42},

};

int[,] data = new int[2,3] { // Not allowed

{42, 42},

{42, 42, 42},

};

int[,] data = new int[2,3] { // Not allowed

{42},

{42, 42, 42},

};

Creating a Computed Size Array

You can create multidimensional arrays by using run-time expressions for the length of each dimension, as shown in the following code:

System.Console.WriteLine(“Enter number of rows : “);

string s1 = System.Console.ReadLine( );

int rows = int.Parse(s1);

System.Console.WriteLine(“Enter number of columns: “);

string s2 = System.Console.ReadLine( );

int cols = int.Parse(s2);

…

int[,] matrix = new int[rows,cols];

Alternatively, you can use a mixture of compile-time constants and run-time expressions:

System.Console.WriteLine(“Enter number of rows: “);

string s1 = System.Console.ReadLine( );

int rows = int.Parse(s1);

…

int[,] matrix = new int[rows,4];

There is one minor restriction. You cannot use a run-time expression to specify the size of an array in combination with array-initializers:

string s = System.Console.ReadLine( );

int size = int.Parse(s);

int[ ] data = new int[size]{0,1,2,3}; // Not allowed

Copying Array Variables

When you copy an array variable, you do not get a full copy of the array instance. Analyzing the code shown in the slide reveals what happens when an array variable is copied. The following statements declare array variables called copy and row that both refer to the same array instance (of four long integers).

long[ ] row = new long[4];

long[ ] copy = row;

The following statement increments the initial element of this array instance from 0 to 1. Both array variables still refer to the same array instance, whose initial element is now 1.

row[0]++;

The next statement initializes a long integer called value from copy[0], which is the initial array element of the array instance referred to by copy.

long value = copy[0];

Since copy and row both refer to the same array instance, initializing the value from row[0] has exactly the same effect. The final statement writes out value (which is 1) to the console:

Console.WriteLine(value);

Array Properties

The Rank property is a read-only integer value that specifies the dimension of the array instance. For example, given the code

int[ ] one = new int[a];

int[,] two = new int[a,b];

int[,,] three = new int[a,b,c];

the resulting rank values are as follows:

one.Rank == 1

two.Rank == 2

three.Rank == 3

The Length property is a read-only integer value that specifies the total length of the array instance. For example, given the same three array declarations above, the resulting length values are:

one.Length == a

two.Length == a * b

three.Length == a * b * c

Array Methods

The System.Array class (a class that all arrays implicitly support) provides many methods that you can use when working with arrays. This topic describes some of the most commonly used methods.

Sort method

This method performs an in-place sort on an array provided as an argument. You can use this method to sort arrays of structures and classes as long as they support the IComparable interface.

int[ ] data = {4,6,3,8,9,3}; // Unsorted

System.Array.Sort(data); // Now sorted

Clear method

This method resets a range of array elements to zero (for value types) or null (for reference types), as shown:

int[ ] data = {4,6,3,8,9,3};

System.Array.Clear(data, 0, data.Length);

Clone method

This method creates a new array instance whose elements are copies of the elements of the cloned array. You can use this method to clone arrays of user-defined structs and classes. Following is an example:

int[ ] data = {4,6,3,8,9,3};

int[ ] clone = (int [ ])data.Clone( );

Caution

The Clone method performs a shallow copy. If the array being copied contains references to objects, the references will be copied and not the objects; both arrays will refer to the same objects.

GetLength method

This method returns the length of a dimension provided as an integer argument. You can use this method for bounds-checking multidimensional arrays. Following is an example:

int[,] data = { {0, 1, 2, 3}, {4, 5, 6, 7} };

int dim0 = data.GetLength(0); // == 2

int dim1 = data.GetLength(1); // == 4

IndexOf method

This method returns the integer index of the first occurrence of a value provided as an argument, or –1 if the value is not present. You can only use this method on one-dimensional arrays. Following is an example:

int[ ] data = {4,6,3,8,9,3};

int where = System.Array.IndexOf(data, 9); // == 4

Returning Arrays from Methods

In the slide, the CreateArray method is implemented by using two statements. You can combine these two statements into one return statement as follows:

static int[ ] CreateArray(int size)

{

return new int[size];

}

C++ programmers should note that in both cases the size of the array that is returned is not specified. If you specify the array size, you will get a compile time error, as in this example:

static int[4] CreateArray( ) // Compiler error

{

return new int[4];

}

You can also return arrays of rank greater than one, as shown in the following example:

static int[,] CreateArray( ) {

string s1 = System.Console.ReadLine( );

int rows = int.Parse(s1);

string s2 = System.Console.ReadLine( );

int cols = int.Parse(s2);

return new int[rows,cols];

}

Passing Arrays as Parameters

 

When you pass an array variable as an argument to a method, the method parameter becomes a copy of the array variable argument. In other words, the array parameter is initialized from the argument. You use the same syntax to initialize the array parameter that you used to initialize an array variable, as described earlier in the Copying Array Variables topic. The array argument and the array parameter both refer to the same array instance.

In the code shown on the slide, arg is initialized with an array instance of length 4 that contains the integers 10, 9, 8, and 7. Then arg is passed as the argument to Method. Method accepts arg as a parameter, meaning that arg and parameter both refer to the same array instance (the one used to initialize arg). The expression parameter[0]++ inside Method then increments the initial element in the same array instance from 10 to 11. (Since the initial element of an array is accessed by specifying the index value 0 and not 1, it is also referred to as the “zeroth” element.) Method then returns and Main writes out the value of arg[0] to the console. The arg parameter still refers to the same array instance, the zeroth element of which has just been incremented, so 11 is written to the console.

Because passing an array variable does not create a deep copy of the array instance, passing an array as a parameter is very fast. If you want a method to have write access to the argument’s array instance, this shallow copy behavior is entirely appropriate.

The Array.Copy method is useful when you need to ensure that the called method will not alter the array instance and you are willing to trade a longer running time for this guarantee. You can also pass a newly created array as an array parameter as follows:

Method(new int[4]{10, 9, 8, 7});

Using Recursive Methods in C#

A method can call itself. This technique is known as recursion. You can address some types of problems with recursive solutions. Recursive methods are often useful when manipulating more complex data structures such as lists and trees.

Methods in C# can be mutually recursive. For example, a situation in which method A can call method B, and method B can call method A, is allowable.

Example of a Recursive Method

The Fibonacci sequence occurs in several situations in mathematics and biology (for example, the reproductive rate and population of rabbits). The nth member of this sequence has the value 1 if n is 1 or 2; otherwise, it is equal to the sum of the preceding two numbers in the sequence. Notice that when n is greater than two the value of the nth member of the sequence is derived from the values of two previous values of the sequence. When the definition of a method refers to the method itself, recursion might be involved.

You can implement the Fibonacci method as follows:

static ulong Fibonacci(ulong n)

{

if (n <= 2)

return 1;

else

return Fibonacci(n-1) + Fibonacci(n-2);

}

 

Notice that two calls are made to the method from within the method itself. A recursive method must have a terminating condition that ensures that it will return without making further calls. In the case of the Fibonacci method, the test for n <= 2 is the terminating condition

Implementing a Method by Using Recursion

If you read the previous blog we implemented the Factorial method using Output parameters , no we will re-implement it using recursion rather than a loop.

The factorial of a number can be defined recursively as follows: the factorial of zero is 1, and you can find the factorial of any larger integer by multiplying that integer with the factorial of the previous number. In summary:

If n=0, then Factorial(n) = 1; otherwise it is n * Factorial(n-1)

//

// Another way to solve the factorial problem,

// this time as a recursive function

//

public static bool RecursiveFactorial(int n, out int f)

{

bool ok=true;

// Trap negative inputs

if (n<0)

{

f=0;

ok = false;

}

if (n<=1)

f=1;

else

{

try

{

int pf;

ok = RecursiveFactorial(n-1,out pf);

f = n * pf;

}

catch(Exception)

{

// Something went wrong. Set error

// flag and return zero.

f=0;

ok=false;

}

}

return ok;

}

Using Parameters in C#

Parameters allow information to be passed into and out of a method. When you define a method, you can include a list of parameters in parentheses following the method name. I will show how to declare parameters and how to call methods with parameters.

Declaring Parameters

Each parameter has a type and a name. You declare parameters by placing the parameter declarations inside the parentheses that follow the name of the method. The syntax that is used to declare parameters is similar to the syntax that is used for example to declare local variables, except that you separate each parameter declaration with a comma instead of with a semicolon.

The following example shows how to declare a method with parameters:

static void MethodWithParameters(int n, string y)

{

// …

}

This example declares the MethodWithParameters method with two parameters: n and y. The first parameter is of type int, and the second is of type string. Note that commas separate each parameter in the parameter list.

Calling Methods with Parameters

The calling code must supply the parameter values when the method is called. The following code shows two examples of how to call a method with parameters. In each case, the values of the parameters are found and placed into the parameters n and y at the start of the execution of MethodWithParameters.

MethodWithParameters(2, “Hello, world”);

int p = 7;

string s = “Test message”;

MethodWithParameters(p, s);

Mechanisms for Passing Parameters

Parameters can be passed in three different ways:

By value – Value parameters are sometimes called in parameters because data can be transferred into the method but cannot be transferred out.

By reference – Reference parameters are sometimes called in/out parameters because data can be transferred into the method and out again.

By output – Output parameters are sometimes called out parameters because data can be transferred out of the method but cannot be transferred in.

 

Pass by Value

In applications, most parameters are used for passing information into a method but not out. Therefore, pass by value is the default mechanism for passing parameters in C#.

 

Defining Value Parameters

The simplest definition of a parameter is a type name followed by a variable name. This is known as a value parameter. When the method is called, a new storage location is created for each value parameter, and the values of the corresponding expressions are copied into them. The expression supplied for each value parameter must be the same type as the declaration of the value parameter, or a type that can be implicitly converted to that type. Within the method, you can write code that changes the value of the parameter. It will have no effect on any variables outside the method call.

In the following example, the variable x inside AddOne is completely separate from the variable k in Main. The variable x can be changed in AddOne, but this has no effect on k.

 

static void AddOne(int x)

{

x++;

}

 

static void Main( )

{

int k = 6;

AddOne(k);

Console.WriteLine(k); // Display the value 6, not 7

}

 

What Are Reference Parameters?

A reference parameter is a reference to a memory location. Unlike a value parameter, a reference parameter does not create a new storage location. Instead, a reference parameter represents the same location in memory as the variable that is supplied in the method call.

 

Declaring Reference Parameters

You can declare a reference parameter by using the ref keyword before the type name, as shown in the following example:

static void ShowReference(ref int nId, ref long nCount)

{

// …

}

 

Using Multiple Parameter Types

The ref keyword only applies to the parameter following it, not to the whole parameter list. Consider the following method, in which nId is passed by reference but longVar is passed by value:

static void OneRefOneVal(ref int nId, long longVar)

{

// …

}

 

Matching Parameter Types and Values

When calling the method, you supply reference parameters by using the ref keyword followed by a variable. The value supplied in the call to the method

must exactly match the type in the method definition, and it must be a variable,
not a constant or calculated expression.

int x;

long q;

ShowReference(ref x, ref q);

If you omit the ref keyword, or if you supply a constant or calculated expression, the compiler will reject the call, and you will receive an error message similar to the following: “Cannot convert from ‘int’ to ‘ref int.’”

 

Changing Reference Parameter Values

If you change the value of a reference parameter, the variable supplied by the caller is also changed, because they are both references to the same location in memory. The following example shows how changing the reference parameter also changes the variable:

static void AddOne(ref int x)

{

x++;

}

static void Main( )

{

int k = 6;

AddOne(ref k);

Console.WriteLine(k); // Display the value 7

}

This works because when AddOne is called, its parameter x is set up to refer to the same memory location as the variable k in Main. Therefore, incrementing x will increment k.

 

Assigning Parameters Before Calling the Method

A ref parameter must be definitively assigned at the point of call; that is, the compiler must ensure that a value is assigned before the call is made. The following example shows how you can initialize reference parameters before calling the method:

static void AddOne(ref int x)

{

x++;

}

static void Main( )

{

int k = 6;

AddOne(ref k);

Console.WriteLine(k); // 7

}

The following example shows what happens if a reference parameter k is not initialized before its method AddOne is called:

int k;

AddOne(ref k);

Console.WriteLine(k);

The C# compiler will reject this code and display the following error message: “Use of unassigned local variable ‘k.‘”

Output Parameters

 

What Are Output Parameters?

Output parameters are like reference parameters, except that they transfer data out of the method rather than into it. Like a reference parameter, an output parameter is a reference to a storage location supplied by the caller. However, the variable that is supplied for the out parameter does not need to be assigned a value before the call is made, and the method will assume that the parameter has not been initialized on entry.

Output parameters are useful when you want to be able to return values from a method by means of a parameter without assigning an initial value to the parameter.

 

Using Output Parameters

To declare an output parameter, use the keyword out before the type and name, as shown in the following example:

static void OutDemo(out int p)

{

// …

}

As with the ref keyword, the out keyword only affects one parameter, and each out parameter must be marked separately.

When calling a method with an out parameter, place the out keyword before the variable to be passed, as in the following example.

int n;

OutDemo(out n);

In the body of the method being called, no initial assumptions are made about the contents of the output parameter. It is treated just like an unassigned local variable. The out parameter must be assigned a value inside the method.

Using Variable-Length Parameter Lists

C# provides a mechanism for passing variable-length parameter lists.

 

Declaring Variable-Length Parameters

It is sometimes useful to have a method that can accept a varying number of parameters. In C#, you can use the params keyword to specify a variablelength parameter list. When you declare a variable-length parameter, you must:

• Declare only one params parameter per method.
• Place the parameter at the end of the parameter list.
• Declare the parameter as a single-dimension array type.

The following example shows how to declare a variable-length parameter list:

static long AddList(params long[ ] v)

{

long total;

long i;

for (i = 0, total = 0; i < v. Length; i++)

total += v[i];

return total;

}

Because a params parameter is always an array, all values must be the same type.

 

Passing Values

When you call a method with a variable-length parameter, you can pass values to the params parameter in one of two ways:

• As a comma separated list of elements (the list can be empty)
• As an array

The following code shows both techniques. The two techniques are treated in exactly the same way by the compiler.

static void Main( )

{

long x;

x = AddList(63, 21, 84); // List

x = AddList(new long[ ]{ 63, 21, 84 }); // Array

}

Regardless of which method you use to call the method, the params parameter is treated like an array. You can use the Length property of the array to determine how many parameters were passed to each call.

In a params parameter, a copy of the data is made, and although you can modify the values inside the method, the values outside the method are unchanged.

 

Using Methods with Output Parameters

We will write a new method called Factorial that takes an int value and calculates its factorial. The factorial of a number is the product of all the numbers between 1 and that number. The factorial of zero is defined to be 1.

The following are examples of factorials:

Factorial(0) = 1

Factorial(1) = 1

Factorial(2) = 1 * 2 = 2

Factorial(3) = 1 * 2 * 3 = 6

Factorial(4) = 1 * 2 * 3 * 4 = 24

namespace Utils

{

using System;

 

public class Utils

{

//

// Calculate factorial

// and return the result as an out parameter

//

public static bool Factorial(int n, out int answer)

{

int k; // Loop counter

int f; // Working value

bool ok=true; // True if okay, false if not

// Check the input value

if (n<0) ok = false;

// Calculate the factorial value as the

// product of all of the numbers from 2 to n

try

{

//checked

f = 1;

for (k=2; k<=n; ++k)

{

f = f * k;

}

}

catch(Exception)

{

// If something goes wrong in the calculation,

// catch it here. All exceptions

// are handled the same way: set the result

// to zero and return false.

f = 0;

ok = false;

}

// Assign result value

answer = f;

// Return to caller

return ok;

}

}

}

 

To test the Factorial method:

namespace Utils

{

public class Test

{

static void Main( )

{

int f; // Factorial result

bool ok; // Factorial success or failure

… existing code omitted for clarity …

// Get input for factorial

Console.WriteLine(“Number for factorial:”);

x = int.Parse(Console.ReadLine( ));

// Test the factorial function

ok = Utils.Factorial(x, out f);

// Output factorial results

if (ok)

Console.WriteLine(“Factorial(” + x + “) = ” + f);

else

Console.WriteLine(“Cannot compute this_factorial”);

}

}

}

Checking for Arithmetic Overflow in C#

As a developer, you sometimes seem to spend more time checking for errors and handling them than you do on the core logic of the actual program. You can address this issue by using exceptions. Exceptions are designed to handle errors, my intention is not cover the whole exception topic, but just a specific C# feature which allow us to handle one of the most common exception.

By default, a C# program will not check arithmetic for overflow. The following code provides an example:

// example.cs

class Example

{

static void Main( )

{

int number = int.MaxValue;

Console.WriteLine(++number);

}

}

In the preceding code, number is initialized to the maximum value for an int. The expression ++number increments number to –2147483648, the largest negative int value, which is then written to the console. No error message is generated.

 

Controlling Arithmetic Overflow Checking

When compiling a C# program, you can globally turn on arithmetic overflow checking by using the /checked+ command line option, as follows:

c:\ csc /checked+ example.cs

 The resulting executable program will cause an exception of class System.OverflowException. Similarly, you can turn off global arithmetic overflow checking by using the /checked- command line option, as follows:

c:\ csc /checked- example.cs

 The resulting executable program will silently wrap the int value to int.MinValue and will not cause an exception of class  System.OverflowException.

Creating Checked and Unchecked Statements

You can use the checked and unchecked keywords to create statements that are explicitly checked or unchecked statements:

checked { statement-list }

unchecked { statement-list }

Regardless of the compile-time /checked setting, the statements inside a checked statement list are always checked for arithmetic overflow. Similarly, regardless of the compile-time /checked setting, the statements inside an unchecked statement list are never checked for arithmetic overflow.

 

Creating Checked and Unchecked Expressions

You can also use the checked and unchecked keywords to create checked and unchecked expressions:

checked ( expression )

unchecked ( expression )

A checked expression is checked for arithmetic overflow; an unchecked expression is not. For example, the following code will generate a System.OverflowException.

// example.cs

class Example

{

static void Main( )

{

int number = int.MaxValue;

Console.WriteLine(checked(++number));

}

}

Generating XML Documentation in C#

It is important to provide adequate documentation for all of your applications. Provide enough comments to enable a developer who was not involved in creating the original application to follow and understand how the application works. Visual Studio allows you to write documentation and easily integrate it to IDE.

C# provides several mechanisms for adding comments to application code: single-line comments, multiple-line comments, and XML-generated documentation.

Generating XML Documentation

You can use C# comments to generate XML documentation for your applications.

Documentation comments begin with three forward slashes (///) followed by an XML documentation tag. For examples, below:

There are a number of suggested XML tags that you can use. (You can also create your own.) The following table shows some XML tags and their uses.

 

 

Tag	Purpose
<summary> … </summary>	To provide a brief description. Use the <remarks> tag for a longer description.
<remarks> … </remarks>	To provide a detailed description. This tag can contain nested paragraphs, lists, and other types of tags.
<para> … </para>	To add structure to the description in a <remarks> tag. This tag allows paragraphs to be delineated.
<list type=”…”> … </list>	To add a structured list to a detailed description. The types of lists supported are “bullet,” “number,” and “table.” Additional tags (<term> … </term> and <description> … </description>) are used inside the list to further define the structure.
<example> … </example>	To provide an example of how a method, property, or other library member should be used. It often involves the use of a nested <code> tag.
<code> … </code>	To indicate that the enclosed text is application code.
<c> … </c>	To indicate that the enclosed text is application code. The <code> tag is used for lines of code that must be separated from any enclosing description; the <c> tag is used for code that is embedded within an enclosing description.
<see cref=”member“/>	To indicate a reference to another member or field. The compiler checks that “member” actually exists.
<seealso cref=”member“/>	To indicate a reference to another member or field. The compiler checks that “member” actually exists. The difference between <see> and <seealso> depends upon the processor that manipulates the XML once it has been generated. The processor must be able to generate See and See Also sections for these two tags to be distinguished in a meaningful way.            <exception> … </exception> To provide a description for an exception class.
<permission> … </permission>	To document the accessibility of a member.
<param name=”name“> … </param>	To provide a description for a method parameter.
<returns> … </returns>	To document the return value and type of a method.
<value> … </value>	To describe a property.

 

You can compile the XML tags and documentation into an XML file by using the C# compiler with the /doc option:

csc myprogram.cs /doc:mycomments.xml

 If there are no errors, you can view the XML file that is generated by using a tool such as Internet Explorer.

The purpose of tuhe /doc option is only to generate an XML file. To render the file, you will need another processor. Internet Explorer displays a simple rendition that shows the structre of the file and allows tags to be expanded or collapsed, but it will not, for example, display the <list type=”bullet”> tag as a bullet.

Using the documentation integrated with the Visual Studio IDE

Upon you have written the XML documentation .NET automatically will become it available in developing time, exactly who happens with the internal class and methods.

Basic Input/Output operations in C#

This blog I will show how to perform command-based input/output operations in C# by using the Console class. I will show you how to display information by using the Write and WriteLine methods, and how to gather input information from the keyboard by using the Read and ReadLine methods.

 

The Console Class

The Console class provides a C# application with access to the standard input, standard output, and standard error streams. Standard input is normally associated with the keyboard—anything that the user types on the keyboard can be read from the standard input stream. Similarly, the standard output stream is usually directed to the screen, as is the standard error stream.

These streams and the Console class are only meaningful to console applications. These are applications that run in a Command window.

 
Write and WriteLine Methods

You can use the Console.Write and Console.WriteLine methods to display information on the console screen. These two methods are very similar; the

main difference is that WriteLine appends a new line/carriage return pair to the end of the output, and Write does not. Both methods are overloaded. You can call them with variable numbers and types of parameters. For example, you can use the following code to write “99″ to the screen:

Console.WriteLine(99);

You can use the following code to write the message “Hello, World” to the screen:

Console.WriteLine(“Hello, World”);

 
Text Formatting

You can use more powerful forms of Write and WriteLine that take a format string and additional parameters. The format string specifies how the data is

output, and it can contain markers, which are replaced in order by the parameters that follow. For example, you can use the following code to display the message “The sum of 100 and 130 is 230″:

Console.WriteLine(“The sum of {0} and {1} is {2}”, 100, 130, 100+130);

You can use the format string parameter to specify field widths and whether values should be left or right justified in these fields, as shown in the following code:

Console.WriteLine(“\”Left justified in a field of width 10:{0, -10}\”", 99);

Console.WriteLine(“\”Right justified in a field of width 10:{0,10}\”", 99);

This will display the following on the console:

“Left justified in a field of width 10: 99 “

“Right justified in a field of width 10: 99″

 
You can use the backward slash (\) character in a format string to turn off the special meaning of the character that follows it. For example, “\{” will cause a literal “{” to be displayed, and “\\” will display a literal “\”. You can use the at sign (@) character to represent an entire string verbatim. For example, @”\\server\share” will be processed as \\server\share.

 
Numeric Formatting

You can also use the format string to specify how numeric data is to be formatted. The full syntax for the format string is {N,M:FormatString}, where N is the parameter number, M is the field width and justification, and FormatString specifies how numeric data should be displayed. The table below summarizes the items that may appear in FormatString. In all of these formats, the number of digits to be displayed, or rounded to, can optionally be specified.

 

 

Item	Meaning
C	Display the number as currency, using the local currency symbol and conventions.
D	Display the number as a decimal integer.
E	Display the number by using exponential (scientific) notation.
F	Display the number as a fixed-point value.
G	Display the number as either fixed point or integer, depending on which format is the most compact.
N	Display the number with embedded commas.
X	Display the number by using hexadecimal notation.

 

The following code shows some examples of how to use numeric formatting:

 
Console.WriteLine(“Currency formatting – {0:C} {1:C4}”, 88.8,-888.8);

Console.WriteLine(“Integer formatting – {0:D5}”, 88);

Console.WriteLine(“Exponential formatting – {0:E}”, 888.8);

Console.WriteLine(“Fixed-point formatting – {0:F3}”,888.8888);

Console.WriteLine(“General formatting – {0:G}”, 888.8888);

Console.WriteLine(“Number formatting – {0:N}”, 8888888.8);

Console.WriteLine(“Hexadecimal formatting – {0:X4}”, 88);

 
When the previous code is run, it displays the following:

 
Currency formatting – $88.80 ($888.8000)

Integer formatting – 00088

Exponential formatting – 8.888000E+002

Fixed-point formatting – 888.889

General formatting – 888.8888

Number formatting – 8,888,888.80

Hexadecimal formatting – 0058

 
Read and ReadLine Methods

You can obtain user input from the keyboard by using the Console.Read and Console.ReadLine methods.

 
The Read Method

Read reads the next character from the keyboard. It returns the int value –1 if there is no more input available. Otherwise it returns an int representing the character read.

 
The ReadLine Method

ReadLine reads all characters up to the end of the input line (the carriage return character). The input is returned as a string of characters. You can use the following code to read a line of text from the keyboard and display it to the screen:

 
string input = Console.ReadLine( );

Console.WriteLine(“{0}”, input);