Wlvyr.DSA 0.3.2

Wlvyr.DSA

Wlvyr.DSA provides a collection of general-purpose data structures and algorithms.

Overview

• PriorityQueue with BinomialHeap
• Disjoint UnionSet
• Graph with AdjacencyList (List is actually a Dictionary<TNode, Dictionary<TNode,TEdge>>, a hybrid of Adjacency list and matrix).
• Graph Traversal Algorithms
  • Breadth First Search
    • Please note that edge classification event is not implemented.
  • Depth First Search
    • With cut-node indicators
  • Priority Based Shortest Path (Dijkstra's and A*)
  • Prim's Minimum Spanning Tree
  • Topological Sort
  • Strongly Connected Components

PriorityQueue

BinomialHeap

Heap Implementation Details

The BinomialHeap class is an implementation of IHeap<T> which is an extension of IConsumeOnlyHeap<T>. The interfaces are separated so that a client that isn't suppose to be allowed to add/remove won't be able to add/remove.

It can handle both min and max priority queue. When initializing, HeapType--that is min or max-- must be passed as argument. Because of this the method names are different. Ex. Instead of FindMin, it is FindNext. Another difference with other priority queue implementations is that the constructor requires an object (of type T) property selector (Func<T, double>). The chosen property will be used as the priorty level of every item in the priority queue. Because of this, Enqueue will only require T item as argument.

Also, because T is encapsulated in HeapNode<T> without the client ever knowing it, Removing or DecreaseKey requires a Dictionary<T, HeapNode<T>> to maintain O(logn). Otherwise, it would have been O(nlogn).

General Usage

Func<double, double> priorityProperty = x => x;
var pq = new BinomialHeap<double>(priorityProperty, HeapType.MIN, /*items // if any*/);

pq.Enqueue(1);
pq.Enqueue(100);

pq.Dequeue() // dequeue's 1.

Graphs

<br>

For a sparse graphs, Graph<TNode,TEdge> and NodeIdGraph<TNode,TEdge,TNodeId> will suffice as these use a variant of AdjacencyList (A hash table within hash table). For dense graphs, will need to implement an Adjacency Matrix implementation of IGraph<TNode,TEdge>.

Graph Implementation Details

Graph data structure and traversal are separated in order to be able to re-use the graph for different traversal approach. Furthermore, Node identity is not necessarily tied to an object, it can be tied to a node id (see NodeIdGraph<TNode,TEdge,TNodeId>). This is useful in the event that a node object comes from a serialization; so for as long as the node's id is serializable, the graph can be recreated and re-used.

<br>

The base of graph traversal are INotifyingTraversal<TNode, TEdge, TState> and ITraversal<TNode, TEdge, TResult>. The first interface allows an observer to listen for node traversal events (e.g. node reached, node processed, edge reached, etc.). This is to allow other traversal algorithms to build on top of another. The other interface is for clients which only need a result. Both must rely on IReadOnlyGraph<TNode, TEdge> graph interface.

<br>

The default implementation of INotifyingTraversal<TNode, TEdge, TState> is an abstract class,NotifyingTraversal<TNode, TEdge, TState>. It encapsulates the over all loop of the traversal, with the ability to skip a node, and cancel the traversal. Traversal implementation deriving from this abstract class need to define the "chain of responsibility" list on how to handle a node, the type of collection (e.g. stack, queue, binomial heap), and the type of state. This allows the deriving class to focus on the logic of the algorithm.

Note the notifying part, the observer, ITraversalObserver<TNode, TEdge, TState>, is passed into the Traverse method as an argument. This should allow any who needs to listen to the traversal to know of the current state of the traversal. The default concrete implementation of the observer is TraversalObserver<TNode, TEdge, TState>.

The default impelementation of ITraversal<TNode, TEdge, TResult> is Traversal<TNode, TEdge, TState TResult>. This requires INotifyingTraversal<TNode, TEdge, TState> to be passed as constructor argument. It is basically a wrapper. the TResult is achieved by listening to the observer's cancel or complete event and returns the state from there.

<br>

See below for usage example.

<br>

Traversal General Usage

Use Graph<TNode, TEdge> when you can ensure the id of TNode object (i.e. every TNode object that will be used to get data in the graph is the same object). Otherwise use NodeIdGraph<TNode, TEdge, TNodeId> or implement your own IGraph<TNode, TEdge, TNodeId>.

<br>

Example Usage of NotifyingTraversal:

// TNode and TEdge can be anything, they can both be int or Nullable<int>.
var graph = new Graph<TNode, TEdge>();
graph.InsertEdge(sourceNode, targetNode, edge, bidirectional: true|false);

var bfsTraverser = new BFSNotifyingTraversal<TNode, TEdgedeId>();

var observer = new TraversalObserver<TNode,TEdge, TraversalState<TNode>>();

// state - contains startNode, endNode, parentMap, etc.. and can be extended
// evOpt - contains event options to manipulate traversal
observer.AddOnBeginListener((state, evOpt) => {
     /*some code here, maybe for strong components, articulation points, etc... */ 
});

observer.OnNodeProcessedListeners.Add((node, state, evOpt) =>{ 
    /*some code here, maybe for strong components, articulation points, etc... */ 
});

observer.OnNodeReachedListeners.Add((node, state, evOpt) => { 
    /*some code here, maybe for strong components, articulation points, etc... */ 
});

observer.OnEdgeReachedListeners.Add((srcNode, tarNode, edge, state, evOpt) => { 
    /*some code here, maybe for strong components, articulation points, etc... */
});

observer.OnEdgeClassifiedListeners.Add((srcNode, tarNode, classified, state, evOpt) => { 
    /*some code here, maybe for strong components, articulation points, etc... */ 
});

// bfsTraverser.On___ListenersEtc.Add... (e.g. AddOnCompletedListener and AddOnCancelledListener)

observer.OnCompletedListeners.Add((trvD) => { traversalMapping.Remove(trvD); });

var traversalContext = new TraversalContext<TNode, TEdge>(graph);

bfsTraverser.Traverse(traversalContext.WithStartNode(someNode), observer: observer);

Example Usage of Traversal:

// TNode and TEdge can be anything, they can both be int or Nullable<int>.
var graph = new Graph<TNode, TEdge>();
graph.InsertEdge(sourceNode, targetNode, edge, bidirectional: true|false);

var bfsTraverser = new BFSTraversal<TNode,TEdge>();
var traversalContext = new TraversalContext<TNode, TEdge>(graph);

var result = bfsTraverser.Traverse(traversalContext);

Maintenance status

This project is maintained on a best-effort basis.<br> Updates may be infrequent due to limited available time.<br> Issues and feature requests are welcome, but responses and releases may take time.<br> Pull requests are not currently accepted.

License

This project is under the MIT License. See LICENSE for details.