# Crate caffe2_nomnigraph

source ·## Macros

- | These #defines are useful when writing passes | as the collapse | | if (!cond) { | continue; // or break; or return; | } | | into a single line without negation

## Structs

- | \brief Annotations allow for generic | manipulation of neural network operations. | The base class contains a saved void* pointer | for external use. Derived classes add richer | semantics to the annotation and it is | encouraged to use them.
- | \brief A basic block holds a reference to | a subgraph of the data flow graph as well as | an ordering on instruction execution. Basic | blocks are used for control flow analysis.
- | \brief Control flow graph is a graph of basic | blocks that can be used as an analysis tool. | | \note G Must be of type Graph<T, U>.

- | Attempts to create a realistic dataflow | graph that shows a fuse procedure. |
- \brief Edge within a NomGraph.
- | This file defines utilities for matching | subgraphs. |
- | MatchGraph is a graph of MatchPredicate | and it contains utilities for subgraph | matching. | | (TODO) the subgraph matching methods | currently still requires a root match | node to be passed in. | | We should improve the matching algorithm | to eliminate this requirement. |
- | MatchGraph is a graph of MatchPredicate. | | MatchPredicate needs a predicate for | node matching and | | - includeInSubgraph: whether this | node and nodes/edges reachable from | it should be included in the return matched | subgraph (if the pattern matches). | | This is useful in case we would like to | specify a matching pattern but do not | want part of the pattern to be included | in the returned subgraph. | | - A count, which means we may want to match | this node multiple times from its incoming | edges. The count can be unlimited (think | about it as a regex star). | | - If nonTerminal flag is set, it means | we will not consider outgoing edges | from the node when doing subgraph matching. |

- | ———– | @brief | | A simple graph implementation | | Everything is owned by the graph to simplify | storage concerns. |
- \brief NomNode within a NomGraph.
- | ———– | @brief | | This class enables a listener pattern. | | It is to be used with a “curious recursive | pattern” i.e. Derived : public Notifier
| {} | - | Implements accessors for a generic type T. If | the type is not specified (i.e., void template | type) then the partial specification gives an | empty type.
- | ———– | @brief | | Effectively a constant reference to | a graph. | | ———– | @note | | A Subgraph could actually point to an | entire NomGraph. | | Subgraphs can only contain references | to nodes/edges in a NomGraph. | | They are technically mutable, but this | should be viewed as a construction helper | rather than a fact to be exploited. There | are no deleters, for example. |
- | ———– | @brief | | Tarjans algorithm implementation. | | See details on how the algorithm works | here: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm | | The algorithm works by annotating nodes, | but we want to be able to handle generic | graphs. Thus, we wrap the input graph | with nodes that contain data composed | of references to the original graph | (for later recovery) and the data required | for the algorithm (see NodeWrapper). | | We then run the algorithm and return | a reverse-topologically sorted vector | of strongly connect components in the | form of Subgraphs on the Graph. | | ———– | @note | | Head/Tail is used in reverse in Tarjan’s | early papers. | | \bug Edges not included in returned | subgraphs. |
- | Very simple random number generator | used to generate platform independent | random test data. |
- | \brief Topological sort using DFS. | | This algorithm takes a Graph object and | returns node references in topological order.
- | Although these seem generic, they make | subtle assumptions about the structure | of the graph that is 100% valid for NNModule | graphs but not any graph (such as data | being a unique_ptr). |

## Enums

- An optional tensor-type specifier.

## Constants

## Traits

- | This is just a way to fix issues when the | dyn_cast<> implementation can’t automatically | downcast. |
- | This is just a way to fix issues when the | isa<> implementation can’t automatically | downcast. |

## Functions

- | ———– | @brief | | A binary graph matching algorithm based | on Kahn’s algorithm. |
- TODO: move this to more generic location. TODO: [algo] improve this algorithm, as it is horrendously inefficient.
- Convert a graph to dot string.
- | Convert a graph to dot string and annotate | subgraph clusters. |
- Convert a subgraph to dot string.
- Create an operator
- Create an output tensor node
- \brief Create subgraph object from graph.
- \brief Deletes a referenced node from the control flow graph.
- | \brief Map all nodes to their dominance | frontiers: a set of nodes that does not | strictly dominate the given node but does | dominate an immediate predecessor. This is | useful as it is the exact location for the | insertion of phi nodes in SSA representation.
- | \brief A dominator tree finder. Runs in | O(M*N), there exist more efficient | implementations. | | High level description of the algorithm: | | 1) Find a map of {node}->{dominator set} | – | allNodes = reachable(root) | for n in nodes: | temporarily delete n from the graph | dom[n] = allNodes - reachable(root) | restore n to the graph | | 2) Construct tree from that map | – | starting at root, BFS in dominatorMap: | if newnode has inedge, delete it | draw edge from parent to child
- | Get the name of the node regardless of | underlying type. |
- Get all nodes tracked by CF graph
- NeuralNetData specific helpers.
- | The node has a unique consumer (there | may be multiple edges from output to | the single consumer). |
- | ———– | @brief | | Map all nodes in the graph to their immediate | dominators. |
- | ———– | @brief | | Induces edges on a subgraph by connecting | all nodes that are connected in the original | graph. |
- \brief Helper for dominator tree finding.
- | Set all consumers of first argument | to consume the second argument |
- Call reset before creating a new TestMatchGraph.
- | ———– | @brief | | A function wrapper to infer the graph | template parameters. |
- | Node matches a criteria (string) if | the data string is the same as the criteria. | Special case: “*” will match any thing. |
- | Our test graph looks like this: | +—––+ | | entry | | +—––+ | | | | | v | +—––+ | | 1 | | +—––+ | | | | | v | +—+ +—––+ | | 4 | <– | 2 | | +—+ +—––+ | | | | | | | | v | | +—––+ | | | 3 | | | +—––+ | | | | | | | | v | | +—––+ | +—–> | 6 | | +—––+ | | | | | v | +—+ +—––+ | | 5 | –> | 7 | | +—+ +—––+ | | | | | v | +—––+ | | exit | | +—––+ | | Here is the code used to generate the dot file | for it: | | auto str = nom::converters::convertToDotString(&graph, | [](nom::Graphstd::string::NodeRef node) { | std::map<std::string, std::string> labelMap; | labelMap[“label”] = node->data(); | return labelMap; | });
- | \brief A function wrapper to infer the graph | template parameters. | | TODO change this to const GraphT& g
- | Helper methods to make it less verbose | to create match graphs. |

## Type Definitions

- | \brief Helper for extracting the type of | BasicBlocks given a graph (probably a dataflow | graph). TODO: refactor this to come from | something like Graph::NodeDataType
- | Map from match node to corresponding | node in the graph to be scanned. |