1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
/* EINA_GRAPH - EFL graph processing library
* Copyright (C) 2013 Jérémy Zurcher
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to
* deal in the Software without restriction, including without limitation the
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies of the Software and its Copyright notices. In addition publicly
* documented acknowledgment must be given that this software has been used if no
* source code of this software is made available publicly. This includes
* acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
* documents or any documentation provided with any product containing this
* software. This License does not apply to any software that links to the
* libraries provided by this software (statically or dynamically), but only to
* the software provided.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
* IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef _EINA_GRAPH_BFS_H
#define _EINA_GRAPH_BFS_H
#include <eina_list.h>
#include <eina_graph.h>
/**
* @typedef Eina_Graph_BFS
* The basic Eina_Graph BFS type.
*/
typedef struct _Eina_Graph_BFS_Opaque Eina_Graph_BFS;
/**
* return the path to reach the given destination from the source.
*
* @param g the graph to compute the shortest path on.
* @param s the source vertex.
* @param d the destination vertex.
*
* @return a list of vertices to follow from source to reach v,
* NULL if v is not reachable.
*/
EAPI Eina_List *
eina_graph_bfs_shortest_path(Eina_Graph *g, unsigned int s, unsigned int d);
/**
* returns a Breadth First Search of the given graph.
*
* @param g the graph to build the BFS from.
* @param s the source vertex of the BFS.
*
* @return a new Breadth First Search.
*/
EAPI Eina_Graph_BFS *
eina_graph_bfs_new(Eina_Graph *g, unsigned int s);
/**
* free the given graph BFS.
*
* @param bfs the graph BFS to free.
*/
EAPI void
eina_graph_bfs_free(Eina_Graph_BFS *bfs);
/**
* get the source vertex of the graph BFS.
*
* @param bfs the graph BFS to consider.
*
* @return the source vertex of the BFS.
*/
EAPI unsigned int
eina_graph_bfs_source(Eina_Graph_BFS *bfs);
/**
* is there a path from the source to the given vertex.
*
* @param bfs the graph BFS to consider.
* @param v the vertex to test if there is a path to.
*
* @return EINA_TRUE if the vertex is reachable from the source.
*/
EAPI Eina_Bool
eina_graph_bfs_has_path_to(Eina_Graph_BFS *bfs, unsigned int v);
/*
* return the path to reach the given vertex from the source.
*
* the Eina_list returned must be freed by the user code.
*
* @param bfs the graph BFS to consider.
* @param v the vertex to test if there is a path to.
*
* @return a list of vertices to follow from source to reach v,
* NULL if v is not reachable.
*/
EAPI Eina_List *
eina_graph_bfs_path_to(Eina_Graph_BFS *bfs, unsigned int v);
/*
* return the distance from the source to the given vertex.
*
* @param bfs the graph BFS to consider.
* @param v the vertex to return the distance to.
*
* @return the distance from the source to the vertex.
* UINT_MAX in not reachable.
*/
EAPI unsigned int
eina_graph_bfs_dist_to(Eina_Graph_BFS *bfs, unsigned int v);
#endif /* _EINA_GRAPH_BFS_H */
|
