1
\$\begingroup\$

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise while using good programming practices.

I have implemented both algorithms, DFS and BFS, to find the bridges in a graph. The code is properly working (as far as I've tested).

Important notes:

  • I've tried a simpler and more intuitive approach of the solution, I know the computational complexity of my solution is \$O(E*(V+E))\$, while others methods resolve this exercise with \$O(V+E)\$ complexity.

    • The method consists of:

      1. For every edge (u, v), do the following:
        1. Remove (u, v) from graph
        2. See if the graph remains connected (We can either use BFS or DFS)
    • The solution is designed to fit this function call:

      List<Tuple<int, int>> FindBridges(int numOfNodes, int numOfEdges, List<Tuple<int, int>> edges)
      { 
          //function body
      }
      
    • I've used string type for Node's id to be able to name them with any kind of data type and then convert them to string (ints,strings,chars...)

I'd appreciate feedback of any kind: ways to improve implementations (using this method), coding style, any refactor suggestions.

class UndirectedGraph
{
    public class Node
    {
        public string Id { get; }
        public List<string> Adjs { get; set; }
        public Node(string nodeId)
        {
            Id = nodeId;
            Adjs = new List<string>();
        }
        public Node(Node node)
        {
            Id = node.Id;
            Adjs = node.Adjs.ConvertAll(x => x);
        }

        public override string ToString()
        {
            string value = string.Format("Node id:{0} -> (", Id);
            foreach (string adj in Adjs)
            {
                value = value + adj + ",";
            }
            value += ")";
            return value;
        }
    }
    public int NumOfNodes { get; private set; }
    public Node[] AdjacencyList { get; }

    private List<Tuple<string, string>> Edges = new List<Tuple<string, string>>();

    public UndirectedGraph(int numOfNodes)
    {
        NumOfNodes = numOfNodes;
        AdjacencyList = new Node[numOfNodes];
        for (int i = 0; i < numOfNodes; i++)
        {
            AdjacencyList[i] = new Node((i+1).ToString());
        }
    }
    public UndirectedGraph(UndirectedGraph originalGraph)
    {
        NumOfNodes = originalGraph.NumOfNodes;
        AdjacencyList = originalGraph.AdjacencyList.Select(a => new Node(a)).ToArray();
        Edges = originalGraph.Edges.ConvertAll(x => Tuple.Create(x.Item1,x.Item2));
    }

    public int FindNodeIndex(string nodeId)
    {
        for (int i = 0; i < AdjacencyList.Length; i++)
        {
            if (AdjacencyList[i].Id == nodeId)
                return i;
        }
        return -1;
    }

    public Node FindNode(string nodeId)
    {
        for (int i = 0; i < AdjacencyList.Length; i++)
        {
            if (AdjacencyList[i].Id == nodeId)
                return AdjacencyList[i];
        }
        return null;
    }

    public void AddEdge(string a, string b)
    {
        Tuple<string, string> edge = Tuple.Create(a, b);
        Node aNode = FindNode(edge.Item1);
        Node bNode = FindNode(edge.Item2);
        // Avoid trying to create edges on non existing nodes
        if (!AdjacencyList.Contains(aNode) || !AdjacencyList.Contains(bNode))
            throw new Exception("The edge couldn't be created because one of the nodes is not part of the graph");

        // To avoid paralel connections
        if (Edges.Contains(edge) || Edges.Contains(Tuple.Create(b, a)))
            return;

        aNode.Adjs.Add(edge.Item2);
        bNode.Adjs.Add(edge.Item1);
        Edges.Add(edge);
    }
    public void AddEdge(Tuple<string,string> edge)
    {
        Node aNode = FindNode(edge.Item1);
        Node bNode = FindNode(edge.Item2);
        // Avoid trying to create edges on non existing nodes
        if (!AdjacencyList.Contains(aNode) || !AdjacencyList.Contains(bNode))
            throw new Exception("The edge couldn't be created because one of the nodes is not part of the graph");

        // To avoid paralel connections
        if (Edges.Contains(edge) || Edges.Contains(Tuple.Create(edge.Item2, edge.Item1)))
            return;

        aNode.Adjs.Add(edge.Item2);
        bNode.Adjs.Add(edge.Item1);
        Edges.Add(edge);
    }

    public void DeleteEdge(Tuple<string, string> edge)
    {
        if (!Edges.Contains(edge))
            return;

        Node aNode = FindNode(edge.Item1);
        Node bNode = FindNode(edge.Item2);
        aNode.Adjs.Remove(edge.Item2);
        bNode.Adjs.Remove(edge.Item1);
        Edges.Remove(edge);
    }

    public override string ToString()
    {
        List<string> nodesString = new List<string>();
        foreach (Node node in AdjacencyList)
        {
            nodesString.Add(node.ToString());
        }
        string message = string.Join('\n', nodesString);
        message += '\n';
        return message;
    }

    public List<string> DFS(string startingNode_id = null)
    {
        // Set up starting node
        Node currentNode;
        if (startingNode_id == null)
            currentNode = AdjacencyList[0];
        else
            currentNode = FindNode(startingNode_id);
        // --------------------

        // Initialize for first iteration
        Stack<string> stack = new Stack<string>(NumOfNodes);
        List<string> nodesVisited = new List<string>();
        nodesVisited.Add(currentNode.Id);
        // --------------------

        // Iteration of DFS
        while (nodesVisited.Count < NumOfNodes)
        {
            int toNode_index = IndexOfFirstNotVisited(currentNode.Adjs, nodesVisited);
            if (toNode_index >= 0)
            {
                stack.Push(currentNode.Id);
                currentNode = FindNode(currentNode.Adjs[toNode_index]);
            }
            else if (stack.Count > 0)
            {
                currentNode = FindNode(stack.Pop());
            }
            else
            {
                break;
            }

            if (!nodesVisited.Contains(currentNode.Id))
                nodesVisited.Add(currentNode.Id);
        }
        return nodesVisited;
    }

    public List<string> BFS(string startingNode_id = null)
    {   
        // Set up starting node
        Node currentNode;
        if (startingNode_id == null)
            currentNode = AdjacencyList[0];
        else
            currentNode = FindNode(startingNode_id);
        // --------------------

        // Initialize for first iteration
        List<string> nodesVisited = new List<string>();
        List<string> queue = new List<string>();
        nodesVisited.Add(currentNode.Id);
        queue.Add(currentNode.Id);
        // --------------------

        // Iterations of BFS
        while (nodesVisited.Count < NumOfNodes && queue.Count > 0)
        {
            currentNode = FindNode(queue[0]);
            queue.RemoveAt(0);
            for (int i = 0; i < currentNode.Adjs.Count; i++)
            {
                string nodeVisited = currentNode.Adjs[i];
                if (!nodesVisited.Contains(nodeVisited))
                {
                    nodesVisited.Add(nodeVisited);
                    queue.Add(nodeVisited);
                }
            }
        }
        return nodesVisited;
    }

    private int IndexOfFirstNotVisited(List<string> adjs, List<string> nodesVisited)
    {
        for (int i = 0; i < adjs.Count; i++)
        {
            if (!nodesVisited.Contains(adjs[i]))
            {
                return i;
            }
        }
        return -1;
    }
}

And the main used for testing purposes and initialization of the graph:

    class Program
{
    static void Main(string[] args)
    {
        List<Tuple<int, int>> edges1 = new List<Tuple<int, int>>() {
            Tuple.Create(1,2),
            Tuple.Create(1,3),
            Tuple.Create(2,3),
            Tuple.Create(4,3),
            Tuple.Create(4,5),
            Tuple.Create(4,6),
            Tuple.Create(5,6),
            Tuple.Create(5,7),
            Tuple.Create(6,7),
            Tuple.Create(8,7),
            Tuple.Create(8,9),
            Tuple.Create(8,10),
            Tuple.Create(9,10),
        };
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        List<Tuple<int, int>> bridges = FindBridges(10, edges1.Count, edges1);
        bridges.ForEach(Console.WriteLine);
        stopwatch.Stop();
        Console.WriteLine(stopwatch.ElapsedMilliseconds);
   }

    private static List<Tuple<int, int>> FindBridges(int numOfNodes, int numOfEdges, List<Tuple<int, int>> edges)
    {
        UndirectedGraph graph = new UndirectedGraph(numOfNodes);
        List<Tuple<int, int>> bridges = new List<Tuple<int, int>>();
        foreach (var edge in edges)
        {
            graph.AddEdge(Tuple.Create(edge.Item1.ToString(), edge.Item2.ToString()));
        }

        foreach (var edge in edges)
        {
            UndirectedGraph newGraph = new UndirectedGraph(graph);
            newGraph.DeleteEdge(Tuple.Create(edge.Item1.ToString(), edge.Item2.ToString()));
            if (newGraph.BFS().Count < numOfNodes)
                bridges.Add(edge);
        }
        return bridges;
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

The code is understandable, perhaps the naming used in some fields is quite hard to recognize for others who are seeing this code for first time.

Example Adjs (AdjacentVertices) is not intuitive, you are used to see this code and understand why you'd put everything on its place but other person who comes will spend more time getting familiar with it. Another example is Node (I think you mean Vertex) perhaps it is due the difference I perceive between Node (for trees) and Vertex (for general graphs, naturally including trees), technical vocabulary is also relevant.

Your UndirectedGraph class is an UndirectedAdjacencyList i think it is important to mention due the different Graph models that there are.

With the code.

You will want to dynamically add edges and vertices in your graph. An alternative would be:

    public List<Node> AdjacencyList { get; } //where Node is means Vertex

In addition, I think it would be better to handle Edges as a list rather than an array.

    //instead of 
    //private List<Tuple<string, string>> Edges = new List<Tuple<string, string>>();
    private List<Edge> Edges = new List<Edge>();

At last I propose you the following Idea which may make easier to manage both Vertices and Edges

    private SortedDictionary<Vertex, List<Edge>> AdjacencyList;

So that there will not be any repeated Vertex in your graph.

Thanks for reading my answer, Hope it helps

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.