Class TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge>

Offline least common ancestor in a rooted tree.

Inheritance
System.Object
AlgorithmBase<IVertexListGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IVertexListGraph<TVertex, TEdge>>
TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms
Assembly: QuikGraph.dll
Syntax
public sealed class TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge> : RootedAlgorithmBase<TVertex, IVertexListGraph<TVertex, TEdge>>, IAlgorithm<IVertexListGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.
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

Constructors

| Improve this Doc View Source

TarjanOfflineLeastCommonAncestorAlgorithm(IAlgorithmComponent, IVertexListGraph<TVertex, TEdge>)

Initializes a new instance of the TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge> class.

Declaration
public TarjanOfflineLeastCommonAncestorAlgorithm(IAlgorithmComponent host, IVertexListGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IVertexListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
| Improve this Doc View Source

TarjanOfflineLeastCommonAncestorAlgorithm(IVertexListGraph<TVertex, TEdge>)

Initializes a new instance of the TarjanOfflineLeastCommonAncestorAlgorithm<TVertex, TEdge> class.

Declaration
public TarjanOfflineLeastCommonAncestorAlgorithm(IVertexListGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IVertexListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.

Properties

| Improve this Doc View Source

Ancestors

Ancestors of vertices pairs.

Declaration
public IDictionary<SEquatableEdge<TVertex>, TVertex> Ancestors { get; }
Property Value
Type Description
System.Collections.Generic.IDictionary<SEquatableEdge<TVertex>, TVertex>

Methods

| Improve this Doc View Source

Compute(TVertex, IEnumerable<SEquatableEdge<TVertex>>)

Runs the algorithm with the given root vertex and set of vertices pairs.

Declaration
public void Compute(TVertex root, IEnumerable<SEquatableEdge<TVertex>> pairs)
Parameters
Type Name Description
TVertex root

Root vertex.
System.Collections.Generic.IEnumerable<SEquatableEdge<TVertex>> pairs

Vertices pairs.
Exceptions
Type Condition
System.ArgumentNullException

root is null.
System.ArgumentNullException

pairs is null.
System.ArgumentException

root is not part of VisitedGraph.
System.ArgumentException

pairs is empty or any vertex from pairs is not part of VisitedGraph.
| Improve this Doc View Source

Initialize()

Called on algorithm initialization step.

Declaration
protected override void Initialize()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IVertexListGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IVertexListGraph<TVertex, TEdge>>.InternalCompute()
| Improve this Doc View Source

SetVertexPairs(IEnumerable<SEquatableEdge<TVertex>>)

Sets vertices pairs.

Declaration
public void SetVertexPairs(IEnumerable<SEquatableEdge<TVertex>> pairs)
Parameters
Type Name Description
System.Collections.Generic.IEnumerable<SEquatableEdge<TVertex>> pairs

Vertices pairs.
Exceptions
Type Condition
System.ArgumentNullException

pairs is null.
System.ArgumentException

pairs is empty or any vertex from pairs is not part of VisitedGraph.
| Improve this Doc View Source

TryGetVertexPairs(out IEnumerable<SEquatableEdge<TVertex>>)

Tries to get vertices pairs if set.

Declaration
public bool TryGetVertexPairs(out IEnumerable<SEquatableEdge<TVertex>> pairs)
Parameters
Type Name Description
System.Collections.Generic.IEnumerable<SEquatableEdge<TVertex>> pairs

Vertices pairs if set.
Returns
Type Description
System.Boolean

True if vertex pairs were set, false otherwise.

Implements

Extension Methods