Artikel getaggt mit ‘C#’

Oktober 28th, 2016

Solving the Shortest Path Problem (5) – Benchmarks

This article of 2012 at http://stegua.github.io/ shows, that the type of the priority queue of a shortest path solver is crucial for the solving time.
You have to agree with that, but there is another point to mention: the choice of the graph representation.
I wanted to spend some more time on the comparison of the graph libraries LEMON and BGL and so I modified some of the code and ran the following tests on it.

The code was compiled using GCC 4.8.4 with the the following switches: -O2 -m64 -std=c++11. My test machine is a laptop with an Intel 4-Core i3@2,4 Ghz. You can download the graph instances from the DIMACS site.

BGL’s Dijkstra d-ary Heap (d=4)
Boost’s Graph Library offers two variants of a Dijkstra shortest path solver implementation. A regular one dijkstra_shortest_path and a variant that does not use an internal color map of nodes (dijkstra_shortest_path_no_color_map). Both of them use by default a d-ary Heap with d=4 which is actually a quad heap queue. Unfortunately there is no easy way to change the heap in the dijkstra implementation.

There is no significant difference comparing the solving time of each of them, if you do not change the graph structure.
Using the BGL with street networks you have two flavours of a graph: the widely known adjacency_list and a representation that you should look at if you’re dealing with sparse graphs as street networks are: the compressed_sparse_row_graph.

Here are the results.

weiterlesen »

Be the first to like.

Oktober 24th, 2012

Solving the Transportation Problem (3) – MSF API in .NET

Solver Foundation in C#. Net

In order to solve the above described instance of a Transporation problem we only need a C# Console Application with a few lines of code. So start your IDE (SharpDevelop or Visual Studio [Express Edition will work either]) and create a new console application project. Then add a reference to the Microsoft.Solver.Foundation.dll under „References“. This DLL should be found after the successful installation of MSF in „C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\“. As we are using Data (DataTables, DataSets) you also need to reference „System.Data“.

The agenda for the current article is the following:

  • load the OML model into Solver Foundation Context
  • retrieve data from our sample Access Database
  • bind data to the model
  • solve the problem
  • print out minimized total result and the amount of flow of each arc

So here we go with the first section of our class.

using System;
using System.IO;
using System.Data;
using System.Data.OleDb;
using Microsoft.SolverFoundation.Services;

namespace GSharpBlog.Optimization.TP_Example 
{
	class Program
	{
        /// Gets results of a SQL query through a OLE-DB connection.
        private static DataSet getDataFromDB(string connectionStr, string query)
        {
            DataSet ds = new DataSet();
            OleDbDataAdapter adapter = new OleDbDataAdapter();
            OleDbConnection conn = new OleDbConnection(connectionStr);
            try {
                conn.Open();
                adapter.SelectCommand = new OleDbCommand(query, conn);
                adapter.Fill(ds);
                return ds;
            }
            catch (Exception ex){ throw ex; }
            finally{ conn.Close(); }
        }

First we state a helper method for retrieving data from our Access Database, that simply takes the Connection String and the SQL query and returns a DataSet. After that we can go on with the automatically generated Main() method in which all code is written for the sake of simplicity.
In the following lines of code we define the above stated OML model as string and read it into the Solver Foundation Context. Then the structure of the supply, demand and arcs table (or OD-Matrix) are defined as DataTables.

            // Access (2007) DB ConnectionString
            string connectionStr = @"Provider=Microsoft.ACE.OLEDB.12.0;Data Source=D:\tp.accdb";

			// Transportation Problem as OML model
			string strModel = @"Model[
				Parameters[Sets,Source,Sink],
				Parameters[Reals,Supply[Source],Demand[Sink],Cost[Source,Sink]],
				Decisions[Reals[0,Infinity],flow[Source,Sink],TotalCost],
				Constraints[
					TotalCost == Sum[{i,Source},{j,Sink},Cost[i,j]*flow[i,j]],
                    Foreach[{i,Source}, Sum[{j,Sink},flow[i,j]]<=Supply[i]],
					Foreach[{i,Source}, Sum[{j,Sink},flow[i,j]]>=Demand[j]]],
				Goals[Minimize[TotalCost]] ]";

