- Concerning Graph Part VI Symbol
- Concerning Graph Part IV: Single
- Concerning Graph Part III: Singl
- Concerning Graph Part V: Connect
- Concerning Graph Part II: Depth
- Concerning Graph Part VII Digrap
- Concerning Graph Part VIII Cycle
- Concerning Graph Part I: Basic I
- Concerning Graph Part IX Edge We
- Concerning Graph Part X MST Algo
We address symbol graph in this post.
We use RBBSTree as the underlying symbol table here, but a hash table might be more efficient.
#include "graph.c"
#include "red_black_bst.c"
#ifndef SYMBOL_GRAPH
#define SYMBOL_GRAPH
typedef struct SymbolGraphStruct {
RBBSTree st;
char **keys;
Graph g;
}*SymbolGraph;
SymbolGraph SymbolGraphCreate(char *fileName, char *delim) {
SymbolGraph sg = (SymbolGraph)malloc(sizeof(*sg));
sg->st = RBBSTreeCreate(RBBSTKeyTypeString);
FILE *fp = fopen(fileName, "r");
char line[100];
while (fgets(line, 100, fp) != NULL) {
int linel = strlen(line);
if (line[linel - 1] == '\n') { line[linel - 1] = '\0'; }
char *sub = strtok(line, delim);
while (sub != NULL) {
if (RBBSTreeGet(sg->st, sub) == INT_MIN) { RBBSTreeSet(sg->st, sub, RBBSTreeCount(sg->st)); }
sub = strtok(NULL, delim);
}
}
sg->g = GraphCreateV(RBBSTreeCount(sg->st));
sg->keys = (char**)malloc(sizeof(char*) * RBBSTreeCount(sg->st));
rewind(fp);
while (fgets(line, 100, fp) != NULL) {
int linel = strlen(line);
if (line[linel - 1] == '\n') { line[linel - 1] = '\0'; }
char *sub = strtok(line, delim);
int v = RBBSTreeGet(sg->st, sub);
if (sg->keys[v] == NULL) { sg->keys[v] = String(sub); }
sub = strtok(NULL, delim);
while (sub != NULL) {
int w = RBBSTreeGet(sg->st, sub);
if (sg->keys[w] == NULL) { sg->keys[w] = String(sub); }
GraphAddEdge(sg->g, v, w);
sub = strtok(NULL, delim);
}
}
fclose(fp);
return sg;
}
bool SymbolGraphContains(SymbolGraph sg, char *s) { return RBBSTreeGet(sg->st, s) != INT_MIN; }
int SymbolGraphIndex(SymbolGraph sg, char *s) { return RBBSTreeGet(sg->st, s); }
char* SymbolGraphName(SymbolGraph sg, int v) { return v < sg->g->v ? sg->keys[v] : NULL; }
Graph SymbolGraphGraph(SymbolGraph sg) { return sg->g; }
#endif
网友评论