Insights of a Full Stack dev: July 2014

Tuesday, 1 July 2014

QuickGraph: Modelling the London Underground in C#

quickgraph.banner.png

In this example we model the London Underground, well more specifically the Victoria, Bakerloo and Circle lines.

We ask the question: what is the shortest path between Marylebone and Victoria?

This requires a change at Oxford Circus from the Bakerloo to Victoria line. Thanks to QuickGraph we can easily model the London underground as a graph.

The way this works is that we have our TrainLine and Station classes each populated with the relevant names. Each TrainLine has an ordered list of it’s Stations. We then loop through each of the TrainLines and their Stations to create a graph, adding “edges” between each of the stations. This map is then used by the library to calculate the shortest path.

	public List<TrainLine> TrainLines { get; set; }
	public List<Station> Stations { get; set; }
	public BidirectionalGraph<Station, TaggedEdge<Station, TrainLine>> Map { get; set; }

	private void InitialiseMap()
	{
	Map = new BidirectionalGraph<Station, TaggedEdge<Station, TrainLine>>(false);
	foreach (var trainLine in TrainLines)
	{
	Station previous = null;
	foreach (var station in trainLine.Stations)
	{
	if (!Map.ContainsVertex(station))
	Map.AddVertex(station);

	if (station != trainLine.Stations.First())
	{
	var edge = new TaggedEdge<Station, TrainLine>(previous, station, trainLine);
	Map.AddEdge(edge);
	}
	previous = station;
	}
	}
	}

	public IEnumerable<TaggedEdge<Station, TrainLine>> GetShortestPath(Station start, Station destination)
	{
	// a delegate that gives the distance between stations (default to 1)
	Func<TaggedEdge<Station, TrainLine>, double> stationDistances = x => 1;

	var tryGetShortestPath = Map.ShortestPathsDijkstra(stationDistances, start);

	IEnumerable<TaggedEdge<Station, TrainLine>> path;
	return tryGetShortestPath(destination, out path) ? path : null;
	}

view raw LondonUnderground hosted with ❤ by GitHub

Source: https://github.com/stevenh77/QuickGraphExample/

Simple Many to Many design

	public class TrainLine
	{
	private readonly List<Station> stations = new List<Station>();

	public IEnumerable<Station> Stations
	{
	get { return stations; }
	}

	public void AddStation(Station station)
	{
	stations.Add(station);
	station.AddTrainLine(this);
	}

	public void RemoveStation(Station station)
	{
	stations.Remove(station);
	station.RemoveTrainLine(this);
	}
	}

	public class Station
	{
	private readonly List<TrainLine> trainLines = new List<TrainLine>();

	public IEnumerable<TrainLine> TrainLines
	{
	get { return trainLines; }
	}

	public void AddTrainLine(TrainLine trainLine)
	{
	trainLines.Add(trainLine);
	}

	public void RemoveTrainLine(TrainLine trainLine)
	{
	trainLines.Remove(trainLine);
	trainLine.RemoveStation(this);
	}
	}