From unknown CodePlex user on Tuesday, 28 September 2010 01:53:20

I am trying to use Tarjan Offfline Least Common Ancestor Algorithm , but a KeyNotFoundException is occurring. It seem that it search the root node in a graph made of the 2 vertex that are present in the pair.

Program.cs

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

namespace QuickGraphTest
{
    class Program
    {
        static void Main(string[] args)
        {
            /// <summary>
            /// Current revision graph
            /// </summary>
            AdjacencyGraph<Entity, Edge<Entity>> graph = new AdjacencyGraph<Entity, Edge<Entity>>();

            Entity root = new Entity() { Value = "Root" };
            Entity node1 = new Entity() { Value = "Node1" };
            Entity node2 = new Entity() { Value = "Node2" };

            graph.AddVertex(root);
            graph.AddVertex(node1);
            graph.AddVertex(node2);
            graph.AddEdge(new Edge<Entity>(root, node1));
            graph.AddEdge(new Edge<Entity>(root, node2));

            var pairs=new List<SEquatableEdge<Entity>>(){};
            pairs.Add(new SEquatableEdge<Entity>(node1,node2));

            graph.OfflineLeastCommonAncestorTarjan(root,pairs);
        }

        public class Entity
        {
            public string Value { get; set; }
        }
    }
}

TarjanOfflineLeastCommonAncestorAlgorithm.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph.Collections;
using QuickGraph.Algorithms.Search;
using System.Diagnostics.Contracts;
using QuickGraph.Algorithms.Services;

namespace QuickGraph.Algorithms
{
    /// <summary>
    /// Offline least common ancestor in a rooted tre
    /// </summary>
    /// <remarks>
    /// Reference:
    /// Gabow, H. N. and Tarjan, R. E. 1983. A linear-time algorithm for a special case 
    /// of disjoint set union. In Proceedings of the Fifteenth Annual ACM Symposium 
    /// on theory of Computing STOC '83. ACM, New York, NY, 246-251. 
    /// DOI= http://doi.acm.org/10.1145/800061.808753 
    /// </remarks>
    /// <typeparam name="TVertex">type of the vertices</typeparam>
    /// <typeparam name="TEdge">type of the edges</typeparam>
    public sealed class TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge>
        : RootedAlgorithmBase<TVertex , IVertexListGraph<TVertex, TEdge>>
        where TEdge : IEdge<TVertex>
    {
        private SEquatableEdge<TVertex>[] pairs;
        private readonly Dictionary<SEquatableEdge<TVertex>, TVertex> ancestors =
            new Dictionary<SEquatableEdge<TVertex>, TVertex>();

        public TarjanOfflineLeastCommonAncestorAlgorithm(
            IVertexListGraph<TVertex, TEdge> visitedGraph)
            : this(null, visitedGraph)
        { }

        public TarjanOfflineLeastCommonAncestorAlgorithm(
            IAlgorithmComponent host,
            IVertexListGraph<TVertex, TEdge> visitedGraph)
            : base(host, visitedGraph)
        { }

        public bool TryGetVertexPairs(out IEnumerable<SEquatableEdge<TVertex>> pairs)
        {
            pairs = this.pairs;
            return pairs!=null;
        }

        public void SetVertexPairs(IEnumerable<SEquatableEdge<TVertex>> pairs)
        {
            Contract.Requires(pairs != null);

            this.pairs = new List<SEquatableEdge<TVertex>>(pairs).ToArray();
        }

        public void Compute(TVertex root, IEnumerable<SEquatableEdge<TVertex>> pairs)
        {
            Contract.Requires(root != null);
            Contract.Requires(pairs != null);

            this.pairs = Enumerable.ToArray(pairs);
            this.Compute(root);
        }

        public IDictionary<SEquatableEdge<TVertex>, TVertex> Ancestors
        {
            get { return this.ancestors; }
        }

        protected override void Initialize()
        {
            base.Initialize();
            this.ancestors.Clear();
        }

        protected override void InternalCompute()
        {
            var cancelManager = this.Services.CancelManager;

            TVertex root;
            if (!this.TryGetRootVertex(out root))
                throw new InvalidOperationException("root vertex not set");
            if (this.pairs == null)
                throw new InvalidProgramException("pairs not set");

            var gpair = GraphExtensions.ToAdjacencyGraph(this.pairs);
            var disjointSet = new ForestDisjointSet<TVertex>();
            var vancestors = new Dictionary<TVertex, TVertex>();
            var dfs = new DepthFirstSearchAlgorithm<TVertex, TEdge>(this, this.VisitedGraph, new Dictionary<TVertex, GraphColor>(this.VisitedGraph.VertexCount));

            dfs.InitializeVertex += v => disjointSet.MakeSet(v);
            dfs.DiscoverVertex += v => vancestors[v] = v;
            dfs.TreeEdge += edge =>
                {
                    disjointSet.Union(edge.Source, edge.Target);
                    vancestors[disjointSet.FindSet(edge.Source)] = edge.Source;
                };

            dfs.FinishVertex += v =>
                {
                    IEnumerable<SEquatableEdge<TVertex>> edges;
                    if (gpair.TryGetOutEdges(v, out edges))
                    {
                        foreach (var e in edges)
                        {
                            if (dfs.VertexColors[e.Target] == GraphColor.Black)
                                this.ancestors[EdgeExtensions.ToVertexPair<TVertex, SEquatableEdge<TVertex>>(e)] = vancestors[disjointSet.FindSet(e.Target)];
                        }
                    }
                };

            // go!
            dfs.Compute(root);
        }
    }
}

FubarDevelopment / QuickGraph

CP-18847: KeyNotFoundException with OfflineLeastCommonAncestorTarjan Algorithm #105

Program.cs

TarjanOfflineLeastCommonAncestorAlgorithm.cs