10-13 Stringy

Stringy representation of a graph.

Stringy Storage of a Graph

The (until now fictional) “string method” of storing a graph lists strings of connected vertices on every line.

Assignment: Write a function that accepts an already open file (returned from open) and creates an instance of your Graph class by reading the “stringy graph file” described below.

def read_stringy(infile) -> Graph:
    firstline = infile.readline()
    return None

General format of a “stringy graph file”:

    V xxx
    L yyy
    v1 v2 v3 ... vn
    w1 w1 w3 ... wn
    ...

Interpretation

  • The line with the V specifies how many vertices, numbered 0 up to xxx.
  • The line with the L specifies how many vertex-chain specifying lines there are in the file.
  • The remaining lines indicate edges from v1 to v2, v2 to v3, v3 to v4, etc.

Example 1

A rectangle graph could be written:

V 4
L 1
0 1 2 3 0

This would be equivalent to the adjacency list:

NVERT 4
0 1 3
1 2
2 3

Example 2

Working with the graph below.

The read_stringy function should be able to take in any of the alternative inputs listed below and produce a Graph that represents the picture above.

There are several ways to write the graph for Example 2.

One possibility:

V 5
L 2
0 1 2 3 0
2 4

Alternatively:

V 5
L 2
2 3 0
0 1 2 4

Or even:

V 5
L 1
2 3 0 1 2 4

Additional Features

  • Add a line A zzz to indicate how many “aliases”.

  • Then zzz lines of the form

      0 WALL
  1 BRING
  2 HELP
  3 DEMO

    After the aliases are specified, you can give the list of vertices by using the aliases:

      WALL BRING HELP DEMO WALL

    is equivalent to

      0 1 2 3 0