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.

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

}

}

}