Graph Matrix Visual Print

Introduction

图在邻接矩阵形式下的动态可视化打印，纯C实现。这对于学习数据结构和算法也是有用的。

另一个项目动态可视化打印二叉树。

图相比于树来说，更加复杂。手工画图时，不仅点的排列方式千差万别，边的相交更会让人头大。

因此这个项目与其说是个复杂的算法，不如说是怎样做才能符合人看图的习惯，才能尽量简洁。

考虑了大量绘图方法，本项目采用如下方式：

1. 所有的顶点横向放在一行（多行过于复杂）
2. 每个顶点左右加括号
3. 上半部分只画某个从顶点出发且终点序号大于这个顶点的边
4. 同理，下半部分只画序号小于这个顶点的边
5. 为了使图像更加紧凑，可以将出发点画在顶点的括号上
6. 先画后面几个顶点的边，对于某个顶点，先画离得近的（注意是在序号上离得近，如第2个顶点离第1个近，不是权值近）
7. 先画的边矮，后画的边高，这样可以有效减少相交的边
8. 采用纯ASCII字符绘制边（曾考虑过制表符等特殊符号，但显示效果不理想），但是箭头、拐弯等并不是很醒目
9. 特别地，用~符号来表示一些视觉上相交但是绕过的边

Preview

// Example 1:
[[    -1,     -1,     -1],
 [ 60726,     -1,  37775],
 [  3946,  63983,     -1]]

                 /-37775-\
                 |       v
[AAAA]       [BBB]       [CC]
     ^       |   ^       |
     \-60726-/   \-63983-/
     \-------3946--------/

// Example 2: 
[[    -1,  27602,     -1,  43470,   8926],
 [    -1,     -1,     -1,     -1,  46209],
 [ 19229,  17514,     -1,     -1,     -1],
 [    -1,     -1,  27271,     -1,  65046],
 [ 22947,  36137,  57666,  61250,     -1]]

       /---------------------8926----------------------\
       /---------------43470----------------\          |
       |              /-------------46209---~----------\
       /-27602-\      |                     |  /-65046-\
       |       v      |                     v  |       v
[AAAAAA]       [BBBBBB]       [CCCCC]       [DD]       [EEEEEEEEE]
       ^              ^       |     ^       |  ^       |
       |              \-17514-/     \-27271-/  \-61250-/
       |              |       |     \------57666-------/
       |              \-------~-----36137--------------/
       \--------19229---------/                        |
       \---------------------22947---------------------/

Usage

#include "graph_matrix_visual_print.h"

然后调用函数

graph_matrix_visual_print(stdout, 6, v_arr, matrix, "%s", "%u");

其中:

1. stdout为一个文件指针，也可以换成别的，便于输出到文件
2. 6是顶点个数
3. v_arr是顶点数组，推荐的顶点数据类型为基础类型，如int，double，char，也可以char *字符串
4. matrix为邻接矩阵，建议以-1表示边不存在
5. "%s"是元素打印时的格式化字符串，类似于printf中的第一个参数
6. "%u"是邻接矩阵某个元素，即路径权值打印时的格式化字符串

注意，若顶点类型为其他类型，如指针指向的元素、结构体等等，需要修改程序（已用TODO标出）

Theory

• 双向链表法存储每行要输出的字符串，先画顶点那一行，然后画边，动态调整高度
• 剩下的自己看吧，懒得写了XD

Future Work

• 邻接表形式
• ...