# Stanford GraphBase

From US Go Wiki

## 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 `Arc`s 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;