Graph Adjacency List C#

Question

I am fairly new to programming in C# and am currently attempting to write the generic classes Graph and GraphNode which I have included below. I understand the logistics behind the methods IsAdjacent and GetNodeByID however I am not to sure how to code these correctly in C# so I have included a small bit of psuedo code in these methods. This however is not the case with the AddEdge method. If possible could you provide me with a solution to these three methods.

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Graph
{
    public class GraphNode<T>
    {
        private T id; //data stored in graph
        private LinkedList<T> adjList; //adjacency list
        //constructor
        public GraphNode(T id)
        {
            this.id = id;
            adjList = new LinkedList<T>();
        }
        //add an edge from this node : add to to the adjacency list
        public void AddEdge(GraphNode<T> to)
        {
            adjList.AddFirst(to.ID);
        }
        //set and get for ID – data stored in graph
        public T ID
        {
            set { id = value; }
            get { return id; }
        }
        //returns adjacency list – useful for traversal methods
        public LinkedList<T> GetAdjList()
        {
            return adjList;
        }
    }
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Graph
{
    public class Graph<T> where T : IComparable
    {
        //list of GraphNodes in this graph
        private LinkedList<GraphNode<T>> nodes;
        //constructor - set nodes to new empty list
        public Graph()
        {
            nodes = new LinkedList<GraphNode<T>>();
        }
        //only return true if the graph’s list of nodes is empty
        public bool IsEmptyGraph()
        {
            return nodes.Count == 0;
        }
        //Search through list of nodes for node
        //Node will be a new graphnode with the
        // containing the ID to be search for
        public bool ContainsGraph(GraphNode<T> node)
        {
            //search based on ID 
            foreach (GraphNode<T> n in nodes)
            {
                if (n.ID.CompareTo(node.ID) == 0)
                    return true;
            }
            return false;
        }
        //find from in list of nodes and search its adjList for to
        public bool IsAdjacent(GraphNode<T> from, GraphNode<T> to)
        {
            foreach(GraphNode<T> n in nodes)
            {
                if (n.ID  same as from.ID)
                    {   if (from.AdjList contains to.ID)
                    return true;  
                     }
                return false;
            }   
        }


        //add a new graphNode to list of nodes
        public void AddNode(T id)
        {
            GraphNode<T> n = new GraphNode<T>(id);
            nodes.AddFirst(n);
       }


        //Search through list of nodes for node with this ID
        public GraphNode<T> GetNodeByID(T id)
       {
        foreach( GraphNode<T> n in nodes )
         {
          if (id = n.ID)
            {
              return n;
            }
         }     
        return null;
       }

        //find from in list of nodes (look at other methods)
        //and call graphNode method to add an edge to to
        //think about validation here
        public void AddEdge(T from, T to)
        {
        }
        //perform a DFS traversal starting at startID, leaving a list
        //of visitied ID’s in the visited list.
    }
}

Many Thanks

Have you tried any code so far? If so, what did you try and in what way did it not work? — Tripp Kinetics, Feb 26 '15 at 15:09
What exactly does not work with your current implementation? — Codor, Feb 26 '15 at 15:13
It's not that it doesn't work at the moment it is just that I am not sure how to code these three methods, the rest of the code works. — midgitads26, Feb 26 '15 at 15:18

score 1 · Answer 1 · edited May 23 '17 at 12:12

A couple of notes:

A few of your methods take the node "ID" rather than the node itself. Wouldn't it be easier just to use the node?
Any good reason for using LinkedList rather than List for most of these items? There's an SO discussion about this here and it's not obvious what LinkedList brings to your implementation.

With adjacency lists, your AddEdge function needs to take two inputs: your source node, and destination node, and add them to each others' adjacency lists. You already have a function AddEdge in your Node class which adds a vertex to its adjacency list. So, your code will look something like this:

public void AddEdge(GraphNode source, GraphNode destination)
{
    source.AddEdge(destination);
    destination.AddEdge(source);
}

For isAdjacent, I'm not clear on why you need to search the entire list of nodes. You just need to check that one node is in the others' adjacency list (which should imply vice versa assuming it's coded correctly):

public bool isAdjacent(GraphNode source, GraphNode destination)
{
    if (source.AdjList.Contains(destination))
    {
        return true;
    }
    return false;
}

I haven't answered your question about GetNodeByID because of my above note - I'm not sure why it's done by ID rather than by the node itself. However, I don't see a problem with your method if you really want to do it with IDs (although it should be if (id = n.ID) rather than if (id = n.ID)).

Graph Adjacency List C#

1 Answers1