19 KiB
Introduction
A graph is a data structure composed of nodes (also known as vertices) and edges, and it is usually used to represent the relationships between objects. The following are the basic concepts and characteristics of graphs:
1. Basic Components
- Node (Vertex): It is the basic unit in a graph and represents an object.
- Edge: It is the line connecting two nodes and represents the relationship between nodes.
2. Types
- Directed Graph: The edges have directions, indicating a one-way relationship from one node to another.
- Undirected Graph: The edges have no directions, representing a two-way relationship between nodes.
- Weighted Graph: The edges have weights, which represent the cost or distance between two connected nodes.
3. Representation Methods
- Adjacency Matrix: A two-dimensional array is used to represent the connection relationships between nodes. The values in the array indicate the existence (1) or non-existence (0) of an edge. In a weighted graph, the weights of the edges are used for representation.
- Adjacency List: An array or linked list is used to represent the adjacent nodes of each node, which is suitable for sparse graphs.
4. Applications
- Social Networks: Nodes represent users, and edges represent the relationships between users.
- Network Routing: Nodes represent routers, and edges represent connections.
- Path Finding: For example, finding the shortest path in map applications.
This module implements a graph data structure, including basic graph operations such as adding and deleting vertices and edges, as well as algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS). The graph supports both directed and undirected graphs and is suitable for various graph theory applications.
Interface
Creating and Deleting a graph Object
graph_t graph_create(int max, int directed);
Creates and initializes a graph.
Parameters:
max: The maximum number of vertices in the graph.directed: A flag indicating whether the graph is a directed graph (non-zero) or an undirected graph (zero).
Returns: Returns a pointer to the newly created graph. If the creation fails, it returns NULL.
void graph_delete(graph_t graph);
Destroys the graph and releases related resources.
Parameters:
graph: A pointer to the graph to be destroyed.
Returns: None
Example:
graph_t graph = graph_create(10, 1);
graph_delete(graph);
Adding a Vertex
int graph_add_vertex(graph_t graph, void *data, int size);
Adds a vertex to the graph.
Parameters:
graph: A pointer to the graph to which the vertex is to be added.data: A pointer to the data associated with the vertex.size: The size of the data to be copied.
Returns: Returns the index of the added vertex. If the addition fails, it returns -1.
Example:
void graph_traverse_int(int index, void *data, int size)
{
printf("graph[%d] %d\r\n", index, *(int *)data);
}
static void test_add_vertex(void)
{
graph_t graph = NULL;
graph = graph_create(10, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 12), sizeof(int));
graph_add_vertex(graph, la(int, 13), sizeof(int));
graph_add_vertex(graph, la(int, 15), sizeof(int));
graph_add_vertex(graph, la(int, 23), sizeof(int));
graph_ls(graph, graph_traverse_int);
graph_delete(graph);
}
Here, la() is a macro definition for getting the address of a literal. For details, you can refer to the test_graph.c file. graph_ls() is a linear search method, which will be introduced later.
Result:
graph[0] 12
graph[1] 13
graph[2] 15
graph[3] 23
Adding an Edge
int graph_add_edge(graph_t graph, int start, int end, int weight);
Adds an edge to the graph.
Parameters:
graph: A pointer to the graph to which the edge is to be added.start: The index of the starting vertex.end: The index of the ending vertex.weight: The weight of the edge.
Returns: Returns 1 if the edge is added successfully, and 0 if it fails.
Example:
static void test_add_edge(void)
{
graph_t graph = NULL;
graph = graph_create(10, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 12), sizeof(int));
graph_add_vertex(graph, la(int, 13), sizeof(int));
graph_add_vertex(graph, la(int, 15), sizeof(int));
graph_add_vertex(graph, la(int, 23), sizeof(int));
printf("---------------\r\n");
graph_dfs(graph, 0, graph_traverse_int);
printf("---------------\r\n");
graph_add_edge(graph, 0, 1, 0);
graph_add_edge(graph, 0, 2, 0);
graph_add_edge(graph, 0, 3, 0);
graph_add_edge(graph, 1, 0, 0);
graph_add_edge(graph, 1, 2, 0);
graph_add_edge(graph, 1, 3, 0);
graph_add_edge(graph, 2, 3, 0);
graph_dfs(graph, 0, graph_traverse_int);
printf("---------------\r\n");
graph_delete(graph);
}
graph_dfs() is the Depth-First Search method, which will be introduced later. Comparing the search situations before and after adding edges, vertices that are not connected by edges cannot be found in the search.
Result:
---------------
graph[0] 12
---------------
graph[0] 12
graph[3] 23
graph[2] 15
graph[1] 13
---------------
Removing a Vertex and an Edge
int graph_remove_vertex(graph_t graph, int index);
Removes the specified vertex and its associated edges from the graph.
Parameters:
graph: A pointer to the graph from which the vertex is to be removed.index: The index of the vertex to be removed.
Returns: Returns 1 if the vertex is removed successfully, and 0 if it fails.
int graph_remove_edge(graph_t graph, int start, int end);
Removes the specified edge from the graph.
Parameters:
graph: A pointer to the graph from which the edge is to be removed.start: The index of the starting vertex of the edge.end: The index of the ending vertex of the edge.
Returns: Returns 1 if the edge is removed successfully, and 0 if it fails.
Example:
static void test_remove(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 0);
graph_add_edge(graph, 0, 2, 0);
graph_add_edge(graph, 0, 3, 0);
graph_add_edge(graph, 1, 0, 0);
graph_add_edge(graph, 1, 2, 0);
graph_add_edge(graph, 1, 3, 0);
graph_add_edge(graph, 2, 3, 0);
graph_remove_vertex(graph, 1);
graph_remove_edge(graph, 0, 2);
graph_dfs(graph, 0, graph_traverse_int);
graph_delete(graph);
}
Result:
graph[0] 100
graph[3] 500
Traversal
void graph_ls(graph_t graph, graph_traverse_t func);
Performs a linear traversal of the graph starting from the beginning position.
Parameters:
graph: A pointer to the graph to be traversed.func: A callback function executed for each visited vertex.
Returns: None
void graph_ls(graph_t graph, graph_traverse_t func);
Performs a Depth-First Search starting from the specified starting vertex.
Parameters:
graph: A pointer to the graph to be traversed.start: The index of the starting vertex.func: A callback function executed for each visited vertex.
Returns: None
void graph_dfs(graph_t graph, int start, graph_traverse_t func);
Performs a Breadth-First Search starting from the specified starting vertex.
Parameters:
graph: A pointer to the graph to be traversed.start: The index of the starting vertex.func: A callback function executed for each visited vertex.
Returns: None
Example:
static void test_search(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 0);
graph_add_edge(graph, 0, 2, 0);
graph_add_edge(graph, 0, 3, 0);
graph_add_edge(graph, 1, 0, 0);
graph_add_edge(graph, 1, 2, 0);
graph_add_edge(graph, 1, 3, 0);
graph_add_edge(graph, 2, 3, 0);
graph_remove_vertex(graph, 1);
graph_remove_edge(graph, 0, 2);
printf("graph_ls ----------------------\r\n");
graph_ls(graph, graph_traverse_int);
printf("graph_dfs ----------------------\r\n");
graph_dfs(graph, 0, graph_traverse_int);
printf("graph_bfs ----------------------\r\n");
graph_bfs(graph, 0, graph_traverse_int);
graph_delete(graph);
}
Result:
graph_ls ----------------------
graph[0] 100
graph[2] 300
graph[3] 500
graph_dfs ----------------------
graph[0] 100
graph[3] 500
graph_bfs ----------------------
graph[0] 100
graph[3] 500
Setting and Getting Data
int graph_vertex_set_data(graph_t graph, int index, void *data, int size);
Sets data for the specified vertex in the graph.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.data: A pointer to the data to be set.size: The size of the data.
Returns: Returns 1 if the data is set successfully, and 0 if it fails.
int graph_vertex_get_data(graph_t graph, int index, void *data, int size);
Gets data from the specified vertex in the graph.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.data: A pointer to the location where the data will be copied.size: The size of the data buffer.
Returns: Returns 1 if the data is obtained successfully, and 0 if it fails.
void *graph_vertex_data(graph_t graph, int index, int *size);
Gets the data of the specified vertex in the graph.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.size: A pointer to the variable storing the size of the vertex data (if notNULL).
Returns: Returns a pointer to the vertex data. If it fails, it returns NULL.
Example:
static void test_data(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_vertex_set_data(graph, 2, la(int, 1024), sizeof(int));
int size = 0;
printf("graph_vertex_data[3].data = %d\r\n", *(int *)graph_vertex_data(graph, 3, &size));
printf("graph_vertex_data[3].size = %d\r\n", size);
graph_ls(graph, graph_traverse_int);
graph_delete(graph);
}
Result:
graph_vertex_data[3].data = 500
graph_vertex_data[3].size = 4
graph[0] 100
graph[1] 200
graph[2] 1024
graph[3] 500
Out-degree and In-degree
int graph_out_degree(graph_t graph, int index);
Gets the out-degree of the specified vertex.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.
Returns: The out-degree of the vertex. If it fails, it returns -1.
int graph_in_degree(graph_t graph, int index);
Gets the in-degree of the specified vertex.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.
Returns: The in-degree of the vertex. If it fails, it returns -1.
Example:
static void test_degree(void)
{
graph_t graph = NULL;
graph = graph_create(10, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 0);
graph_add_edge(graph, 0, 2, 0);
graph_add_edge(graph, 0, 3, 0);
graph_add_edge(graph, 1, 0, 0);
graph_add_edge(graph, 1, 2, 0);
graph_add_edge(graph, 1, 3, 0);
graph_add_edge(graph, 2, 3, 0);
printf("graph_out_degree %d\r\n", graph_out_degree(graph, 3));
printf("graph_out_degree %d\r\n", graph_out_degree(graph, 2));
printf("graph_in_degree %d\r\n", graph_in_degree(graph, 0));
printf("graph_in_degree %d\r\n", graph_in_degree(graph, 2));
graph_delete(graph);
}
Result:
graph_out_degree 0
graph_out_degree 1
graph_in_degree 1
graph_in_degree 2
Adjacency
int graph_is_adjacent(graph_t graph, int start, int end);
Checks whether two vertices are adjacent.
Parameters:
graph: A pointer to the graph.start: The index of the starting vertex.end: The index of the ending vertex.
Returns: Returns 1 if the vertices are adjacent, otherwise returns 0 or fails.
Weight
int graph_get_edge_weight(graph_t graph, int start, int end);
This function is used to obtain the weight of the edge between two vertices (if it exists).
Parameters:
graph: A pointer to the graph.start: The index of the starting vertex.end: The index of the ending vertex.
Returns: It returns the weight of the edge. If the operation fails or the edge does not exist, it returns INT_MAX.
int graph_set_edge_weight(graph_t graph, int start, int end, int weight);
This function is used to set the weight of the edge between two vertices (if the edge exists).
Parameters:
graph: A pointer to the graph.start: The index of the starting vertex.end: The index of the ending vertex.weight: The weight to be set for the edge.
Returns: It returns 1 if the edge exists and the weight is set successfully, and 0 if the operation fails or the edge does not exist.
Example:
static void test_weight(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 0);
graph_add_edge(graph, 0, 2, 0);
graph_add_edge(graph, 0, 3, 10);
graph_add_edge(graph, 1, 0, 0);
graph_add_edge(graph, 1, 2, 0);
graph_add_edge(graph, 1, 3, 0);
graph_add_edge(graph, 2, 3, 0);
printf("graph_get_edge_weight = %d\r\n", graph_get_edge_weight(graph, 0, 3));
graph_set_edge_weight(graph, 0, 3, 1024);
printf("graph_get_edge_weight = %d\r\n", graph_get_edge_weight(graph, 0, 3));
graph_delete(graph);
}
Result:
graph_get_edge_weight = 10
graph_get_edge_weight = 1024
Checking Vertices
int graph_contains_vertex(graph_t graph, int index);
This function is used to check whether a vertex exists in the graph.
Parameters:
graph: A pointer to the graph.index: The index of the vertex.
Returns: It returns 1 if the vertex exists, and 0 if the operation fails or the vertex does not exist.
Topological Sorting
int graph_contains_vertex(graph_t graph, int index);
This function is supposed to perform a topological sorting on the graph.
Parameters:
graph: A pointer to the graph.
Returns: It does not return a value.
Shortest Path
void graph_shortest_path(graph_t graph, int start);
This function is used to find the shortest path from the starting vertex to other vertices.
Parameters:
graph: A pointer to the graph.start: The index of the starting vertex.
Returns: It does not return a value.
Example:
static void test_shortest_path(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 3);
graph_add_edge(graph, 0, 2, 2);
graph_add_edge(graph, 0, 3, 5);
graph_add_edge(graph, 1, 0, 6);
graph_add_edge(graph, 1, 2, 3);
graph_add_edge(graph, 1, 3, 2);
graph_add_edge(graph, 2, 3, 1);
graph_shortest_path(graph, 0);
graph_delete(graph);
}
Result:
Shortest path from 0 to 0: 0 (0)
Shortest path from 0 to 1: 3 (0 -> 1)
Shortest path from 0 to 2: 2 (0 -> 2)
Shortest path from 0 to 3: 3 (0 -> 2 -> 3)
Connected Graph
int graph_is_connected(graph_t graph);
This function is used to check whether the graph is connected.
Parameters:
graph: A pointer to the graph.
Returns: It returns 1 if the graph is connected, and 0 if it is not.
Complete Graph
int graph_is_complete(graph_t graph);
This function is used to check whether the graph is a complete graph.
Parameters:
graph: A pointer to the graph.
Returns: It returns 1 if the graph is a complete graph, and 0 if it is not.
Bipartite Graph
int graph_is_bipartite(graph_t graph);
This function is used to check whether the graph is a bipartite graph.
Parameters:
graph: A pointer to the graph.
Returns: It returns 1 if the graph is a bipartite graph, and 0 if it is not.
Eulerian Graph
int graph_is_eulerian(graph_t graph);
This function is used to check whether the graph is an Eulerian graph (which can traverse each edge exactly once).
Parameters:
graph: A pointer to the graph.
Returns: It returns 1 if the graph is an Eulerian graph, and 0 if it is not.
Minimum Vertex Cover
void graph_min_vertex_cover(graph_t graph);
This function is used to calculate the minimum vertex cover of the graph.
Parameters:
graph: A pointer to the graph.
Returns: It does not return a value.
Example:
static void test_min_cover(void)
{
graph_t graph = NULL;
graph = graph_create(100, 1);
if (!graph)
{
printf("graph_create fail!\r\n");
}
graph_add_vertex(graph, la(int, 100), sizeof(int));
graph_add_vertex(graph, la(int, 200), sizeof(int));
graph_add_vertex(graph, la(int, 300), sizeof(int));
graph_add_vertex(graph, la(int, 500), sizeof(int));
graph_add_edge(graph, 0, 1, 3);
graph_add_edge(graph, 0, 2, 2);
graph_add_edge(graph, 0, 3, 5);
graph_add_edge(graph, 1, 0, 6);
graph_add_edge(graph, 1, 2, 3);
graph_add_edge(graph, 1, 3, 2);
graph_add_edge(graph, 2, 3, 1);
graph_min_vertex_cover(graph);
graph_delete(graph);
}
Result:
0 3 1 2