QuikGraph icon indicating copy to clipboard operation
QuikGraph copied to clipboard

Properly implement the Bron Kerbosh Maximum Clique algorithm

Open KeRNeLith opened this issue 5 years ago • 0 comments

Implement the Bron Kerbosh Maximum Clique algorithm and unit test it.

The library had a draft of implementation for this algorithm, here is the basis:

using System.Collections.Generic;
using JetBrains.Annotations;
using QuikGraph.Algorithms.Services;

namespace QuikGraph.Algorithms.Cliques
{
    public class BronKerboshMaximumCliqueAlgorithm<TVertex, TEdge> : MaximumCliqueAlgorithmBase<TVertex, TEdge>
        where TEdge : IEdge<TVertex>
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="BronKerboshMaximumCliqueAlgorithm{TVertex,TEdge}"/> class.
        /// </summary>
        /// <param name="host">Host to use if set, otherwise use this reference.</param>
        /// <param name="visitedGraph">Graph to visit.</param>
        protected BronKerboshMaximumCliqueAlgorithm(
            [CanBeNull] IAlgorithmComponent host,
            [NotNull] IUndirectedGraph<TVertex, TEdge> visitedGraph)
            : base(host, visitedGraph)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BronKerboshMaximumCliqueAlgorithm{TVertex,TEdge}"/> class.
        /// </summary>
        /// <param name="visitedGraph">Graph to visit.</param>
        protected BronKerboshMaximumCliqueAlgorithm(
            [NotNull] IUndirectedGraph<TVertex, TEdge> visitedGraph)
            : base(visitedGraph)
        {
        }

        #region AlgorithmBase<TGraph>

        /// <inheritdoc />
        protected override void InternalCompute()
        {
            // the currently growing clique;
            var R = new List<TVertex>();
            // prospective nodes which are connected to all nodes in R 
            // and using which R can be expanded
            var P = new List<TVertex>();
            // nodes already processed i.e. nodes which were previously in P 
            // and hence all maximal cliques containing them have already been reported
            var X = new List<TVertex>();

            // An important invariant is that all nodes which are connected to every node 
            // of R are either in P or X.

        }

        #endregion
    }
}

KeRNeLith avatar Feb 08 '20 15:02 KeRNeLith