ytDLGraph.h

/*
  math/ytDLGraph.{h,c} : Graph by Doubly Linked List
  Copyright (C) 2018, Yoshinori Tamada <tamada  A T  ytlab.jp>
  All rights reserved.
 
  See LICENSE.txt for details of the licensing agreement.
*/
 
#ifndef __YTLIB_DL_GRAPH_H
#define __YTLIB_DL_GRAPH_H
 
#include "util/ytIntArray.h"
 
#ifdef DOXY
#define ytDLGraph_NULL
#else
#define ytDLGraph_NULL ((size_t) -1)
#endif /* DOXY */
 
typedef struct ytDLGraph_Edge_t {
  int pa;
  int ch;
 
  size_t pa_next;
  size_t ch_next;
 
  size_t pa_prev;
  size_t ch_prev;
} ytDLGraph_Edge;
 
typedef struct {
#ifdef DOXY
private:
#endif
  ytGraph super;
  
  int nodes;
  int edges;
  size_t buff_size;
  ytDLGraph_Edge * ptr; /* First 'nodes' pointers are used to
                         maintain parents and children for nodes */
 
  /* 
     'pa_last' & 'ch_last' maintain the last edge for each node.
     ''pa_last[v]' ('ch_last[v]') points to the position in 'ptr'
     of the last parent (child) node for 'v'.
   */
  size_t * pa_last; 
  size_t * ch_last;
 
  size_t last;
 
  /* degrees of nodes. */
  int * in_degree;
  int * out_degree;
 
} ytDLGraph;
 
ytDLGraph * ytDLGraph_new(int nodes);
void      ytDLGraph_resize_buff(ytDLGraph * this, size_t size);
void      ytDLGraph_delete(void * this);
void      ytDLGraph_copy(ytDLGraph * this, const ytDLGraph * src);
void      ytDLGraph_clear(ytDLGraph * this);
 
void      ytDLGraph_status(ytDLGraph * this, FILE * fp);
void      ytDLGraph_fill(ytDLGraph * this);
 
size_t    ytDLGraph_numNodes(const ytDLGraph * this);
size_t    ytDLGraph_numEdges(const ytDLGraph * this);
 
size_t    ytDLGraph_add_edge(ytDLGraph * this, int u, int v);
int       ytDLGraph_check_edge(ytDLGraph * this, int u, int v);
size_t    ytDLGraph_check_edge_index(ytDLGraph * this, int u, int v);
size_t    ytDLGraph_check_edge_id(ytDLGraph * this, int u, int v);
void      ytDLGraph_remove_edge_id(ytDLGraph * this, size_t id);
void      ytDLGraph_remove_edge(ytDLGraph * this, int u, int v);
 
void      ytDLGraph_copyGraph(ytDLGraph * this, const ytGraph * src);
void      ytDLGraph_addGraph(ytDLGraph * this, const ytGraph * src);
 
size_t    ytDLGraph_first_parent_id(ytDLGraph * this, int v);
size_t    ytDLGraph_first_child_id(ytDLGraph * this, int v);
size_t    ytDLGraph_next_parent_id(ytDLGraph * this, size_t id);
size_t    ytDLGraph_next_child_id(ytDLGraph * this, size_t id);
size_t    ytDLGraph_parent_next(ytDLGraph * this, size_t id, int * pa);
size_t    ytDLGraph_child_next(ytDLGraph * this, size_t id, int * ch);
 
int       ytDLGraph_get_parent(ytDLGraph * this, size_t id);
int       ytDLGraph_get_child(ytDLGraph * this, size_t id);
void      ytDLGraph_get_edge(ytDLGraph * this, size_t id, int * u, int * v);
void      ytDLGraph_get_edge_index(const ytDLGraph * this, size_t index, int * u, int * v);
 
size_t    ytDLGraph_first_edge(ytDLGraph * this);
size_t    ytDLGraph_next_edge(ytDLGraph * this, size_t id);
 
size_t    ytDLGraph_parents(ytDLGraph * this, int v, ytIntArray * ar);
 
 
int       ytDLGraph_check_cyclic(ytDLGraph * this, int u, int v);
 
size_t    ytDLGraph_num_parents(ytDLGraph * this, int v);
size_t    ytDLGraph_num_children(ytDLGraph * this, int v);
size_t    ytDLGraph_degree(ytDLGraph * this, int v);
 
void      ytDLGraph_DAG_fsc_th(ytDLGraph * g, ytFloatArray * sc, float th, 
                             ytDLGraph * dag);
 
void      ytDLGraph_print_all_parents(ytDLGraph * this, FILE * fp);
void      ytDLGraph_print_parents(ytDLGraph * this, int j, FILE * fp);
void      ytDLGraph_print_children(ytDLGraph * this, int j, FILE * fp);
 
#endif /* __YTLIB_DL_GRAPH_H */