CODEWITHSUNDEEP
algorithmdata-structurescomputer-sciencegraph-algorithmundirected-graph
user3574076
user3574076

Reputation: 731

Finding all bridge edges in an undirected graph? (Code not working)

I am learning about bridges in graphs.

I have the following C# code (also available in a fiddle - https://dotnetfiddle.net/XQEEdy):

using System;
using System.Collections.Generic;

public class Program
{
    public class Graph
    {
        private int[,] adjMatrix;

        public Graph(int vertices)
        {
            adjMatrix = new int[vertices, vertices];
        }

        public int[,] AdjMatrix
        {
            get
            {
                return adjMatrix;
            }
        }

        public void AddEdge(int source, int destination)
        {
            adjMatrix[source, destination] = 1;
            adjMatrix[destination, source] = 1;
        }
    }

    public static HashSet<Tuple<int, int>> Bridges(Graph graph)
    {
        var visited = new HashSet<int>();
        var bridges = new HashSet<Tuple<int, int>>();
        var ids = new Dictionary<int, int>();
        var lowLinkValues = new Dictionary<int, int>();
        var parent = -1;
        var id = 0;

        for (int i = 0; i < graph.AdjMatrix.GetLength(0); i++)
        {
            if (visited.Contains(i))
            {
                continue;
            }

            Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, graph.AdjMatrix);
        }

        return bridges;
    }

    private static void Dfs(
        int vertex,
        int parent,
        int id,
        HashSet<Tuple<int, int>> bridges,
        Dictionary<int, int> ids,
        Dictionary<int, int> lowLinkValues,
        HashSet<int> visited,
        int[,] adjMatrix)
    {
        visited.Add(vertex);
        ids.Add(vertex, id);
        lowLinkValues.Add(vertex, id);
        id++;

        for (int i = 0; i < adjMatrix.GetLength(0); i++)
        {
            if (parent == i)
            {
                continue;
            }

            if (!visited.Contains(i))
            {
                parent = vertex;
                Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, adjMatrix);

                if (ids[vertex] < lowLinkValues[i])
                {
                    bridges.Add(Tuple.Create(vertex, i));
                }
                else
                {
                    lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], lowLinkValues[i]);
                }
            }
            else
            {
                lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], ids[i]);
            }
        }
    }

    public static void Main()
    {
        // Adjacency Matrix:
        var g = new Graph(11);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(0, 3);
        g.AddEdge(0, 4);
        g.AddEdge(4, 2);
        g.AddEdge(3, 5);
        g.AddEdge(4, 6);
        g.AddEdge(6, 3);
        g.AddEdge(6, 7);
        g.AddEdge(6, 8);
        g.AddEdge(7, 9);
        g.AddEdge(9, 10);
        g.AddEdge(8, 10);

        // bridges should be: 0--1, 3--5
        // but bridges collection is empty
        var bridges = Bridges(g);

        foreach (var bridge in bridges)
        {
            Console.WriteLine(bridge.Item1);
            Console.WriteLine(bridge.Item2);
            Console.WriteLine("\n");
        }
    }
}

I have compared the code to: https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/BridgesAdjacencyList.java

I do not see any real differences, but I am still getting nothing returned. Drawing the graph out, it looks like edge(0,1) and edge(3,5) should be bridges - as removing the edges would mean 1 & 5 would be disconnected from the graph.

Similarly, if I use the same test case from the github link I also get no bridges returned.

I am clearly missing something, but I've not been able to pick up what it might be. Does anyone see what the issue with my code is?

Upvotes: 1

Views: 461

Answers (1)

Welbog
Welbog

Reputation: 60418

The problem appears to be that you've not implemented an actual depth-first search, though that appears to be your intention with the name Dfs. A depth-first search starts at some vertex and follows all edges from that vertex in a depth-first manner (follows all edges from the first child before looking at the next child).

Your algorithm, however, looks at every node and simply defines the parent as the current node, so it's not really searching, it's just looking at every node in numerical order. A simplified version of your code (in pseudocode):

Dfs(Vertex current):
  mark current as visited
  for each Vertex v in the graph:
    if v is not visited: 
      Dfs(v)

Note there's no relationship between the vertex called "current" and the vertices examined from the graph. Instead, the algorithm should be more like this:

Dfs(Vertex current, Vertex parent):
  mark current as visited
  for each Vertex v in the graph:
    if v is not visited: 
      if v shares an edge with current:
        Dfs(v)

I'll leave it as an exercise for you to figure out how to patch your algorithm to fix this issue. There may be other issues as well. I stopped once I found the first issue.

Upvotes: 1

Related Questions