build_GraphAlgorithm

Graph Algorithms Library

This project provides a C-based library for creating and manipulating graphs. It supports both directed and undirected graphs, weighted and unweighted graphs, and includes a variety of graph traversal, search, and optimization algorithms.

Features

• Graph Creation and Manipulation: Add vertices and edges, remove vertices and edges, check connectivity, and more.
• Graph Traversal Algorithms: Depth-first search (DFS), breadth-first search (BFS), and their non-recursive versions.
• Pathfinding Algorithms:
  • Shortest path algorithms like Dijkstra, Bellman-Ford, and Floyd-Warshall.
  • Single-source and multi-source path exploration.
• Graph Properties:
  • Detect if a graph has cycles, is bipartite, or contains a Hamiltonian or Eulerian path/loop.
  • Find bridges and cut points in a graph.
• Minimum Spanning Tree Algorithms: Kruskal’s and Prim’s algorithms.
• Max Flow Algorithm: Calculate max flow using the Edmonds-Karp algorithm.
• Bipartite Matching: Supports matching with both max flow and Hungarian algorithms.
• Strongly Connected Components: Find SCCs using Kosaraju's algorithm.

Dependencies

This project depends on custom data structures:

• Hashtable (for maps)
• HashSet (for sets)
• ArrayList (dynamic array implementation)
• LinkedList (doubly linked list)

See: https://github.com/PL-play/build-collection to build and install dependencies.

Getting Started

Creating a Graph

You can create both directed and undirected graphs, as well as weighted or unweighted graphs.

Graph *graph = create_graph(1, 1);  // 1 for directed, 0 for undirected, second 1 for weighted

Adding Data and Edges

Add vertices to the graph with or without specifying an ID:

int vertex_id = add_graph_data(graph, data);
int vertex_with_id = add_graph_data_with_id(graph, id, data);
add_edge(graph, from_vertex, to_vertex, weight);

Traversing the Graph

You can traverse the graph using DFS or BFS:

VertexEntry *dfs_result = dfs_graph(graph);
VertexEntry *bfs_result = bfs_graph(graph);

Pathfinding

Use Dijkstra, Bellman-Ford, or Floyd-Warshall for finding the shortest paths:

Hashtable *distances = dijkstra(graph, source_vertex);
Hashtable *bellman_ford_distances = bellman_ford(graph, source_vertex);
Hashtable *floyd_distances = floyd(graph, &has_negative_circle);

Graph Algorithms

• Minimum Spanning Tree: Use Kruskal’s or Prim’s algorithms:

  LinkedList *mst = kruskal_mst(graph);

• Max Flow: Use the Edmonds-Karp algorithm for max flow:

  int max_flow;
  Hashtable *flow_map = max_flow(graph, source, sink, &max_flow);
  

Freeing the Graph

Don’t forget to free the graph when you're done using it to avoid memory leaks:

free_graph(graph);

Example

Graph *graph = create_graph(0, 1);  // Undirected, weighted graph

int v1 = add_graph_data(graph, some_data);
int v2 = add_graph_data(graph, other_data);
add_edge(graph, v1, v2, 5);  // Edge from v1 to v2 with weight 5

LinkedList *mst = kruskal_mst(graph);  // Find minimum spanning tree
free_graph(graph);  // Clean up

License

This project is licensed under the MIT License.