Stanford GraphBase

From US Go Wiki
Jump to: navigation, search

Contents

The Stanford GraphBase

The Stanford GraphBase was developed by Donald E. Knuth

A graph consists of one or more vertices and zero or more directed arcs connecting those vertices. Therefore graphs with isolated vertices are explicitly supported.

Data Structures

Arc

In Find_Path, each game is represented by a pair of Arcs connecting the two players. The number of days since the game was played is stored in Arc.len. Win or loss is recorded in Arc.a with 1 as a win and 0 as a loss. The game_id from the database is stored in Arc.b.

typedef struct arc_struct {
    struct vertex_struct *tip;     // this directed arc points to this vertex.
    struct arc_struct *next;       // next directed arc originating from this vertex.
    long len;                      // length or cost metric of this arc.
    util a,                        // 1 if a win by the player at the source of this arc (NOT the player at *tip.
                                   // 0 if  a loss.
         b;                        // game_id from the database.
} Arc;

Graph

typedef struct graph_struct {
    Vertex *vertices;              // pointer to an array of vertices
    long n;                        // total number of vertices
    long m;                        // total number of arcs
    char id[161];                  // identification
    char util_types[15];           // identify how the util structure members of Vertex, Arc and Graph
                                   //     are to be interpreted A: Arc, G: Graph, I: long integer,
                                   //     S: string, V: Vertex, Z: Zero as in unset and unused 
                                   //     first six describe the Vertex utils
                                   //     middle two describe the Arc utils
                                   //     last six describe the Graph utils
    Area data;
    Area aux_data;
    util uu, vv, ww, xx, yy, zz;
}
Graph;

Vertex

In Find_Path, each player is represented by a Vertex. The player's AGA ID is stored in Vertex.name.

typedef struct vertex_struct {
    struct arc_struct *arcs;       // linked list of arcs originating from this vertex.
    char *name;                    // name of this vertex. hashing functions use this as input.
    util u,                        // hash_link, used by the hashing functions and must not be changed (hash_link).
         v,                        // hash_head, used by the hashing functions and must not be changed (hash_head).
                                   // used by dijkstra() (rlink).
         w,                        // used by dijkstra() (llink).
         x,                        // used by dijkstra() to cache the computed distance to this vertex (hh_val).
         y,                        // used by dijkstra() for arc back to source vertex along shortest path
                                   // discovered to date from this vertex to source vertex (backlink).
         z;                        // used by dijkstra() for true distance from source to this vertex, if known.
                                   // if not known, used for shortest distance discovered to date (dist).
} Vertex;

Util

typedef union {
    struct vertex_struct *V;
    struct arc_struct *A;
    struct graph_struct *G;
    char *S;
    long l;
} util;

American_Go_Assocation_Go_Database

Personal tools