INGOR
Loading...
Searching...
No Matches
ytDLGraph.h
1/*
2 math/ytDLGraph.{h,c} : Graph by Doubly Linked List
3 Copyright (C) 2018, Yoshinori Tamada <tamada A T ytlab.jp>
4 All rights reserved.
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12
13 * Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in
15 the documentation and/or other materials provided with the
16 distribution.
17
18 * Neither the name of Kyoto University nor the names of its
19 contributors may be used to endorse or promote products derived
20 from this software without specific prior written permission.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 POSSIBILITY OF SUCH DAMAGE.
34*/
35
36#ifndef __YTLIB_DL_GRAPH_H
37#define __YTLIB_DL_GRAPH_H
38
39#include "util/ytIntArray.h"
40
41#ifdef DOXY
44#define ytDLGraph_NULL
45#else
46#define ytDLGraph_NULL ((size_t) -1)
47#endif /* DOXY */
48
49typedef struct ytDLGraph_Edge_t {
50 int pa;
51 int ch;
52
53 size_t pa_next;
54 size_t ch_next;
55
56 size_t pa_prev;
57 size_t ch_prev;
59
72typedef struct {
73#ifdef DOXY
74private:
75#endif
76 ytGraph super;
77
78 int nodes;
79 int edges;
80 size_t buff_size;
81 ytDLGraph_Edge * ptr; /* First 'nodes' pointers are used to
82 maintain parents and children for nodes */
83
84 /*
85 'pa_last' & 'ch_last' maintain the last edge for each node.
86 ''pa_last[v]' ('ch_last[v]') points to the position in 'ptr'
87 of the last parent (child) node for 'v'.
88 */
89 size_t * pa_last;
90 size_t * ch_last;
91
92 size_t last;
93
94 /* degrees of nodes. */
95 int * in_degree;
96 int * out_degree;
97
98} ytDLGraph;
99
100ytDLGraph * ytDLGraph_new(int nodes);
101void ytDLGraph_resize_buff(ytDLGraph * this, size_t size);
102void ytDLGraph_delete(void * this);
103void ytDLGraph_copy(ytDLGraph * this, const ytDLGraph * src);
104void ytDLGraph_clear(ytDLGraph * this);
105
106void ytDLGraph_status(ytDLGraph * this, FILE * fp);
107void ytDLGraph_fill(ytDLGraph * this);
108
109size_t ytDLGraph_numNodes(const ytDLGraph * this);
110size_t ytDLGraph_numEdges(const ytDLGraph * this);
111
112size_t ytDLGraph_add_edge(ytDLGraph * this, int u, int v);
113int ytDLGraph_check_edge(ytDLGraph * this, int u, int v);
114size_t ytDLGraph_check_edge_index(ytDLGraph * this, int u, int v);
115size_t ytDLGraph_check_edge_id(ytDLGraph * this, int u, int v);
116void ytDLGraph_remove_edge_id(ytDLGraph * this, size_t id);
117void ytDLGraph_remove_edge(ytDLGraph * this, int u, int v);
118
119void ytDLGraph_copyGraph(ytDLGraph * this, const ytGraph * src);
120void ytDLGraph_addGraph(ytDLGraph * this, const ytGraph * src);
121
122size_t ytDLGraph_first_parent_id(ytDLGraph * this, int v);
123size_t ytDLGraph_first_child_id(ytDLGraph * this, int v);
124size_t ytDLGraph_next_parent_id(ytDLGraph * this, size_t id);
125size_t ytDLGraph_next_child_id(ytDLGraph * this, size_t id);
126size_t ytDLGraph_parent_next(ytDLGraph * this, size_t id, int * pa);
127size_t ytDLGraph_child_next(ytDLGraph * this, size_t id, int * ch);
128
129int ytDLGraph_get_parent(ytDLGraph * this, size_t id);
130int ytDLGraph_get_child(ytDLGraph * this, size_t id);
131void ytDLGraph_get_edge(ytDLGraph * this, size_t id, int * u, int * v);
132void ytDLGraph_get_edge_index(const ytDLGraph * this, size_t index, int * u, int * v);
133
134size_t ytDLGraph_first_edge(ytDLGraph * this);
135size_t ytDLGraph_next_edge(ytDLGraph * this, size_t id);
136
137size_t ytDLGraph_parents(ytDLGraph * this, int v, ytIntArray * ar);
138
139
140int ytDLGraph_check_cyclic(ytDLGraph * this, int u, int v);
141
142size_t ytDLGraph_num_parents(ytDLGraph * this, int v);
143size_t ytDLGraph_num_children(ytDLGraph * this, int v);
144size_t ytDLGraph_degree(ytDLGraph * this, int v);
145
146void ytDLGraph_DAG_fsc_th(ytDLGraph * g, ytFloatArray * sc, float th,
147 ytDLGraph * dag);
148
149void ytDLGraph_print_all_parents(ytDLGraph * this, FILE * fp);
150void ytDLGraph_print_parents(ytDLGraph * this, int j, FILE * fp);
151void ytDLGraph_print_children(ytDLGraph * this, int j, FILE * fp);
152
153#endif /* __YTLIB_DL_GRAPH_H */
Interface class for handling graph structure.
Expandable array.
Definition ytDLGraph.h:49
Graph structure for efficient parents and children handling.
Definition ytDLGraph.h:72