matlab_bgl.h

The MatlabBGL library fills a hole in Matlab s suite of algorithms. Namely, it provides a rich set o

#ifndef MATLAB_BGL_H
#define MATLAB_BGL_H

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

#define MATLAB_BGL_VISITOR_METHOD_VERTEX(a) int (*a)(void *pdata, int u)
#define MATLAB_BGL_VISITOR_METHOD_EDGE(a) int (*a)(void *pdata, int ei, int u, int v)

typedef struct {
    void *pdata;
   
    MATLAB_BGL_VISITOR_METHOD_VERTEX(initialize_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(discover_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(examine_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(finish_vertex);

    MATLAB_BGL_VISITOR_METHOD_EDGE(examine_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(tree_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(non_tree_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(gray_target);
    MATLAB_BGL_VISITOR_METHOD_EDGE(black_target);

} bfs_visitor_funcs_t;

typedef struct {
    void *pdata;

    MATLAB_BGL_VISITOR_METHOD_VERTEX(initialize_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(start_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(discover_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(finish_vertex);

    MATLAB_BGL_VISITOR_METHOD_EDGE(examine_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(tree_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(back_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(forward_or_cross_edge);
} dfs_visitor_funcs_t;

typedef struct {
    void *pdata;

    MATLAB_BGL_VISITOR_METHOD_VERTEX(initialize_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(examine_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(discover_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(finish_vertex);

    MATLAB_BGL_VISITOR_METHOD_EDGE(examine_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_relaxed);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_not_relaxed);
} dijkstra_visitor_funcs_t;

typedef struct {
    void *pdata;

    MATLAB_BGL_VISITOR_METHOD_VERTEX(initialize_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(examine_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(discover_vertex);
    MATLAB_BGL_VISITOR_METHOD_VERTEX(finish_vertex);

    MATLAB_BGL_VISITOR_METHOD_EDGE(examine_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_relaxed);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_not_relaxed);
    MATLAB_BGL_VISITOR_METHOD_EDGE(black_target);
} astar_visitor_funcs_t;


typedef struct {
    void *pdata;

    MATLAB_BGL_VISITOR_METHOD_VERTEX(initialize_vertex);

    MATLAB_BGL_VISITOR_METHOD_EDGE(examine_edge);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_relaxed);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_not_relaxed);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_minimized);
    MATLAB_BGL_VISITOR_METHOD_EDGE(edge_not_minimized);

} bellman_ford_visitor_funcs_t;

/**
 * Wrap the boost graph library class for a push relabel max flow computation.
 *
 * the ja and ia arrays specify the connectivity of the underlying graph,
 * ia is a length (nverts+1) array with the indices in ja that start the
 * nonzeros in each row.  ja is a length (ia(nverts)) array with the 
 * columns of the connectivity.  
 *
 * the connectivity graph must be symmetric, that is, for each edge (i,j)
 * the edge (j,i) must exist in the connectivity graph.  
 *
 * @param nverts the number of vertices in the graph
 * @param ja the connectivity for each vertex
 * @param ia the row connectivity points into ja
 * @param src the source vertex for the flow
 * @param sink the sink vertex for the flow
 * @param cap the array of capacities for each edge
 * @param res the array of residual capacities for each edge
 * @param rev_edge_index an array indicating the index of the reverse edge 
 * for the edge with the current index
 * @param flow the maximum flow in the graph
 * @return an error code if possible
 */                  
int push_relabel_max_flow(
    int nverts, int *ja, int *ia,  /* connectivity params */
    int src, int sink, /* flow data */
    int* cap, int* res, /* capacity and residual capacity */
    int* rev_edge_index, int *flow);

/**
 * Wrap a boost graph library call to bfs.
 *
 * the ja and ia arrays specify the connectivity of the underlying graph,
 * ia is a length (nverts+1) array with the indices in ja that start the
 * nonzeros in each row.  ja is a length (ia(nverts)) array with the 
 * columns of the connectivity.  
 *
 * if d, dt, or pred is NULL, then that parameter is not computed.
 *   (currently not implemented)
 *
 * @param nverts the number of vertices in the graph
 * @param ja the connectivity for each vertex
 * @param ia the row connectivity points into ja
 * @param src the source vertex for the flow
 * @param d the distance array
 * @param dt the discover time array
 * @param pred the predecessor array
 * @return an error code if possible
 */
int breadth_first_search(
    int nverts, int *ja, int *ia, /* connectivity params */
    int src, /* problem data */
    int* d, int* dt, int* pred /* output data: distance, discover time, predecessor */
    );

int breadth_first_search_visitor(
    int nverts, int *ja, int *ia, /* connectivity params */
    int src, /* problem data */
    bfs_visitor_funcs_t vis /* visitor structure */
    );

/**
 * Wrap a boost graph library call to dfs.
 *
 * the ja and ia arrays specify the connectivity of the underlying graph,
 * ia is a length (nverts+1) array with the indices in ja that start the
 * nonzeros in each row.  ja is a length (ia(nverts)) array with the 
 * columns of the connectivity.  
 *
 * if dt, ft, or pred is NULL, then that parameter is not computed.
 *   (currently not implemented)
 *
 * @param nverts the number of vertices in the graph
 * @param ja the connectivity for each vertex
 * @param ia the row connectivity points into ja
 * @param src the source vertex for the flow
 * @param full if full is non-zero, then compute the full dfs over all
 *    vertices, not just the connected component.
 * @param d
 * @param dt the discover time array
 * @param ft the finish time array
 * @param pred the predecessor array
 * @return an error code if possible
 */
int depth_first_search(
    int nverts, int *ja, int *ia, /* connectivity params */
    int src, int full, /* problem data */
    int* d, int* dt, int* ft, int *pred /* output data: discover time, finish time, predecessor */
    );

int depth_first_search_visitor(
    int nverts, int *ja, int *ia, /* connectivity params */
    int src, int full, /* problem data */
    dfs_visitor_funcs_t vis /* visitor structure */
    );


/**
 * Wrap a boost graph library call to biconnected_components.
 *
 * the ja and ia arrays specify the connectivity of the underlying graph,
 * ia is a length (nverts+1) array with the indices in ja that start the
 * nonzeros in each row.  ja is a length (ia(nverts)) array with the 
 * columns of the connectivity.  
 *
 * if a or ci is NULL, then that parameter is not computed.
 *
 * @param nverts the number of vertices in the graph
 * @param ja the connectivity for each vertex
 * @param ia the row connectivity points into ja
 * @param a an array which will store the articulaion points of the graph 
 *     the array length should be n
 * @param ci the component index array which is length (nnz)
 * @return an error code if possible
 */

int strong_components(
    int nverts, int *ja, int *ia, /* connectivity params */
    int* ci);

int biconnected_components(
    int nverts, int *ja, int *ia, /* connectivity params */
    int* a, int* ci);

int dijkstra_sp(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* problem data */
    double* d, int *pred, double dinf);
int dijkstra_sp_visitor(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* problem data */
    double* d, int *pred, double dinf, 
    dijkstra_visitor_funcs_t vis);

int bellman_ford_sp(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* problem data */
    double* d, int *pred, double dinf);
int bellman_ford_sp_visitor(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* problem data */
    double* d, int *pred, double dinf,
    bellman_ford_visitor_funcs_t vis);


int dag_sp(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* problem data */
    double* d, int *pred, double dinf);

int johnson_all_sp(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    double* D, double dinf);

int floyd_warshall_all_sp(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    double* D, double dinf);

int kruskal_mst(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int* i, int* j, double* val, int* nedges /* tree output */);

int prim_mst(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int* i, int* j, double* val, int* nedges /* tree output */);

/**
 * If weight == NULL, then the algorithm is used is slightly more
 * efficient, so if you don't want the weighted version, explicitly
 * set weight to NULL
 */
int betweenness_centrality(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    double *centrality);

int clustering_coefficients(
    int nverts, int *ja, int *ia, /* connectivity params */
    double *ccoeffs);

int reverse_cuthill_mckee_order(
    int nverts, int *ja, int *ia, /* connectivity params */
    int start, /* input */
    int *perm /* permutation output */);

int king_order(
    int nverts, int *ja, int *ia, /* connectivity params */
    int *perm /* permutation output */);

int minimum_degree_order(
    int nverts, int *ja, int *ia, /* connectivity params */
    int *perm /* permutation output */);

int sloan_order(
    int nverts, int *ja, int *ia, /* connectivity params */
    int *perm /* permutation output */);

int astar_search(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* start vertex */
    double *d, int *pred, double *f, /* output */ 
    double *h /* heuristic function value for all vertices */, double dinf);
int astar_search_hfunc(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* start vertex */
    double *d, int *pred, double *f, 
    double (*hfunc)(void* pdata, int u), void* pdata /* heuristic function */, double dinf);
int astar_search_hfunc_visitor(
    int nverts, int *ja, int *ia, double *weight, /* connectivity params */
    int src, /* start vertex */
    double *d, int *pred, double *f, 
    double (*hfunc)(void* pdata, int u), void* pdata /* heuristic function */, double dinf,
    astar_visitor_funcs_t vis);



#ifdef __cplusplus
}
#endif /* __cplusplus */



#endif /* MATLAB_BGL_H */