Skip to content

Instantly share code, notes, and snippets.

@SourceCode
Created October 1, 2017 22:28
Show Gist options
  • Save SourceCode/d3b3346329a20e8f693d0019f5b99b5d to your computer and use it in GitHub Desktop.
Save SourceCode/d3b3346329a20e8f693d0019f5b99b5d to your computer and use it in GitHub Desktop.
Graph, GraphNode, NodeList, and Node for Graph data structure in C#
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
// This is based on the graph implementation found at: https://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx
// But is updated to work in the latest C# and Net Core
namespace Graph1
{
class Program
{
static void Main(string[] args)
{
Graph<string> web = new Graph<string>();
web.AddNode("Privacy.aspx");
web.AddNode("People.aspx");
web.AddNode("About.aspx");
web.AddNode("Index.aspx");
web.AddNode("Products.aspx");
web.AddNode("Contact.aspx");
var people = new GraphNode<string>("People.aspx");
var privacy = new GraphNode<string>("Privacy.aspx");
var index = new GraphNode<string>("Index.aspx");
var about = new GraphNode<string>("About.aspx");
var contact = new GraphNode<string>("Contact.aspx");
var products = new GraphNode<string>("Products.aspx");
web.AddDirectedEdge(people, privacy, 1); // People -> Privacy
web.AddDirectedEdge(privacy, index, 1); // Privacy -> Index
web.AddDirectedEdge(privacy, about, 1); // Privacy -> About
web.AddDirectedEdge(about, privacy, 1); // About -> Privacy
web.AddDirectedEdge(about, people, 1); // About -> People
web.AddDirectedEdge(about, contact, 1); // About -> Contact
web.AddDirectedEdge(index, about, 1); // Index -> About
web.AddDirectedEdge(index, contact, 1); // Index -> Contacts
web.AddDirectedEdge(index, products, 1); // Index -> Products
web.AddDirectedEdge(products, index, 1); // Products -> Index
web.AddDirectedEdge(products, people, 1);// Products -> People
Console.WriteLine("C# Graph Example - Updated for latest C# Net Core");
}
}
public class Node<T>
{
private T data;
private NodeList<T> neighbors = null;
public Node() { }
public Node(T data) : this(data, null) { }
public Node(T data, NodeList<T> neighbors)
{
this.data = data;
this.neighbors = neighbors;
}
public T Value { get; set; }
protected NodeList<T> Neighbors { get; set; }
}
public class NodeList<T> : Collection<Node<T>>
{
public NodeList() : base() { }
public NodeList(int initialSize)
{
for (int i = 0; i < initialSize; i++)
{
base.Items.Add(default(Node<T>));
}
}
public Node<T> FindByValue(T value)
{
foreach(Node<T> node in Items)
{
if (node.Value.Equals(value))
{
return node;
}
}
return null;
}
}
public class GraphNode<T> : Node<T>
{
private List<int> costs;
public GraphNode() : base() { }
public GraphNode(T value) : base(value) { }
public GraphNode(T value, NodeList<T> neighbors) : base(value, neighbors) { }
new public NodeList<T> Neighbors
{
get
{
if (base.Neighbors == null)
base.Neighbors = new NodeList<T>();
return base.Neighbors;
}
}
public List<int> Costs
{
get
{
if (costs == null)
costs = new List<int>();
return costs;
}
}
}
public class Graph<T> : IEnumerable<Node<T>>
{
private NodeList<T> nodeSet;
public NodeList<T> Nodes { get; }
public Graph() : this(null) { }
public Graph(NodeList<T> nodeSet)
{
if (nodeSet == null)
{
this.nodeSet = new NodeList<T>();
} else {
this.nodeSet = nodeSet;
}
}
public void AddNode(GraphNode<T> node)
{
nodeSet.Add(node);
}
public void AddNode(T value)
{
nodeSet.Add(new GraphNode<T>(value));
}
public void AddDirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
{
from.Neighbors.Add(to);
from.Costs.Add(cost);
}
public void AddUndirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
{
AddDirectedEdge(from, to, cost); //This was duplicated so just call the existing value
to.Neighbors.Add(to);
to.Costs.Add(cost);
}
public bool contains(T value)
{
return nodeSet.FindByValue(value) != null;
}
public bool Remove(T value)
{
// Remove node from nodeset
GraphNode<T> nodeToRemove = (GraphNode<T>)nodeSet.FindByValue(value);
if (nodeToRemove == null)
{
// wasnt found
return false;
}
// was found
nodeSet.Remove(nodeToRemove);
// enumerate through each node in nodeSet, removing edges to this node
foreach(GraphNode<T> gnode in nodeSet)
{
int index = gnode.Neighbors.IndexOf(nodeToRemove);
if (index != -1)
{
gnode.Neighbors.RemoveAt(index);
gnode.Costs.RemoveAt(index);
}
}
return true;
}
public int Count
{
get { return nodeSet.Count; }
}
public IEnumerator<Node<T>> GetEnumerator()
{
return nodeSet.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
@91vikas
Copy link

91vikas commented Apr 11, 2020

How do you determine which cost is for which neighbour?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment