class ComputationalGraph

Overview

/brief Class implementing a computation graph

In the context of nrp-core a computation graph is defined as a directed, acyclic property graph in which nodes are associated to objects of type ComputationalNode and which implements a ‘compute’ method. More…

#include <computational_graph.h>

class ComputationalGraph: private NGraph::tGraph {
public:
    // typedefs

    typedef std::vector<ComputationalGraph::vertex> comp_layer;

    // enums

    enum ExecMode;
    enum GraphState;

    // methods

    void insert_edge(const vertex& a, const vertex& b);
    void clear();
    void configure();
    void compute();
    GraphState getState() const;
    void setExecMode(ExecMode mode);
    ExecMode getExecMode();
};

Inherited Members

public:
    // typedefs

    typedef T vertex;
    typedef T value_type;
    typedef std::pair<vertex, vertex> edge;
    typedef std::set<vertex> vertex_set;
    typedef std::set<edge> edge_set;
    typedef std::pair<vertex_set, vertex_set> in_out_edge_sets;
    typedef std::map<vertex, in_out_edge_sets> adj_graph;
    typedef edge_set::iterator edge_iterator;
    typedef edge_set::const_iterator const_edge_iterator;
    typedef vertex_set::iterator vertex_iterator;
    typedef vertex_set::const_iterator const_vertex_iterator;
    typedef vertex_set::iterator vertex_neighbor_iterator;
    typedef vertex_set::const_iterator vertex_neighbor_const_iterator;
    typedef adj_graph::iterator iterator;
    typedef adj_graph::const_iterator const_iterator;
    typedef iterator node_iterator;
    typedef const_iterator const_node_iterator;

    // enums

    enum line_type;

    // methods

    unsigned int num_vertices() const;
    unsigned int num_nodes() const;
    unsigned int num_edges() const;
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    void clear();
    vertex_neighbor_iterator out_neighbors_begin(const vertex& a);
    vertex_neighbor_const_iterator out_neighbors_begin(const vertex& a) const;
    vertex_neighbor_iterator out_neighbors_end(const vertex& a);
    vertex_neighbor_const_iterator out_neighbors_end(const vertex& a) const;
    bool is_undirected() const;
    bool is_directed() const;
    void set_undirected();
    iterator find(const vertex& a);
    const_iterator find(const vertex& a) const;
    const vertex_set& in_neighbors(const vertex& a) const;
    vertex_set& in_neighbors(const vertex& a);
    const vertex_set& out_neighbors(const vertex& a) const;
    vertex_set& out_neighbors(const vertex& a);
    unsigned int in_degree(const vertex& a) const;
    unsigned int out_degree(const vertex& a) const;
    unsigned int degree(const vertex& a) const;
    bool isolated(const vertex& a) const;
    void insert_vertex(const vertex& a);

    void insert_new_vertex_inout_list(
        const vertex& a,
        const vertex_set& IN,
        const vertex_set& OUT
    );

    void insert_edge_noloop(iterator pa, iterator pb);
    void insert_edge(iterator pa, iterator pb);
    void insert_edge_noloop(const vertex& a, const vertex& b);
    void insert_edge(const vertex& a, const vertex& b);
    void insert_undirected_edge(const vertex& a, const vertex& b);
    void insert_edge(const edge& E);
    void insert_undirected_edge(const edge& E);
    bool remove_edge(iterator pa, iterator pb);
    void remove_edge(const vertex& a, const vertex& b);
    void remove_edge(const edge& E);
    void remove_undirected_edge(const vertex& a, const vertex& b);
    void remove_undirected_edge(const edge& e);
    void remove_vertex(iterator pa);
    void remove_vertex_set(const vertex_set& V);
    void remove_vertex(const vertex& a);
    bool includes_vertex(const vertex& a) const;
    bool includes_edge(const vertex& a, const vertex& b) const;
    bool includes_edge(const edge& e) const;
    std::vector<edge> edge_list() const;
    tGraph& plus_eq(const tGraph& B);
    tGraph intersect(const tGraph& B) const;
    tGraph operator * (const tGraph& B) const;
    tGraph minus(const tGraph& B) const;
    tGraph operator - (const tGraph& B) const;
    tGraph plus(const tGraph& B) const;
    tGraph operator + (const tGraph& B) const;
    tGraph& operator += (const tGraph& B);
    tGraph subgraph(const vertex_set& A) const;
    unsigned int subgraph_size(const vertex_set& A) const;
    double subgraph_sparsity(const vertex_set& A) const;
    void print() const;
    void absorb(iterator pa, iterator pb);
    iterator smart_absorb(iterator pa, iterator pb);
    vertex smart_absorb(vertex a, vertex b);
    void absorb(vertex a, vertex b);
    static const vertex& node(const_iterator p);
    static const vertex& node(iterator p);
    static const vertex& node(const_vertex_iterator p);
    static const vertex_set& in_neighbors(const_iterator p);
    static vertex_set& in_neighbors(iterator p);
    static const_vertex_iterator in_begin(const_iterator p);
    static const_vertex_iterator in_end(const_iterator p);
    static const vertex_set& out_neighbors(const_iterator p);
    static const_vertex_iterator out_begin(const_iterator p);
    static const_vertex_iterator out_end(const_iterator p);
    static vertex_set& out_neighbors(iterator p);
    static vertex_iterator out_begin(iterator p);
    static unsigned int num_edges(const_iterator p);
    static unsigned int num_edges(iterator p);
    static unsigned int out_degree(const_iterator p);
    static unsigned int out_degree(iterator p);
    static unsigned int in_degree(const_iterator p);
    static unsigned int in_degree(iterator p);
    static unsigned int degree(const_iterator p);
    static unsigned int degree(iterator p);
    static bool isolated(const_iterator p);
    static bool isolated(iterator p);

    static std::istream& read_line(
        std::istream& s,
        T& v1,
        T& v2,
        std::string& line,
        line_type& t
    );

Detailed Documentation

/brief Class implementing a computation graph

In the context of nrp-core a computation graph is defined as a directed, acyclic property graph in which nodes are associated to objects of type ComputationalNode and which implements a ‘compute’ method. Nodes use Ports to communicate with each other. Nodes are uniquely identified in the graph by an ‘id’ attribute which is of type string. Edges in the graph represent connections between nodes, ie. between ports in the source and target nodes.

Nodes can be of three types: ‘Input’, ‘Output’ and ‘Functional’. ‘Input’ nodes can only be source nodes in edges. ‘Output’ nodes can only be target nodes in edges. ‘Functional’ nodes can be both source and target.

The graph itself implements a ‘compute’ function which calls ‘compute’ on all the nodes in the graph in the right order. The latter is defined as follows: within a graph ‘compute’ operation, a node must always be executed after all the source nodes in edges for which the former is target.

The former definition on the execution order allows to divide the graph in layers which must be executed sequentially. Nodes in each layer can be executed in parallel.

The first layer will always be composed of nodes which have no inputs. These include ‘Input’ nodes and ‘Functional’ with no inputs. For convenience, the latter are moved to the second layer (with no consequences) and the first layer is kept with ‘Input’ nodes only. In the same way, all ‘Output’ nodes are moved to a separate layer which is executed the last.

Methods

void insert_edge(const vertex& a, const vertex& b)

Insert edge.

void clear()

Clear graph.

void configure()

Creates the graph execution structure and call ‘configure’ on each node.

void compute()

Executes all nodes in the graph in order.

GraphState getState() const

Returns true if the graph is configured, false otherwise.