|
using System;
using
System.Collections.Generic;
namespace Graph_3
{
class Program
{
static void Main(string[] args)
{
Graph graf = new Graph();
Graph graf2 = new Graph();
graf2.addVertex("0");
graf2.addVertex("1");
graf2.addVertex("2");
graf2.addVertex("3");
graf2.addVertex("4");
graf2.addVertex("5");
graf2.addVertex("6");
graf2.addEdge("0", "1", 2);
graf2.addEdge("0", "3", 1);
graf2.addEdge("1", "4", 10);
graf2.addEdge("1", "3", 3);
graf2.addEdge("2", "0", 4);
graf2.addEdge("2", "5", 5);
graf2.addEdge("3", "4", 2);
graf2.addEdge("3", "6", 4);
graf2.addEdge("3", "5", 8);
graf2.addEdge("3", "2", 2);
graf2.addEdge("4", "6", 6);
graf2.addEdge("6", "5", 1);
//--Extra for testing-----------
//graf2.addVertex("7");
//graf2.addVertex("8");
//graf2.addEdge("4", "7", 1);
//graf2.addEdge("7", "8", 1);
//graf2.addEdge("1", "8", 1);
graf.addVertex("A");
graf.addVertex("B");
graf.addVertex("C");
graf.addVertex("D");
graf.addVertex("E");
graf.addVertex("F");
graf.addVertex("G");
graf.addVertex("H");
graf.addVertex("I");
graf.addEdge("A", "B", 2); //var 2
graf.addEdge("A", "D", 5);
graf.addEdge("A", "E", 4);
graf.addEdge("B", "E", 1);
graf.addEdge("D", "G", 2);
graf.addEdge("E", "F", 3);
graf.addEdge("E", "H", 6);
graf.addEdge("F", "C", 4);
graf.addEdge("F", "H", 3);
graf.addEdge("C", "B", 3);
graf.addEdge("H", "I", 1);
graf.addEdge("I", "F", 1); // var 1,
graf.addEdge("G", "H", 1);
Console.WriteLine("------------Print
Graph 1.---------------");
graf.printGraph();
Console.WriteLine("------------Print
Graph 2.---------------");
graf2.printGraph();
Console.WriteLine("------------Breath-First
Traversal Graph 1.----------");
graf.BreathFirstTraversal("A");
graf.setAllToNotVisited();
Console.WriteLine("------------Depth-First
Traversal Graph 1.----------");
graf.DepthFirstTraversal("A");
graf.setAllToNotVisited();
Console.WriteLine("------------is ther
a connecition Graph 1.----------");
Console.WriteLine(graf.isThereAConnection("A", "H"));
graf2.setAllToNotVisited();
graf2.findShortesPathUnweightedGraph("0");
graf.setAllToNotVisited();
graf.findShortesPathUnweightedGraph("H");
Console.WriteLine("------------Dijkstra.----------");
graf.setAllToNotVisited();
graf.dijkstra("A", "H");
}
}
class Graph
{
List<Vertex> grafList = new List<Vertex>();
public void
dijkstra(String navnPaaStartVertex, String navnPaaStopVertex)
{
Console.WriteLine();
Console.WriteLine("--------------------- From " + navnPaaStartVertex + " to " + navnPaaStopVertex + "
----------------");
Console.WriteLine();
List<Vertex> priorityQueue = new List<Vertex>();
Vertex startVertex = getVertex(navnPaaStartVertex);
startVertex.visited = true;
startVertex.lengthFromStartVertex = 0;
priorityQueue.Add(startVertex);
Vertex frontVertex = startVertex;
Boolean search = true;
while (priorityQueue.Count > 0 && search)
{
//---- Prioritizing from
the Queue-----
int value = 1000000000;
//Symboliserer uendelig stort tal.
int teller = 0;
foreach (Vertex v in priorityQueue)
{
if (v.lengthFromStartVertex
< value)
{
frontVertex = priorityQueue[teller];
value =
v.lengthFromStartVertex;
}
teller++;
}
priorityQueue.Remove(frontVertex);
frontVertex.visited = true;
Console.WriteLine(" <-
Dequeue: " + frontVertex.navn + " with weight: " + frontVertex.lengthFromStartVertex +
" Queue size:" + priorityQueue.Count);
//----Prioritizing
STOP-------------------------------------------
//-----We have found the
Vertex-------------------------------------
if
(frontVertex.navn.Equals(navnPaaStopVertex))
{
Console.WriteLine(" ---------- Found: Name: " + frontVertex.navn + " Weight: " +
frontVertex.lengthFromStartVertex);
Vertex holder = frontVertex;
while
(!holder.navn.Equals(navnPaaStartVertex))
{
Console.WriteLine("backtracking: " + holder.navn);
holder =
holder.previousVertex;
}
Console.WriteLine("backtracking: " + navnPaaStartVertex);
search = false;
break;
}
//--------------------------------------
foreach (Edge e in frontVertex.edgeList)
{
int w = (int)e.weight;
if (e.vertex.visited == false) //Den er ikke
besøgt før.
{
//0 findes ikke
i køen, så skal den indsættes i prioritetskøen.
//1 findes
allerede i køen og er mindre, skal derfor overskrive.
//2 findes
allerede i køen men er større, derfor ingen overskrivning.
int tilstand = 0; //Starter med
antagelse at den ikke findes i køen.
foreach (Vertex v in priorityQueue)
{
if (v.navn.Equals(e.vertex.navn))
//Så findes den i Køen.
{
if
(frontVertex.lengthFromStartVertex + w >= v.lengthFromStartVertex)
{
tilstand = 2; //2: findes
allerede i køen men er større. Ikke overskrive.
}
else
{
tilstand = 1; //1: findes allerede i køen og er mindre, derfor
overskrive.
}
}
}
if (tilstand == 0) //Tilstand 0:
findes ikke i Køen. Indsættes i Prioritetskøen.
{
e.vertex.lengthFromStartVertex = frontVertex.lengthFromStartVertex +
w;
e.vertex.previousVertex = frontVertex;
priorityQueue.Add(e.vertex);
Console.WriteLine("
-> Enqueing: " + e.vertex.navn + "
Weight: " +
e.vertex.lengthFromStartVertex +
" Previous Vertex:
" +
e.vertex.previousVertex.navn + " Queue size:" + priorityQueue.Count);
}
else if (tilstand == 1) //Tilstand 1:
findes i køen og er mindre. Skal OVERSKRIVE.
{
Vertex v =
getVertex(e.vertex.navn);
v.lengthFromStartVertex = frontVertex.lengthFromStartVertex + w;
v.previousVertex = frontVertex;
Console.WriteLine(" *
Overskriver Vertex " + e.vertex.navn + " Weight: " + e.vertex.lengthFromStartVertex);
}
else if (tilstand == 2) //Tilstand 2:
findes i køen men er større. Laver ingenting
{
Console.WriteLine(" *
Findes allerede og har mindre eller samme vægt: " + e.vertex.navn);
}
}
else
{
Console.WriteLine(" *
Besøgt Vertex før: " + e.vertex.navn);
}
}
}
}
public void
findShortesPathUnweightedGraph(String navnPaaStartVertex)
{
Queue<Vertex> vertexQueue = new Queue<Vertex>();
Queue<Vertex> traversalOrder = new Queue<Vertex>();
Vertex startVertex = getVertex(navnPaaStartVertex);
startVertex.visited = true;
startVertex.lengthFromStartVertex = 0;
vertexQueue.Enqueue(startVertex);
traversalOrder.Enqueue(startVertex);
Vertex frontVertex;
while (vertexQueue.Count > 0)
{
frontVertex =
vertexQueue.Dequeue();
foreach (Edge e in frontVertex.edgeList)
{
if (e.vertex.visited == false)
{
e.vertex.visited = true;
e.vertex.lengthFromStartVertex = frontVertex.lengthFromStartVertex +
1;
e.vertex.previousVertex = frontVertex;
vertexQueue.Enqueue(e.vertex);
traversalOrder.Enqueue(e.vertex);
}
}
}
Console.WriteLine("-------- Shortes Path in an Unweighted
Graph-------------");
Console.WriteLine("-------- From vertex: " + navnPaaStartVertex + " to all other
rechable Vertex-------");
foreach (Vertex v in traversalOrder)
{
Console.Write("Name: " + v.navn + " Distance: " + v.lengthFromStartVertex
+ "
- ");
}
Console.WriteLine();
}
public Boolean isThereAConnection(String a, String b)
{
Boolean fundet = false;
Queue<Vertex> vertexQueue = new Queue<Vertex>();
Queue<Vertex> traversalOrder = new Queue<Vertex>();
Vertex startVertex = getVertex(a);
startVertex.visited = true;
vertexQueue.Enqueue(startVertex);
traversalOrder.Enqueue(startVertex);
Vertex frontVertex;
while (vertexQueue.Count > 0)
{
frontVertex =
vertexQueue.Dequeue();
foreach (Edge e in frontVertex.edgeList)
{
if (e.vertex.visited == false)
{
vertexQueue.Enqueue(e.vertex);
traversalOrder.Enqueue(e.vertex);
e.vertex.visited = true;
if (e.vertex.navn.Equals(b))
{
fundet = true;
}
}
}
}
return fundet;
}
public void
addVertex(string navn)
{
Vertex v = new Vertex(navn);
grafList.Add(v);
}
public void
addEdge(String VertexBegin, String VertexEnd, double edgeWeight)
{
Edge edge = new Edge();
edge.vertex =
getVertex(VertexEnd);
edge.weight = edgeWeight;
getVertex(VertexBegin).edgeList.Add(edge);
}
public Vertex getVertex(String navn)
{
Vertex gemmer = null;
foreach (Vertex vertex in
grafList)
{
if
(vertex.navn.Equals(navn))
{
gemmer = vertex;
}
}
return gemmer;
}
public void
setAllToNotVisited()
{
foreach (Vertex v in grafList)
{
v.visited = false;
}
}
public void
printGraph()
{
foreach (Vertex v in grafList)
{
foreach (Edge e in v.edgeList)
{
Console.WriteLine("From: " + v.navn + " To: " + e.vertex.navn + " weight: " + e.weight);
}
}
}
public void
BreathFirstTraversal(String navnPaaStartVertex)
{
Queue<Vertex> vertexQueue = new Queue<Vertex>();
Queue<Vertex> traversalOrder = new Queue<Vertex>();
Vertex startVertex = getVertex(navnPaaStartVertex);
startVertex.visited = true;
vertexQueue.Enqueue(startVertex);
traversalOrder.Enqueue(startVertex);
Vertex frontVertex;
while (vertexQueue.Count > 0)
{
Console.WriteLine("Items in Queue:
" +
vertexQueue.Count);
frontVertex =
vertexQueue.Dequeue();
Console.WriteLine(" <-
Dequeue: " + frontVertex.navn + " frontVertex");
foreach (Edge e in frontVertex.edgeList)
{
if (e.vertex.visited == false)
{
Console.WriteLine(" ->
Enqueue: " + e.vertex.navn);
vertexQueue.Enqueue(e.vertex);
traversalOrder.Enqueue(e.vertex);
e.vertex.visited = true;
}
}
}
Console.Write(" Traversal order: ");
foreach (Vertex v in traversalOrder)
{
Console.Write(v.navn + " ");
}
Console.WriteLine();
}
public void
DepthFirstTraversal(String navnPaaStartVertex)
{
Stack<Vertex> vertexStack = new Stack<Vertex>();
Queue<Vertex> traversalOrder = new Queue<Vertex>();
Vertex startVertex = getVertex(navnPaaStartVertex);
startVertex.visited = true;
Vertex topVertex;
vertexStack.Push(startVertex);
traversalOrder.Enqueue(startVertex);
while (vertexStack.Count > 0)
{
Console.WriteLine("Items in Stack:
" +
vertexStack.Count);
topVertex =
vertexStack.Pop();
Console.WriteLine(" <-
Pop from stack: " + topVertex.navn + " topVertex");
foreach (Edge e in topVertex.edgeList)
{
if (e.vertex.visited == false)
{
Console.WriteLine(" ->
Push to stack: " + e.vertex.navn);
vertexStack.Push(e.vertex);
traversalOrder.Enqueue(e.vertex);
e.vertex.visited = true;
}
}
}
Console.Write(" Traversal order: ");
foreach (Vertex v in traversalOrder)
{
Console.Write(v.navn + " ");
}
Console.WriteLine();
}
}
class Vertex
{
public String navn;
public List<Edge> edgeList = new List<Edge>();
public Boolean visited = false;
public int
lengthFromStartVertex = 0;
public Vertex previousVertex = null;
public Vertex(String n)
{
navn = n;
}
}
class Edge
{
public Vertex vertex;
public double weight;
}
}
|