			// Load OML-Model
			SolverContext context = SolverContext.GetContext();
			context.LoadModel(FileFormat.OML, new StringReader(strModel));
			context.CurrentModel.Name = "Transportation Problem";

			// Create Tables
			// Supply table
			DataTable pSupply = new DataTable();
			pSupply.Columns.Add("SupplyNode",Type.GetType("System.String"));
			pSupply.Columns.Add("Supply",Type.GetType("System.Int32"));

			// Demand table
			DataTable pDemand = new DataTable();
			pDemand.Columns.Add("DemandNode",Type.GetType("System.String"));
			pDemand.Columns.Add("Demand",Type.GetType("System.Int32"));

			// OD-Matrix
			DataTable pCost = new DataTable();
			pCost.Columns.Add("SupplyNode",Type.GetType("System.String"));
			pCost.Columns.Add("DemandNode",Type.GetType("System.String"));
			pCost.Columns.Add("Cost",Type.GetType("System.Double"));

Then data is pulled out of our Access Database and loaded into the DataTables. Now we can use the helper method getDataFromDB().

            //// Fill tables
            // 1. Fill Supply
            string query = String.Empty;
            DataSet accessDS = new DataSet();
            query = "SELECT SupplyNode, Supply FROM Supply ORDER BY SupplyNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pSupply.Rows.Add(row[0].ToString(), row[1]);
            }

            // Clear
            query = String.Empty;
            accessDS.Clear();

            // 2.Fill Demand
            query = "SELECT DemandNode, Demand FROM Demand ORDER BY DemandNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pDemand.Rows.Add(row[0].ToString(), row[1]);
            }

            // Clear
            query = String.Empty;
            accessDS.Clear();

            // 3. Fill Arcs (or OD-Matrix)
            query = "SELECT SupplyNode, DemandNode, Cost FROM Arcs ORDER BY SupplyNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pCost.Rows.Add(row[0].ToString(), row[1].ToString(), row[2]);
            }

Now we bind the data to the OML model that we have defined earlier. Microsoft Solver Foundation has an advanced binding mechanism that is pretty straight forward. With the following lines, we bind the data from our tables to the OML model: loop through the parameters in the model and simply call the method SetBinding([DataTable].AsEnumerable(), [ValueColumnName], [IDColumnName]) for each parameter.

			// Bind values from tables to parameter of the OML model
			foreach (Parameter p in context.CurrentModel.Parameters)
			{
				switch (p.Name)
					{
						case "Supply":
							p.SetBinding(pSupply.AsEnumerable(), "Supply", "SupplyNode");
							break;
						case "Demand":
							p.SetBinding(pDemand.AsEnumerable(), "Demand", "DemandNode");
							break;
						case "Cost":
                            p.SetBinding(pCost.AsEnumerable(), "Cost", "SupplyNode", "DemandNode");
							break;
					}
			}

Then we just have to call the Solve() method and fetch the result. Now we loop through the decisions of the model, look for the decision „TotalCost“ and fetch the value of the optimized result.

			// Call solver
			solution = context.Solve();

			// Fetch results: minimized total costs
			Report report = solution.GetReport();	
			double cost = 0;
			foreach (Decision desc in solution.Decisions) {
				if (desc.Name == "TotalCost")
				{
						foreach (object[] value in desc.GetValues()) {
							cost = Convert.ToDouble(value[0]);
						}
				}
			}

Because we want to know not only the optimized total costs but also the amount of flow between each supply node and demand node we have to query the solution more detailed. We get information about the source/sink-pairs about the amount of flow from MSF – but we lack the distance (or cost) between each pair. So we need to lookup the distances in the original arcs table.

