ytDLGraph.h

/*
  math/ytDLGraph.{h,c} : Graph by Doubly Linked List
  Copyright (C) 2018, Yoshinori Tamada <tamada  A T  ytlab.jp>
  All rights reserved.
 
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:
 
  * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
 
  * Redistributions in binary form must reproduce the above copyright 
    notice, this list of conditions and the following disclaimer in 
    the documentation and/or other materials provided with the 
    distribution.
 
  * Neither the name of Kyoto University nor the names of its 
    contributors may be used to endorse or promote products derived 
    from this software without specific prior written permission.
 
  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  POSSIBILITY OF SUCH DAMAGE.
*/
 
#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 */