/*******************************************************************
Directed Graph
1. How to define the data structure of a directed graph in C
2. How to create a directed graph
3. How to save a directed graph into a *.dot file and convert it into an
image file (*.png).
COMP9024
*******************************************************************/A directed graph is a type of graph in which edges have a direction associated with them.
This means that the connections between nodes are one-way, indicating a specific relationship from one node to another.
Directed graphs can be represented using various data structures, such as adjacency lists or adjacency matrices.
They offer a powerful way to analyze and visualize relationships between entities, making them essential in fields like computer science.
1 How to download this project in CSE VLAB
Open a terminal (Applications -> Terminal Emulator)
$ git clone https://github.com/sheisc/COMP9024.git
$ cd COMP9024/Graphs/DirectedGraph
DirectedGraph$
2 How to start Visual Studio Code to browse/edit/debug a project.
DirectedGraph$ code
Two configuration files (DirectedGraph/.vscode/launch.json and DirectedGraph/.vscode/tasks.json) have been preset.
In the window of Visual Studio Code, please click "File" and "Open Folder",
select the folder "COMP9024/Graphs/DirectedGraph", then click the "Open" button.
click Terminal -> Run Build Task
Open src/main.c, and click to add a breakpoint (say, line 11).
Then, click Run -> Start Debugging
├── Makefile defining set of tasks to be executed (the input file of the 'make' command)
|
├── README.md introduction to this tutorial
|
├── images *.dot and *.png files generated by this program
|
├── src containing *.c and *.h
| |
| ├── Graph.c containing the code for Directed Graph
| ├── Graph.h
| ├── main.c main()
|
└── .vscode containing configuration files for Visual Studio Code
|
├── launch.json specifying which program to debug and with which debugger,
| used when you click "Run -> Start Debugging"
|
└── tasks.json specifying which task to run (e.g., 'make' or 'make clean')
used when you click "Terminal -> Run Build Task" or "Terminal -> Run Task"Makefile is discussed in COMP9024/C/HowToMake.
In addition to utilizing VS Code, we can also compile and execute programs directly from the command line interface as follows.
DirectedGraph$ make
DirectedGraph$ ./main
********** The Adjacency Matrix *************
0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 1 0 0 0 1 1 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
...
dot -T png images/OurDirectedGraph_0000.dot -o images/OurDirectedGraph_0000.png
DirectedGraph$ make view
find . -name "*.png" | sort | xargs feh &
| Directed Graph |
|---|
 |
