Graphs - osvaldoandrade/ova-lib GitHub Wiki

Graphs

Read this page when the graph itself is a first-class object in your program and you want one API for structure, traversal, shortest paths, spanning trees, and topological work.

Construct the Right Graph First

The constructor is:

graph *create_graph(graph_type type,
                    graph_representation rep,
                    graph_traversal_strategy traversal_strategy,
                    graph_min_path_strategy min_path_strategy);

type chooses directed or undirected semantics. rep chooses adjacency lists or an adjacency matrix.

traversal_strategy chooses which concrete algorithm powers traverse.

min_path_strategy chooses which concrete algorithm powers min_path.

Use GRAPH_ADJACENCY_LIST when the graph is sparse or traversal-heavy.

Use GRAPH_ADJACENCY_MATRIX when direct edge lookup matters more than edge-count scaling, or when dense-graph work is the point.

Use GRAPH_TRAVERSE_BFS when level order is the point. Use one of the DFS strategies when depth-first visitation is the point and you want that choice fixed in the graph instance.

Use GRAPH_MIN_PATH_DIJKSTRA for non-negative edge weights. Use GRAPH_MIN_PATH_BELLMAN_FORD when negative edges may exist and you want reachable negative-cycle detection.

Graph Model

Vertices are identified by non-negative int ids.

add_vertex adds one vertex explicitly, called as g->add_vertex(g, ...).

add_edge also creates missing endpoint vertices implicitly. If the edge list is your source of truth, you can build the graph by adding edges only.

Edge weights are double. Missing edges are represented internally by GRAPH_NO_EDGE, which is INFINITY in the current source.

Structural API

Operation	Meaning
`add_vertex`	adds one vertex if the id is non-negative and not already present
`add_edge`	adds one weighted edge and, for undirected graphs, the symmetric edge
`remove_edge`	removes the edge and, for undirected graphs, the symmetric edge
`has_edge`	returns whether an edge exists
`get_neighbors`	returns a new list container of neighbor vertex ids
`vertex_count`	returns the number of present vertices
`has_vertex`	returns whether a vertex id is present
`get_edge_weight`	returns the stored weight or `GRAPH_NO_EDGE`

get_neighbors returns a list container even when the vertex is missing. In that case the list is empty.

Traversal Strategy and Topology

Function	Result shape	Notes
`traverse`	list of vertex ids	invalid start vertex returns an empty list; the visit order comes from the graph's configured traversal strategy
`topological_sort`	list of vertex ids or `NULL`	returns `NULL` on cyclic directed graphs
`connected_components`	outer list of inner vertex-id lists	use for undirected connectivity
`strongly_connected_components`	outer list of inner vertex-id lists	for directed graphs
`has_cycle`	`bool`	detects cycles under the graph type

Traversal result lists contain graph-owned int * vertex-id pointers. Free the list container. Do not free the integers inside it.

The traversal strategy is fixed per graph instance. If you need both BFS and DFS over the same structure, create two graph instances with different traversal strategies or rebuild the graph in the second configuration.

Single-Source Minimum Path

Function	Return contract	Caller cleanup
`min_path`	returns `1` on success, `0` on failure	free the returned `vector` if one is produced

min_path uses the graph's configured shortest-path strategy. With GRAPH_MIN_PATH_DIJKSTRA, min_path returns 0 on invalid input or allocation failure. With GRAPH_MIN_PATH_BELLMAN_FORD, min_path also returns 0 when it finds a reachable negative cycle.

The returned distance storage is sized to the graph vertex capacity, not only to the count of present vertices. Missing or unreachable vertices therefore still occupy slots in the result.

Minimum Spanning Trees

mst_prim and mst_kruskal are for undirected graphs. On directed graphs they return NULL.

mst_prim accepts a start vertex, but if that vertex is invalid it falls back to the first present vertex.

Both functions return a list of heap-allocated graph_weighted_edge * records. You must free each edge and then free the list container.

Representation Diagram

flowchart LR
    G[graph] --> T{graph_type}
    T --> D[GRAPH_DIRECTED]
    T --> U[GRAPH_UNDIRECTED]
    G --> R{graph_representation}
    R --> AL[GRAPH_ADJACENCY_LIST]
    R --> AM[GRAPH_ADJACENCY_MATRIX]
    G --> TS{graph_traversal_strategy}
    TS --> BFS[GRAPH_TRAVERSE_BFS]
    TS --> DFI[GRAPH_TRAVERSE_DFS_ITERATIVE]
    TS --> DFR[GRAPH_TRAVERSE_DFS_RECURSIVE]
    G --> PS{graph_min_path_strategy}
    PS --> DIJ[GRAPH_MIN_PATH_DIJKSTRA]
    PS --> BF[GRAPH_MIN_PATH_BELLMAN_FORD]

Example

#include "graph.h"

int main(void) {
    graph *g = create_graph(GRAPH_DIRECTED,
                            GRAPH_ADJACENCY_LIST,
                            GRAPH_TRAVERSE_BFS,
                            GRAPH_MIN_PATH_DIJKSTRA);
    vector *dist = NULL;

    g->add_edge(g, 0, 1, 1.0);
    g->add_edge(g, 1, 2, 2.0);
    g->min_path(g, 0, &dist);

    double d = dist ? dist->get(dist, 2) : -1.0;
    if (dist) {
        dist->free(dist);
    }
    g->free(g);
    return d == 3.0 ? 0 : 1;
}

Ownership and Cleanup

Destroy the graph with g->free(g).

Destroy neighbor lists, traversal lists, component lists, SCC lists, MST edge lists, and distance vectors on the caller side.

The graph object frees its own adjacency storage and its own vertex-id pointers.