/Users/jst/src/grafalgo/cpp/include/Nca.h

Go to the documentation of this file.

#ifndef NCA_H
#define NCA_H

#include "stdinc.h"
#include "Adt.h"
#include "Util.h"
#include "Partition.h"
#include "Graph.h"

namespace grafalgo {

class Nca {
public:
        struct VertexPair {
                vertex v1, v2;
                VertexPair(vertex u, vertex v) : v1(u), v2(v) {}
        };

                Nca(Graph&, vertex, VertexPair[], int, vertex[]);
private:
        Graph   *tp;            // pointer to tree
        vertex  root;           // tree root
        VertexPair *pairs;      // vector of vertex pairs
        int     np;             // number of vertex pairs
        vertex  *ncav;          // pointer to nca vector

        Graph   *gp;            // graph used to represent pairs internally
        Partition *pp;          // groups closed vertices with their noa
        vertex  *noa;           // if u is a canonical element, noa[u] is noa

        enum state_t { unreached, open, closed };
        state_t *state;         // states of vertices in search

        void    compute_nca(vertex, vertex); // recursive search routine
};

} // ends namespace

#endif