#define CONNECTED 1
#define NUM_OF_NODES 8
int main(void) {
// Create a directed graph with 8 nodes
struct Graph *pGraph = CreateGraph(NUM_OF_NODES, 1);
//char *nodeNames[NUM_OF_NODES] = {"A", "B", "C", "D", "E", "F", "G", "H"};
char *nodeNames[NUM_OF_NODES] = {"0", "1", "2", "3", "4", "5", "6", "7"};
// Add nodes
for (long u = 0; u < NUM_OF_NODES; u++) {
GraphAddNode(pGraph, u, nodeNames[u]);
}
// edges: source node id, target/destination node id, value of the edge
long edges[][3] = {
{3, 0, CONNECTED},
{0, 2, CONNECTED},
{0, 4, CONNECTED},
{4, 2, CONNECTED},
{2, 5, CONNECTED},
{2, 1, CONNECTED},
{2, 6, CONNECTED},
{1, 5, CONNECTED},
{6, 7, CONNECTED},
};
// Add edges
for (long i = 0; i < sizeof(edges)/sizeof(edges[0]); i++) {
GraphAddEdge(pGraph, edges[i][0], edges[i][1], edges[i][2]);
}
PrintGraph(pGraph);
// create a sub-directory 'images' (if it is not present) in the current directory
system("mkdir -p images");
// remove the *.dot and *.png files in the directory 'images'
system("rm -f images/*.dot images/*.png");
GenOneImage(pGraph, "OurDirectedGraph", "images/OurDirectedGraph", 0, NULL);
ReleaseGraph(pGraph);
return 0;
}// Storing information of a graph node
struct GraphNode {
char name[MAX_ID_LEN + 1];
};
typedef long AdjMatrixElementTy;
struct Graph{
/*
Memory Layout:
-----------------------------------------------------------
pAdjMatrix ----> Element(0, 0), Element(0, 1), ..., Element(0, n-1), // each row has n elements
Element(1, 0), Element(1, 1), ..., Element(1, n-1),
..... Element(u, v) ... // (n * u + v) elements away from Element(0, 0)
Element(n-1, 0), Element(n-1, 1), ..., Element(n-1, n-1)
-----------------------------------------------------------
Adjacency Matrix on Heap
*/
AdjMatrixElementTy *pAdjMatrix;
/*
Memory Layout
---------------------------
pNodes[n-1]
pNodes[1]
pNodes -----> pNodes[0]
----------------------------
struct GraphNode[n] on Heap
*/
struct GraphNode *pNodes;
// number of nodes
long n;
// whether it is a directed graph
int isDirected;
};
// 0 <= u < n, 0 <= v < n
// ELement(u, v) is (n * u + v) elements away from Element(0, 0)
#define MatrixElement(pGraph, u, v) (pGraph)->pAdjMatrix[(pGraph)->n * (u) + (v)]/*
Create a graph which can contain n nodes
*/
struct Graph *CreateGraph(long n, int isDirected) {
assert(n > 0);
struct Graph *pGraph = (struct Graph *) malloc(sizeof(struct Graph));
assert(pGraph);
pGraph->pAdjMatrix = (AdjMatrixElementTy *) malloc(sizeof(AdjMatrixElementTy) * n * n);
pGraph->pNodes = (struct GraphNode *) malloc(sizeof(struct GraphNode) * n);
assert(pGraph->pAdjMatrix && pGraph->pNodes);
memset(pGraph->pAdjMatrix, 0, sizeof(AdjMatrixElementTy) * n * n);
memset(pGraph->pNodes, 0, sizeof(struct GraphNode) * n);
pGraph->n = n;
pGraph->isDirected = isDirected;
return pGraph;
}
/*
Add an undirected edge between u and v
*/
void GraphAddUndirectedEdge(struct Graph *pGraph, long u, long v, AdjMatrixElementTy val) {
if (IsLegalNodeNum(pGraph, u) && IsLegalNodeNum(pGraph, v)) {
MatrixElement(pGraph, u, v) = val;
MatrixElement(pGraph, v, u) = val;
}
}
/*
Add a directed edge from u to v
*/
void GraphAddDirectedEdge(struct Graph *pGraph, long u, long v, AdjMatrixElementTy val) {
if (IsLegalNodeNum(pGraph, u) && IsLegalNodeNum(pGraph, v)) {
MatrixElement(pGraph, u, v) = val;
}
}
/*
Add a directed edge from u to v, or an undirected edge between u and v
*/
void GraphAddEdge(struct Graph *pGraph, long u, long v, AdjMatrixElementTy val) {
if (pGraph->isDirected) {
GraphAddDirectedEdge(pGraph, u, v, val);
} else {
GraphAddUndirectedEdge(pGraph, u, v, val);
}
}
void GraphAddNode(struct Graph *pGraph, long u, char *name) {
if (IsLegalNodeNum(pGraph, u)) {
snprintf(pGraph->pNodes[u].name, MAX_ID_LEN, "%s", name);
}
}5.2 How to generate images/OurDirectedGraph_0000.dot
digraph OurDirectedGraph {
"0" -> {"2"}
"0" -> {"4"}
"1" -> {"5"}
"2" -> {"1"}
"2" -> {"5"}
"2" -> {"6"}
"3" -> {"0"}
"4" -> {"2"}
"6" -> {"7"}
"0"
"1"
"2"
"3"
"4"
"5"
"6"
"7"
}
void Graph2Dot(struct Graph *pGraph,
char *filePath,
char *graphName,
int isDirectedGraph,
int displayLabel,
int *visited,
int displayVisited) {
FILE *dotFile = fopen(filePath, "w");
/*
FIXME: check sanity of the parameters.
*/
if (dotFile) {
char *edgeConnectorStr = "";
if (isDirectedGraph) {
edgeConnectorStr = "->";
fprintf(dotFile, "digraph %s {\n", graphName);
} else {
edgeConnectorStr = "--";
fprintf(dotFile, "graph %s {\n", graphName);
}
for (long u = 0; u < pGraph->n; u++) {
long vStart = u;
if (isDirectedGraph) {
vStart = 0;
}
for (long v = vStart; v < pGraph->n; v++) {
long val = MatrixElement(pGraph, u, v);
if (val) {
fprintf(dotFile, "\"%s\" %s {\"%s\"}",
pGraph->pNodes[u].name,
edgeConnectorStr,
pGraph->pNodes[v].name);
if (displayLabel) {
fprintf(dotFile, " [label=\"%ld\"]", val);
}
fprintf(dotFile, "\n");
}
}
}
/*
"0" [color=red]
*/
// if (displayVisited && visited) {
// for (long i = 0; i < pGraph->n; i++) {
// if (visited[i]) {
// fprintf(dotFile, "\"%s\" [color=red]\n", pGraph->pNodes[i].name);
// }
// }
// }
for (long i = 0; i < pGraph->n; i++) {
if (displayVisited && visited && visited[i]) {
fprintf(dotFile, "\"%s\" [color=red]\n", pGraph->pNodes[i].name);
} else {
fprintf(dotFile, "\"%s\"\n", pGraph->pNodes[i].name);
}
}
fprintf(dotFile, "}\n");
fclose(dotFile);
}
}5.3 How to generate images/OurDirectedGraph_0000.png
dot -T png images/OurDirectedGraph_0000.dot -o images/OurDirectedGraph_0000.png#define FILE_NAME_LEN 255
void GenOneImage(struct Graph *pGraph, char *graphName, char *fileName, int seqNo, int *visited) {
char dotFileName[FILE_NAME_LEN+1] = {0};
char pngFileName[FILE_NAME_LEN+1] = {0};
char command[(FILE_NAME_LEN+1)*4] = {0};
snprintf(dotFileName, FILE_NAME_LEN, "%s_%04d.dot", fileName, seqNo);
snprintf(pngFileName, FILE_NAME_LEN, "%s_%04d.png", fileName, seqNo);
Graph2Dot(pGraph, dotFileName, graphName, pGraph->isDirected, 0, visited, 1);
snprintf(command, FILE_NAME_LEN*4, "dot -T png %s -o %s", dotFileName, pngFileName);
// Execute the command in a child process (fork() + exec() on Linux)
system(command);
}