graph_constants.h.svntmp 2.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
  1. /*!
  2. Temelia - Graph constants interface.
  3. Copyright (C) 2008, 2009 Ceata (http://cod.ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #ifndef GRAPHCONSTANTS_
  18. #define GRAPHCONSTANTS_
  19. #include "common.h"
  20. typedef enum
  21. {
  22. WHITE, GRAY, BLACK
  23. } colors;
  24. typedef enum
  25. {
  26. DFS_UNKNOWN_EDGE,
  27. // Let (u, v) be and edge and variables time_start, time_stop and parent
  28. // obtained by the complete DFS travel applied to given graph_t.
  29. // (u, v) is tree edge <=> t_start[u] < t_start[v] < t_stop[v] < t_stop[v] and parent[v] = u.
  30. DFS_TREE_EDGE,
  31. // (u, v) is forward edge <=> t_start[u] < t_start[v] < t_stop[v] < t_stop[u] and parent[v] != u.
  32. DFS_FORWARD_EDGE,
  33. // (u, v) is back edge <=> t_start[v] < t_start[u] < t_stop[u] < t_stop[v].
  34. DFS_BACK_EDGE,
  35. // (u, v) is cross edge <=> t_start[v] < t_stop[v] < t_start[u] < t_stop[u].
  36. DFS_CROSS_EDGE
  37. } temelia_dfs_edge_types;
  38. typedef enum
  39. {
  40. BFS_UNKNOWN_EDGE,
  41. // Let (u, v) be an edge and variables distance and parent obtained by
  42. // the complete BFS travel applied to given graph_t.
  43. // (u, v) is tree edge <=> u = parent[v]
  44. BFS_TREE_EDGE,
  45. // (u, v) is back edge <=> parent[..parent[u]] = v;
  46. BFS_BACK_EDGE,
  47. // (u, v) is cross edge <=> parent[..parent[u]] != v and distance[v] <= distance[u] + 1.
  48. BFS_CROSS_EDGE,
  49. } temelia_bfs_edge_types;
  50. // Use this string if you don't want named edges or NULL.
  51. #define TEMELIA_UNNAMED_EDGE ("")
  52. extern char TEMELIA_DFS_EDGE_TYPES[4][10];
  53. extern char TEMELIA_BFS_EDGE_TYPES[10][5];
  54. #endif /*GRAPHCONSTANTS_*/