I am studying graphs and I am trying to make a library in C# for myself and anyone else interested, that is didactic and simple, so I can remember how to solve common problems.
I would like to improve it.
How can I improve, for example, the DFS
, complete the Prim's algorithm
and implement the Kruskal's and Dijkstra's algorithms ?
Create an interface that can be derived for representing different kinds of graphs, like Undirect and Direct Graph, for example.
public interface IGraph
{
void InsertDirectEdge(int edgeAKey, int edgeBKey,int weight = 0);
void IsertNewVertex(int vertexKey);
bool ExistKey(int vertexKey);
Vertex InitializeDFS(int vertexKeyToFind);
bool MakeItBipartite();
Vertex DFS(Vertex root, int vertexKeyToFind);
void FindNumberOfConnectedComponents();
void BFS(int startVertexKey);
Vertex InitialiazeBFS(int vertexKeyToFind);
bool IsVisited(Vertex v);
Vertex MarkVertexAsVisited(Vertex v);
Vertex GetFirstElementOfTheList(int findKey);
void InsertUndirectedEdge(int vertexAKey, int vertexBKey, int Weight = 0);
GraphDirect PrimAlgorithm();
Vertex FindByKey(int vertexKey);
}
Created a direct graph, with a Dictionary<int,Vertex>
to represent a Graph Adjacency List
, where the key
is an integer.
public class GraphDirect : IGraph
{
private Dictionary<int,Vertex> Vertices { get; set; }
//For use on the DFS to "break" the recursion.
private bool finished;
public GraphDirect()
{
Vertices = new Dictionary<int, Vertex>();
}
//Initialize all vertices with Unvisited value.
private void InitializeVertices()
{
foreach(int key in this.Vertices.Keys)
{
this.Vertices[key].Status = State.UnVisited;
}
}
}
This part is used for Depth-First-Search and probably should be changed to be more elegant and efficient. It should execute in linear time O(|E|)
, where E
is the total number of edges. To call DFS
in this case you start calling InitializeDFS(TheKeyYouWantToFind)
.
public Vertex InitializeDFS(int vertexKeyToFind)
{
if (this.Vertices.Count == 0)
return null;
InitializeVertices();
finished = false;
return this.DFS(Vertices.First().Value, vertexKeyToFind);
}
private void ProccessVertex(int vertexBeenProcessed, int vertexKeyToFind)
{
if (vertexBeenProcessed == vertexKeyToFind)
finished = true;
else
finished = false;
}
public Vertex DFS(Vertex root, int vertexKeyToFind)
{
Console.WriteLine("Root = {0}", root.Key);
ProccessVertex(root.Key, vertexKeyToFind);
if (finished)
return root;
this.Vertices[root.Key].Status = State.Visited;
while (root.Next != null)
{
if (Vertices[root.Next.Key].Status == State.UnVisited)
{
root.Next.Status = State.Processed;
Console.WriteLine("Root.Next = {0}", root.Key);
DFS(Vertices[root.Next.Key], vertexKeyToFind);
}
root = root.Next;
}
if (!finished)
return null;
else
return root;
}
This part is to check if the graph is bipartite or not.
void InitializeVerticesColors()
{
foreach(Vertex v in this.Vertices.Values)
{
v.Color = Color.Uncolored;
}
}
//If is bipartite
public bool MakeItBipartite()
{
InitializeVerticesColors();
InitializeVertices();
return this.BFS2Colors(this.Vertices.First().Key);
}
private bool BFS2Colors(int startVertexKey)
{
if (this.Vertices.Count == 0)
return true;
int white = 0;
Queue<Vertex> Q = new Queue<Vertex>();
Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);
this.Vertices[startVertexKey].Color = Color.White;
Console.WriteLine("White");
this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));
while (Q.Count != 0)
{
white = (this.Vertices[Q.Peek().Key].Color == Color.White) ? 1 : 0;
List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());
foreach (Vertex v in children)
{
if (this.Vertices[v.Key].Status == State.UnVisited)
{
Console.WriteLine("Passed to {0}", v.Key);
if (white == 1)
this.Vertices[v.Key].Color = Color.Black;
else
this.Vertices[v.Key].Color = Color.White;
if (this.Vertices[v.Key].Color == Color.White)
Console.WriteLine("Child color white");
else if (this.Vertices[v.Key].Color == Color.Black)
Console.WriteLine("Child Color Black");
this.Vertices[v.Key].Status = State.Visited;
Q.Enqueue(this.Vertices[v.Key]);
}
}
}
return true;
}
This part if for checking the number of Connected Components of a Graph.
public void FindNumberOfConnectedComponents()
{
int c = 0;
InitializeVertices();
foreach (Vertex v in this.Vertices.Values)
{
if (v.Status == State.UnVisited)
{
//Counting the number of components
c++;
Console.WriteLine("Component number {0}", c);
this.BFS(v.Key);
}
}
}
This is to do a Breath-First-Search (BFS) looking for a key.
public void BFS(int startVertexKey)
{
if (this.Vertices.Count == 0)
return;
Queue<Vertex> Q = new Queue<Vertex>();
Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);
this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));
while (Q.Count != 0)
{
List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());
foreach (Vertex v in children)
{
if (this.Vertices[v.Key].Status == State.UnVisited)
{
Console.WriteLine("Passed to {0}", v.Key);
this.Vertices[v.Key].Status = State.Visited;
Q.Enqueue(this.Vertices[v.Key]);
}
}
}
}
private List<Vertex> GetChildrenOfVertex(Vertex headVertex)
{
List<Vertex> vertexes = new List<Vertex>();
Vertex v = headVertex.Next;
while (v != null)
{
vertexes.Add(v);
v = v.Next;
}
return vertexes;
}
public Vertex InitialiazeBFS(int vertexKeyToFind)
{
InitializeVertices();
return BFS(this.Vertices.First().Key,vertexKeyToFind);
}
private Vertex BFS(int startVertexKey, int vertexKeyToFind)
{
if (this.Vertices.Count == 0)
return null;
//Starting from the first element
Queue<Vertex> Q = new Queue<Vertex>();
Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);
this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));
while (Q.Count != 0)
{
List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());
foreach (Vertex v in children)
{
if (this.Vertices[v.Key].Status == State.UnVisited)
{
Console.WriteLine("Passed to {0}", v.Key);
if (v.Key == vertexKeyToFind)
return v;
this.Vertices[v.Key].Status = State.Visited;
Q.Enqueue(this.Vertices[v.Key]);
}
}
}
return null;
}
public bool IsVisited(Vertex v)
{
if (v == null)
return false;
return this.Vertices[v.Key].Status == State.Visited;
}
public Vertex MarkVertexAsVisited(Vertex v)
{
if (v == null) return null;
this.Vertices[v.Key].Status = State.Visited;
return this.Vertices[v.Key];
}
public Vertex GetFirstElementOfTheList(int findKey)
{
if (this.Vertices.ContainsKey(findKey))
return this.Vertices[findKey];
return null;
}
public bool ExistKey(int vertexKey)
{
if (this.FindByKey(vertexKey) == null)
return false;
else
return true;
}
These are operations used to insert new vertices
, undirect edges
and direct edges
. Also find an element on the graph by it's key
, return null
if it doesn't exist on the graph.
public void IsertNewVertex(int vertexKey)
{
if (!this.ExistKey(vertexKey))
{
this.Vertices.Add(vertexKey, new Vertex(vertexKey));
}
}
public void InsertUndirectedEdge(int vertexAKey, int vertexBKey, int Weight = 0)
{
this.InsertDirectEdge(vertexAKey, vertexBKey, Weight);
this.InsertDirectEdge(vertexBKey, vertexAKey, Weight);
}
public void InsertDirectEdge(int vertexAKey, int vertexBKey, int weightEdge = 0)
{
//Create the vertex A on the vertex list
if (!this.ExistKey(vertexAKey))
{
this.IsertNewVertex(vertexAKey);
}
//Create the vertex B on the vertex list
if (!this.ExistKey(vertexBKey))
{
this.IsertNewVertex(vertexBKey);
}
//Add the vertex B on the vertex A position on the Dictionary, as the second element of the list
Vertex vertexB = new Vertex(vertexBKey);
vertexB.Weight = weightEdge;
vertexB.Next = this.Vertices[vertexAKey].Next;
this.Vertices[vertexAKey].Next = vertexB;
}
public Vertex FindByKey(int vertexKey)
{
if (this.Vertices.ContainsKey(vertexKey))
return this.Vertices[vertexKey];
return null;
}
This is a Prim's algorithm used to find the minimum spanning tree of a Graph using Greedy algorithm, and it is still incomplete.
public GraphDirect PrimAlgorithm()
{
if (this.Vertices.First().Value == null)
return null;
GraphDirect SpanningTree = new GraphDirect();
Vertex v = this.Vertices.First().Value;
v.SpanningTreeVertex = true;
Console.WriteLine("v.key = {0}",v.Key);
SpanningTree.IsertNewVertex(v.Key);
Queue<Vertex> Q = new Queue<Vertex>();
Q.Enqueue(v);
int min = int.MaxValue;
Vertex minVertex = null;
while (Q.Count != 0)
{
Vertex parent = Q.Dequeue();
List<Vertex> children = GetChildrenOfVertex(parent);
foreach (Vertex vet in children)
{
if (vet.Status == State.UnVisited && vet.Weight < min)
{
min = vet.Weight;
minVertex = vet;
}
}
//TODO:
minVertex.Status = State.Visited;
SpanningTree.InsertUndirectedEdge(parent.Key, minVertex.Key, min);
}
return SpanningTree;
}
Created the states of the graph for DFS
, and Colors for checking if a graph is bipartite
or not, also the Vertex
is represented bellow, where the Key
is the integer that uniquely identify it, and attached to the class you can add any attributes like Value
for example.
public enum State { Visited = 0, UnVisited = 1, Processed = 2 }
public enum Color { White = 0, Black = 1, Uncolored = 2 }
public class Vertex
{
public int Key;
public int Value;
public State Status = State.UnVisited;
public Vertex Next;
public Color Color = Color.Uncolored;
public bool SpanningTreeVertex = false;
public int Weight = 0;
public Vertex(int key)
{
this.Key = key;
this.Value = 0;
}
public Vertex(int key, int value)
{
this.Key = key;
this.Value = value;
}
}
An example showing how to use the GraphDirect
class on a Console Application:
public class Start
{
public static void Main(){
GraphDirect gDirect = new GraphDirect();
gDirect.InsertDirectEdge(2, 7, 2);
gDirect.InsertDirectEdge(7, 4, 4);
gDirect.InsertDirectEdge(4, 6, 5);
gDirect.InsertDirectEdge(8, 3, 5);
gDirect.InsertDirectEdge(6, 2, 4);
}
}