temelia/release/include/graph_constants.h.svntmp

/*!
 Temelia - Graph constants interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef GRAPHCONSTANTS_
#define GRAPHCONSTANTS_

#include "common.h"

typedef enum
{
	WHITE, GRAY, BLACK
} colors;

typedef enum
{
	DFS_UNKNOWN_EDGE,

	// Let (u, v) be and edge and variables time_start, time_stop and parent
	// obtained by the complete DFS travel applied to given graph_t.

	// (u, v) is tree edge <=> t_start[u] < t_start[v] < t_stop[v] < t_stop[v] and parent[v] = u.
	DFS_TREE_EDGE,

	// (u, v) is forward edge <=> t_start[u] < t_start[v] < t_stop[v] < t_stop[u] and parent[v] != u.
	DFS_FORWARD_EDGE,

	// (u, v) is back edge <=> t_start[v] < t_start[u] < t_stop[u] < t_stop[v].
	DFS_BACK_EDGE,

	// (u, v) is cross edge <=> t_start[v] < t_stop[v] < t_start[u] < t_stop[u].
	DFS_CROSS_EDGE
} temelia_dfs_edge_types;

typedef enum
{
	BFS_UNKNOWN_EDGE,

	// Let (u, v) be an edge and variables distance and parent obtained by
	// the complete BFS travel applied to given graph_t.

	// (u, v) is tree edge <=> u = parent[v]
	BFS_TREE_EDGE,

	// (u, v) is back edge <=> parent[..parent[u]] = v;
	BFS_BACK_EDGE,

	// (u, v) is cross edge <=> parent[..parent[u]] != v and distance[v] <= distance[u] + 1.
	BFS_CROSS_EDGE,

} temelia_bfs_edge_types;

// Use this string if you don't want named edges or NULL.
#define TEMELIA_UNNAMED_EDGE    ("")

extern char TEMELIA_DFS_EDGE_TYPES[4][10];

extern char TEMELIA_BFS_EDGE_TYPES[10][5];

#endif /*GRAPHCONSTANTS_*/