61 lines
2.1 KiB
C
61 lines
2.1 KiB
C
#ifndef INCLUDED_C_BIPARTITEBFS_H
|
|
#define INCLUDED_C_BIPARTITEBFS_H
|
|
|
|
#ifndef INCLUDED_C_GRAPH_H
|
|
#include <c_Graph.h>
|
|
#endif /*INCLUDED_C_GRAPH_H*/
|
|
|
|
|
|
#ifndef INCLUDED_C_VERTEXIDLIST_H
|
|
#include <c_VertexIdList.h>
|
|
#endif /*INCLUDED_C_VERTEXIDLIST_H*/
|
|
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
typedef struct {
|
|
c_bool_t* marked; // marked[v] = has vertex v been discovered?
|
|
c_bool_t* color; // color[v] = color assigned to vertex v (true/false)
|
|
c_size_t* edge_to; // edge_to[v] = last vertex on shortest path to v
|
|
c_VertexIdList_t cycle; // Stores the shortest odd-length cycle if found
|
|
c_bool_t is_bipartite; // Global bipartite validation status flag
|
|
c_size_t V; // Cached vertex count boundary
|
|
c_Allocator_t allocator; // Memory allocator copy
|
|
} c_BipartiteBFS_t;
|
|
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
/**
|
|
* @brief Determines whether an undirected graph is bipartite using Breadth-First Search.
|
|
* @param self Pointer to the uninitialized bipartite tracking structure.
|
|
* @param G Pointer to the constant target graph object to verify.
|
|
* @param allocator Memory allocator instance pointer to deploy.
|
|
* @return C_SUCCESS on success, or an error status code on allocation failure.
|
|
*/
|
|
c_err_t c_BipartiteBFS_Init(c_BipartiteBFS_t* self, const c_Graph_t* G, c_Allocator_t* allocator);
|
|
|
|
/**
|
|
* @brief Drops all internal allocation states within the bipartite instance safely.
|
|
*/
|
|
void c_BipartiteBFS_Destroy(c_BipartiteBFS_t* self);
|
|
|
|
/**
|
|
* @brief Returns true if the graph is bipartite.
|
|
*/
|
|
c_bool_t c_BipartiteBFS_IsBipartite(const c_BipartiteBFS_t* self);
|
|
|
|
/**
|
|
* @brief Returns the color assignment of vertex v.
|
|
*/
|
|
c_bool_t c_BipartiteBFS_Color(const c_BipartiteBFS_t* self, c_VertexId_t v);
|
|
|
|
/**
|
|
* @brief Returns the shortest odd-length cycle if the graph is not bipartite, or empty if it is.
|
|
*/
|
|
const c_VertexIdList_t* c_BipartiteBFS_Cycle(const c_BipartiteBFS_t* self);
|
|
|
|
#endif /*INCLUDED_C_BIPARTITEBFS_H*/
|