// Print out optimized results
string result = String.Empty;
double totalFlow = 0.0;
foreach (Decision desc in solution.Decisions) {
	// flow as variable
	if (desc.Name == "flow")
	{
		foreach (object[] value in desc.GetValues()) {
			string source = value[1].ToString();
			string sink =  value[2].ToString();
			double flow = Convert.ToDouble(value[0]);

			// lookup km from arcs table
			DataRow[] rows = new DataRow[1];
			rows = pCost.Select("SupplyNode ='"+source+"' AND DemandNode ='"+sink+"'");
			double km = Convert.ToDouble(rows[0]["Cost"]);
			string sourceSink = String.Format("{0}_{1}", source, sink);
			if(flow != 0)
			{
				totalFlow += flow;
				result = result + "\n" + String.Format("\"{0}\";\"{1}\";\"{2}\";{3};{4}",
													   sourceSink, source, sink, flow, km);
			}
		}
		Console.WriteLine(result);
	}
}

The optimized result is 46. Our solver application prints out the following results.

Total result: 46
**********************

„S1_D1″;“S1″;“D1“;5;3
„S2_D1″;“S2″;“D1“;2;4
„S2_D2″;“S2″;“D2“;3;2
„S2_D3″;“S2″;“D3“;2;4
„S3_D3″;“S3″;“D3“;3;3

Download as IDE-Project (SharpDevelop/Visual Studio 2010)

4 Leute mögen diesen Artikel.

März 13th, 2011

G#.Viewer – Kartenfunktionen (4)

Im letzten Teil der Serie beschäftigten wir uns mit dem Laden und Anzeigen von ESRI Shapefiles im G#.Viewer. Nun werden wir die einfach zugänglichen Funktionen zum Bedienen der Kartenansicht in unseren GIS-Viewer einbauen.

Im Namespace SharpMap.Forms.MapImage befindet sich ein Enumerator, der die verfügbaren Kartenfunktionalitäten auflistet.

Die wichtigsten sind:

  • Pan (Verschieben)
  • ZoomIn
  • ZoomOut
  • Query

Da diese Tools ja bereits „out-of-the-box“ mitgeliefert werden, brauchen wir nichts anderes tun, als an jedem LabelButton in unserem ToolStrip ein Click-Event zu erzeugen und den Wechsel des aktuellen Werkzeugs zu vollziehen. Was sich etwas umständlich anhört ist mit C# und SharpDevelop ganz simpel umzusetzen:

weiterlesen »

1 andere Person mag diesen Artikel.

Februar 16th, 2011

G#.Viewer – Laden und Anzeigen eines Shapefiles (3)

Im Dritten Teil dieses Artikel über den G#.Viewer möchte ich auf das Laden und Anzeigen eines Shapefiles mit Sharpmap in C# eingehen. Nun werden wir das erste Mal C# Code nicht nur über den Designer der IDE erstellen, sondern auch selbst Hand anlegen.

Zunächst einmal definiere ich einige Felder am Anfang der Klasse, die im Folgenden verwendet werden:

public partial class frmMain : Form
{
	// Map
	private SharpMap.Map map;
	private bool isMapOpen = false;
	private SharpMap.Layers.VectorLayer vLayer;
	public int width;
	public int height;

	//TreeView
	private TreeNode rootNode;

