imstkTaskGraph.h

/*
** This file is part of the Interactive Medical Simulation Toolkit (iMSTK)
** iMSTK is distributed under the Apache License, Version 2.0.
** See accompanying NOTICE for details.
*/

#pragma once

#include "imstkTaskNode.h"

#include <list>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace std
{
template<>
struct hash<std::shared_ptr<imstk::TaskNode>>
{
    std::size_t operator()(const std::shared_ptr<imstk::TaskNode>& node) const
    {
        using std::size_t;
        return node->getGlobalId();
    }
};
template<>
struct equal_to<std::shared_ptr<imstk::TaskNode>>
{
    bool operator()(const std::shared_ptr<imstk::TaskNode>& lhs,
                    const std::shared_ptr<imstk::TaskNode>& rhs) const
    {
        return lhs->getGlobalId() == rhs->getGlobalId();
    }
};
} // namespace std

namespace imstk
{
using TaskNodeVector  = std::vector<std::shared_ptr<TaskNode>>;
using TaskNodeList    = std::list<std::shared_ptr<TaskNode>>;
using TaskNodeSet     = std::unordered_set<std::shared_ptr<TaskNode>>;
using TaskNodeAdjList = std::unordered_map<std::shared_ptr<TaskNode>, TaskNodeSet>;
using TaskNodeNameMap = std::unordered_map<std::shared_ptr<TaskNode>, std::string>;

class TaskGraph
{
public:
    TaskGraph(std::string sourceName = "Source", std::string sinkName = "Sink");
    virtual ~TaskGraph() = default;

public:
    std::shared_ptr<TaskNode> getSource() const { return m_source; }
    std::shared_ptr<TaskNode> getSink() const { return m_sink; }

    TaskNodeVector& getNodes() { return m_nodes; }

    const TaskNodeAdjList& getAdjList() const { return m_adjList; }

    const TaskNodeAdjList& getInvAdjList() const { return m_invAdjList; }

// Node operations
public:
    TaskNodeVector::iterator findNode(std::string name);
    TaskNodeVector::const_iterator findNode(std::string name) const;
    TaskNodeVector::iterator findNode(std::shared_ptr<TaskNode> node);
    TaskNodeVector::const_iterator findNode(std::shared_ptr<TaskNode> node) const;

    bool containsNode(std::shared_ptr<TaskNode> node) const;

    TaskNodeVector::iterator endNode() { return m_nodes.end(); }
    TaskNodeVector::const_iterator endNode() const { return m_nodes.end(); }
    TaskNodeVector::iterator beginNode() { return m_nodes.begin(); }
    TaskNodeVector::const_iterator beginNode() const { return m_nodes.begin(); }

    bool addNode(std::shared_ptr<TaskNode> node);

    void addNodes(const std::vector<std::shared_ptr<TaskNode>>& nodes);

    std::shared_ptr<TaskNode> addFunction(std::string name, std::function<void()> func);

    bool removeNode(std::shared_ptr<TaskNode> node);

    bool removeNodeAndRedirect(std::shared_ptr<TaskNode> node);

    void insertAfter(std::shared_ptr<TaskNode> refNode, std::shared_ptr<TaskNode> newNode);

    void insertBefore(std::shared_ptr<TaskNode> refNode, std::shared_ptr<TaskNode> newNode);

// Edge operations
public:
    bool containsEdge(std::shared_ptr<TaskNode> srcNode, std::shared_ptr<TaskNode> destNode) const;

    void addEdge(std::shared_ptr<TaskNode> srcNode, std::shared_ptr<TaskNode> destNode);

    void addEdges(const std::vector<std::pair<std::shared_ptr<TaskNode>, std::shared_ptr<TaskNode>>>& edges);

    void nestGraph(std::shared_ptr<TaskGraph> subgraph, std::shared_ptr<TaskNode> source, std::shared_ptr<TaskNode> sink);

    void removeEdge(std::shared_ptr<TaskNode> srcNode, std::shared_ptr<TaskNode> destNode);

    bool isReachable(std::shared_ptr<TaskNode> srcNode, std::shared_ptr<TaskNode> destNode);

public:
    void clear();

    void clearEdges()
    {
        m_adjList.clear();
        m_invAdjList.clear();
    }

// Graph algorithms, todo: Move into filtering module
public:
    //static std::shared_ptr<TaskGraph> sum(std::shared_ptr<TaskGraph> graphA, std::shared_ptr<TaskGraph> graphB);

    static std::shared_ptr<TaskNodeList> topologicalSort(std::shared_ptr<TaskGraph> graph);

    static std::shared_ptr<TaskGraph> transitiveReduce(std::shared_ptr<TaskGraph> graph);

    static std::shared_ptr<TaskGraph> removeRedundantNodes(std::shared_ptr<TaskGraph> graph);

    static std::shared_ptr<TaskGraph> reduce(std::shared_ptr<TaskGraph> graph)
    {
        std::shared_ptr<TaskGraph> reducedGraph = transitiveReduce(graph);
        if (reducedGraph != nullptr)
        {
            return removeRedundantNodes(reducedGraph);
        }
        else
        {
            return nullptr;
        }
    }

    static std::shared_ptr<TaskGraph> removeUnusedNodes(std::shared_ptr<TaskGraph> graph);

    static bool isCyclic(std::shared_ptr<TaskGraph> graph);

    static TaskNodeNameMap getUniqueNodeNames(std::shared_ptr<TaskGraph> graph, bool apply = false);

    static std::unordered_map<std::shared_ptr<TaskNode>, double> getNodeStartTimes(std::shared_ptr<TaskGraph> graph);

    static TaskNodeList getCriticalPath(std::shared_ptr<TaskGraph> graph);

protected:
    TaskNodeVector  m_nodes;
    TaskNodeAdjList m_adjList;    
    TaskNodeAdjList m_invAdjList; 

    std::shared_ptr<TaskNode> m_source = nullptr;
    std::shared_ptr<TaskNode> m_sink   = nullptr;
};
} // namespace imstk