	public frmMain()
	{
		InitializeComponent();

		//Größe der Karte = Größe des TabPages tabMap
		width = tabMap.Width;
		height = tabMap.Height;
	}

weiterlesen »

Be the first to like.

Februar 16th, 2011

G#.Viewer – GUI – Layerübersicht und OpenFileDialog (2)

Erweiterung der GUI

Im letzten Artikel habe ich einen ersten Entwurf der GUI für den G#.Viewer mit der IDE SharpDevelop angefertigt. Diesen Entwurf möchte ich nun etwas erweitern. Was noch gefehlt hat war eine Übersicht der Layer, die in den Viewer geladen werden. In dieser Übersicht sollen die Layer verschiebbar sein – also die Reihenfolge geändert werden können, in der sie im Kartenbild überlagert werden und die Sichtbarkeit verändert werden können. Außerdem braucht man die eine Layerübersicht wenn man Funktionen auf einzelne Layer beziehen möchte – beispielsweise das Zoomen auf eine bestimmte Ebene oder etwa auch das Entfernen einer Ebene aus dem Viewer.

Deshalb holen wir uns jetzt noch ein TreeView-Control hinzu. Mit Hilfe eines zusätzlichen SplitContainers bauen wir den TreeView in unseren GIS-Viewer ein. Anschließend müssen die Eigenschaften bearbeitet werden, so dass aus dem TreeView auch eine Layerübersicht werden kann. Die weniger interessanten Eigenschaften des TreeViews habe ich ausgeblendet. Ansonsten sollten die fett markierten Eigenschaften wie folgt aussehen:

weiterlesen »

Be the first to like.

Dezember 29th, 2010

G#.Viewer – GUI (1)

G#.Viewer – ein eigener GIS-Datenviewer in C#

Mit der Open Source .NET-Bibliothek SharpMap kann man eigene einfache GIS-Anwendungen mit C# relativ schnell entwickeln. In den nun folgenden Artikeln werde ich die Entwicklung eines einfachen GIS-Viewers beschreiben. Das Projekt heisst „G#.Viewer“ und soll das können: Geodaten darstellen und abfragen.

Als Entwicklungsumgebung (IDE) empfehle ich das Werkzeug SharpDevelop. Auch dies ist Open Source und ist eine profunde Alternative zu Microsoft Visual Studio C# Express Edition oder zur Vollversion Microsoft Visual Studio. In diesen Artikeln werde ich die portable Version 3.2 von SharpDevelop nutzen.

Los geht’s

Zunächst sollten wir uns mit der aktuellen Version der SharpMap-Bibliothek eindecken. Unter „Downloads“ auf der Seite von SharpMap wird man schnell fündig. Am besten läd man sich den aktuellen Quellcode (ich benutze im folgenden das ChangeSet 81947). Es werden zwar auch bereits kompilierte DLLs zum Download angeboten – dabei fehlen jedoch einige nette Sachen wie der Namespace SharpMap.UI, in dem alle nützlichen GUI-Kartenwerkzeuge für Windows Forms zu finden sind (nämlich das MapImage-Control).

Deshalb ist das Motto: selber kompilieren! Ist ja auch mit SharpDevelop ohne weiteres möglich..

weiterlesen »

1 andere Person mag diesen Artikel.

Dezember 11th, 2010

SharpMap – Open Source GIS mit C#

Ich wollte schon immer eigene Applikationen schreiben. Dabei habe ich mir an verschiedenen Programmiersprachen die Zähne ausgebissen und habe es immer wieder verworfen. Einen guten Einstieg in die Programmierung fand ich dann durch Python: es war leicht zu erlernen und man konnte schnell etwas interessantes entwickeln.

Nachdem ich mit Python und Geoprocessing etwas Erfahrung gesammelt hatte und ein Praktikum bei ESRI Deutschland absolvierte, bei dem ich unter anderem ein bisschen in die Sprache C# schnuppern durfte, wollte ich C# weiter vertiefen.  Vor allem aber wollte ich eigentlich C# mit GIS verbinden. Python spielt sich ja meist auf der Konsole ab. Was ich wollte, war eine Benutzeroberfläche! Einen eigenen GIS-Datenviewer in C# – das war mein Ziel. Nur gab es da ein Problem: .NET-Bibliotheken oder Engines für GIS-Applikationen waren nur kommerziell verfügbar. Ich wollte aber doch nur spielen und lernen – also was tun?

Nach einer längeren Recherche fand ich dann SharpMap. SharpMap ist eine Mapping-Bibilothek für C#. Sie steht unter der LGPL-Lizenz und ist damit für kommerzielle, closed-source Produkte ohne Schwierigkeiten verwendbar – was manch einer als einen Nachteil sehen möchte. (Meine Meinung dazu ist eher pragmatisch: mit der LGPL kann man sowohl Open Source bleiben, als auch Closed Source. Das ist eine Möglichkeit mehr.)

Mit SharpMap ist es relativ leicht, eigene GIS-Applikationen (oder zumindest GIS-Datenviewer) in C# zu erstellen.  Und genau das werde ich in den nächsten Beiträgen etwas vorstellen.

2 Leute mögen diesen Artikel.

Tags: , , , ,