50. graphs

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.1 Introduction to graphs

The graphs package provides graph and digraph data structure for Maxima. Graphs and digraphs are simple (have no multiple edges nor loops), although digraphs can have a directed edge from u to v and a directed edge from v to u.

Internally graphs are represented by adjacency lists and implemented as a lisp structures. Vertices are identified by their ids (an id is an integer). Edges/arcs are represented by lists of length 2. Labels can be assigned to vertices of graphs/digraphs and weights can be assigned to edges/arcs of graphs/digraphs.

There is a draw_graph function for drawing graphs. Graphs are drawn using a force based vertex positioning algorithm. draw_graph can also use graphviz programs available from http://www.graphviz.org. draw_graph is based on the maxima draw package.

To use the graphs package, first load it with load(graphs).

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.2 Functions and Variables for graphs

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.2.1 Building graphs

Function: create_graph (v_list, e_list)

Function: create_graph (n, e_list)

Function: create_graph (v_list, e_list, directed)

Creates a new graph on the set of vertices v_list and with edges e_list.

v_list is a list of vertices ([v1, v2,..., vn]) or a list of vertices together with vertex labels ([[v1,l1], [v2,l2],..., [vn,ln]]).

n is the number of vertices. Vertices will be identified by integers from 0 to n-1.

e_list is a list of edges ([e1, e2,..., em]) or a list of edges together with edge-weights ([[e1, w1], ..., [em, wm]]).

If directed is not false, a directed graph will be returned.

Example 1: create a cycle on 3 vertices:

(%i1) load (graphs)$
(%i2) g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
(%i3) print_graph(g)$
Graph on 3 vertices with 3 edges.
Adjacencies:
  3 :  1  2
  2 :  3  1
  1 :  3  2

Example 2: create a cycle on 3 vertices with edge weights:

(%i1) load (graphs)$
(%i2) g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
                          [[1,3], 3.0]])$
(%i3) print_graph(g)$
Graph on 3 vertices with 3 edges.
Adjacencies:
  3 :  1  2
  2 :  3  1
  1 :  3  2

Example 3: create a directed graph:

(%i1) load (graphs)$
(%i2) d : create_graph(
        [1,2,3,4],
        [
         [1,3], [1,4],
         [2,3], [2,4]
        ],
        'directed = true)$
(%i3) print_graph(d)$
Digraph on 4 vertices with 4 arcs.
Adjacencies:
  4 :
  3 :
  2 :  4  3
  1 :  4  3

Function: copy_graph (g): Returns a copy of the graph g.

Function: circulant_graph (n, d)

Returns the circulant graph with parameters n and d.

Example:

(%i1) load (graphs)$
(%i2) g : circulant_graph(10, [1,3])$
(%i3) print_graph(g)$
Graph on 10 vertices with 20 edges.
Adjacencies:
  9 :  2  6  0  8
  8 :  1  5  9  7
  7 :  0  4  8  6
  6 :  9  3  7  5
  5 :  8  2  6  4
  4 :  7  1  5  3
  3 :  6  0  4  2
  2 :  9  5  3  1
  1 :  8  4  2  0
  0 :  7  3  9  1

Function: clebsch_graph (): Returns the Clebsch graph.

Function: complement_graph (g): Returns the complement of the graph g.

Function: complete_bipartite_graph (n, m): Returns the complete bipartite graph on n+m vertices.

Function: complete_graph (n): Returns the complete graph on n vertices.

Function: cycle_digraph (n): Returns the directed cycle on n vertices.

Function: cycle_graph (n): Returns the cycle on n vertices.

Function: cuboctahedron_graph (n): Returns the cuboctahedron graph.

Function: cube_graph (n): Returns the n-dimensional cube.

Function: dodecahedron_graph (): Returns the dodecahedron graph.

Function: empty_graph (n): Returns the empty graph on n vertices.

Function: flower_snark (n)

Returns the flower graph on 4n vertices.

Example:

(%i1) load (graphs)$
(%i2) f5 : flower_snark(5)$
(%i3) chromatic_index(f5);
(%o3)                           4

Function: from_adjacency_matrix (A): Returns the graph represented by its adjacency matrix A.

Function: frucht_graph (): Returns the Frucht graph.

Function: graph_product (g1, g1)

Returns the direct product of graphs g1 and g2.

Example:

(%i1) load (graphs)$
(%i2) grid : graph_product(path_graph(3), path_graph(4))$
(%i3) draw_graph(grid)$

Function: graph_union (g1, g1): Returns the union (sum) of graphs g1 and g2.

Function: grid_graph (n, m): Returns the n x m grid.

Function: great_rhombicosidodecahedron_graph (): Returns the great rhombicosidodecahedron graph.

Function: great_rhombicuboctahedron_graph (): Returns the great rhombicuboctahedron graph.

Function: grotzch_graph (): Returns the Grotzch graph.

Function: heawood_graph (): Returns the Heawood graph.

Function: icosahedron_graph (): Returns the icosahedron graph.

Function: icosidodecahedron_graph (): Returns the icosidodecahedron graph.

Function: induced_subgraph (V, g)

Returns the graph induced on the subset V of vertices of the graph g.

Example:

(%i1) load (graphs)$
(%i2) p : petersen_graph()$
(%i3) V : [0,1,2,3,4]$
(%i4) g : induced_subgraph(V, p)$
(%i5) print_graph(g)$
Graph on 5 vertices with 5 edges.
Adjacencies:
  4 :  3  0
  3 :  2  4
  2 :  1  3
  1 :  0  2
  0 :  1  4

Function: line_graph (g): Returns the line graph of the graph g.

Function: make_graph (vrt, f)

Function: make_graph (vrt, f, oriented)

Creates a graph using a predicate function f.

vrt is a list/set of vertices or an integer. If vrt is an integer, then vertices of the graph will be integers from 1 to vrt.

f is a predicate function. Two vertices a and b will be connected if f(a,b)=true.

If directed is not false, then the graph will be directed.

Example 1:

(%i1) load(graphs)$
(%i2) g : make_graph(powerset({1,2,3,4,5}, 2), disjointp)$
(%i3) is_isomorphic(g, petersen_graph());
(%o3)                         true
(%i4) get_vertex_label(1, g);
(%o4)                        {1, 2}

Example 2:

(%i1) load(graphs)$
(%i2) f(i, j) := is (mod(j, i)=0)$
(%i3) g : make_graph(20, f, directed=true)$
(%i4) out_neighbors(4, g);
(%o4)                    [8, 12, 16, 20]
(%i5) in_neighbors(18, g);
(%o5)                    [1, 2, 3, 6, 9]

Function: mycielski_graph (g): Returns the mycielskian graph of the graph g.

Function: new_graph (): Returns the graph with no vertices and no edges.

Function: path_digraph (n): Returns the directed path on n vertices.

Function: path_graph (n): Returns the path on n vertices.

Function: petersen_graph ()
Function: petersen_graph (n, d): Returns the petersen graph P_{n,d}. The default values for n and d are n=5 and d=2.

Function: random_bipartite_graph (a, b, p): Returns a random bipartite graph on a+b vertices. Each edge is present with probability p.

Function: random_digraph (n, p): Returns a random directed graph on n vertices. Each arc is present with probability p.

Function: random_regular_graph (n)
Function: random_regular_graph (n, d): Returns a random d-regular graph on n vertices. The default value for d is d=3.

Function: random_graph (n, p): Returns a random graph on n vertices. Each edge is present with probability p.

Function: random_graph1 (n, m): Returns a random graph on n vertices and random m edges.

Function: random_network (n, p, w)

Returns a random network on n vertices. Each arc is present with probability p and has a weight in the range [0,w]. The function returns a list [network, source, sink].

Example:

(%i1) load (graphs)$
(%i2) [net, s, t] : random_network(50, 0.2, 10.0);
(%o2)                   [DIGRAPH, 50, 51]
(%i3) max_flow(net, s, t)$
(%i4) first(%);
(%o4)                   27.65981397932507

Function: random_tournament (n): Returns a random tournament on n vertices.

Function: random_tree (n): Returns a random tree on n vertices.

Function: small_rhombicosidodecahedron_graph (): Returns the small rhombicosidodecahedron graph.

Function: small_rhombicuboctahedron_graph (): Returns the small rhombicuboctahedron graph.

Function: snub_cube_graph (): Returns the snub cube graph.

Function: snub_dodecahedron_graph (): Returns the snub dodecahedron graph.

Function: truncated_cube_graph (): Returns the truncated cube graph.

Function: truncated_dodecahedron_graph (): Returns the truncated dodecahedron graph.

Function: truncated_icosahedron_graph (): Returns the truncated icosahedron graph.

Function: truncated_tetrahedron_graph (): Returns the truncated tetrahedron graph.

Function: tutte_graph (): Returns the Tutte graph.

Function: underlying_graph (g): Returns the underlying graph of the directed graph g.

Function: wheel_graph (n): Returns the wheel graph on n+1 vertices.

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.2.2 Graph properties

Function: adjacency_matrix (gr)

Returns the adjacency matrix of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) c5 : cycle_graph(4)$
(%i3) adjacency_matrix(c5);
                         [ 0  1  0  1 ]
                         [            ]
                         [ 1  0  1  0 ]
(%o3)                    [            ]
                         [ 0  1  0  1 ]
                         [            ]
                         [ 1  0  1  0 ]

Function: average_degree (gr)

Returns the average degree of vertices in the graph gr.

Example:

(%i1) load (graphs)$
(%i2) average_degree(grotzch_graph());
                               40
(%o2)                          --
                               11

Function: biconected_components (gr)

Returns the (vertex sets of) 2-connected components of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g : create_graph(
            [1,2,3,4,5,6,7],
            [
             [1,2],[2,3],[2,4],[3,4],
             [4,5],[5,6],[4,6],[6,7]
            ])$
(%i3) biconnected_components(g);
(%o3)        [[6, 7], [4, 5, 6], [1, 2], [2, 3, 4]]

Function: bipartition (gr)

Returns a bipartition of the vertices of the graph gr or an empty list if gr is not bipartite.

Example:

(%i1) load (graphs)$
(%i2) h : heawood_graph()$
(%i3) [A,B]:bipartition(h);
(%o3)  [[8, 12, 6, 10, 0, 2, 4], [13, 5, 11, 7, 9, 1, 3]]
(%i4) draw_graph(h, show_vertices=A, program=circular)$

Function: chromatic_index (gr)

Returns the chromatic index of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) p : petersen_graph()$
(%i3) chromatic_index(p);
(%o3)                           4

Function: chromatic_number (gr)

Returns the chromatic number of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) chromatic_number(cycle_graph(5));
(%o2)                           3
(%i3) chromatic_number(cycle_graph(6));
(%o3)                           2

Function: clear_edge_weight (e, gr)

Removes the weight of the edge e in the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
(%i3) get_edge_weight([0,1], g);
(%o3)                          1.5
(%i4) clear_edge_weight([0,1], g)$
(%i5) get_edge_weight([0,1], g);
(%o5)                           1

Function: clear_vertex_label (v, gr)

Removes the label of the vertex v in the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
(%i3) get_vertex_label(0, g);
(%o3)                         Zero
(%i4) clear_vertex_label(0, g);
(%o4)                         done
(%i5) get_vertex_label(0, g);
(%o5)                         false

Function: connected_components (gr)

Returns the (vertex sets of) connected components of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g: graph_union(cycle_graph(5), path_graph(4))$
(%i3) connected_components(g);
(%o3)            [[1, 2, 3, 4, 0], [8, 7, 6, 5]]

Function: diameter (gr)

Returns the diameter of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) diameter(dodecahedron_graph());
(%o2)                           5

Function: edge_coloring (gr)

Returns an optimal coloring of the edges of the graph gr.

The function returns the chromatic index and a list representing the coloring of the edges of gr.

Example:

(%i1) load (graphs)$
(%i2) p : petersen_graph()$
(%i3) [ch_index, col] : edge_coloring(p);
(%o3) [4, [[[0, 5], 3], [[5, 7], 1], [[0, 1], 1], [[1, 6], 2], 
[[6, 8], 1], [[1, 2], 3], [[2, 7], 4], [[7, 9], 2], [[2, 3], 2], 
[[3, 8], 3], [[5, 8], 2], [[3, 4], 1], [[4, 9], 4], [[6, 9], 3], 
[[0, 4], 2]]]
(%i4) assoc([0,1], col);
(%o4)                           1
(%i5) assoc([0,5], col);
(%o5)                           3

Function: degree_sequence (gr)

Returns the list of vertex degrees of the graph gr.

Example:

(%i1) load (graphs)$
(%i2) degree_sequence(random_graph(10, 0.4));
(%o2)            [2, 2, 2, 2, 2, 2, 3, 3, 3, 3]

Function: edge_connectivity (gr)

Returns the edge-connectivity of the graph gr.

50.2.3 Modifying graphs

Function: add_edge (e, gr)

Adds the edge e to the graph gr.

Example:

(%i1) load (graphs)$
(%i2) p : path_graph(4)$
(%i3) neighbors(0, p);
(%o3)                          [1]
(%i4) add_edge([0,3], p);
(%o4)                         done
(%i5) neighbors(0, p);
(%o5)                        [3, 1]

Function: add_edges (e_list, gr)

Adds all edges in the list e_list to the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g : empty_graph(3)$
(%i3) add_edges([[0,1],[1,2]], g)$
(%i4) print_graph(g)$
Graph on 3 vertices with 2 edges.
Adjacencies:
  2 :  1
  1 :  2  0
  0 :  1

Function: add_vertex (v, gr)

Adds the vertex v to the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g : path_graph(2)$
(%i3) add_vertex(2, g)$
(%i4) print_graph(g)$
Graph on 3 vertices with 1 edges.
Adjacencies:
  2 :
  1 :  0
  0 :  1

Function: add_vertices (v_list, gr): Adds all vertices in the list v_list to the graph gr.

Function: connect_vertices (v_list, u_list, gr)

Connects all vertices from the list v_list with the vertices in the list u_list in the graph gr.

v_list and u_list can be single vertices or lists of vertices.

Example:

(%i1) load (graphs)$
(%i2) g : empty_graph(4)$
(%i3) connect_vertices(0, [1,2,3], g)$
(%i4) print_graph(g)$
Graph on 4 vertices with 3 edges.
Adjacencies:
  3 :  0
  2 :  0
  1 :  0
  0 :  3  2  1

Function: contract_edge (e, gr)

Contracts the edge e in the graph gr.

Example:

(%i1) load (graphs)$
(%i2) g: create_graph(
      8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
(%i3) print_graph(g)$
Graph on 8 vertices with 7 edges.
Adjacencies:
  7 :  4
  6 :  4
  5 :  4
  4 :  7  6  5  3
  3 :  4  2  1  0
  2 :  3
  1 :  3
  0 :  3
(%i4) contract_edge([3,4], g)$
(%i5) print_graph(g)$
Graph on 7 vertices with 6 edges.
Adjacencies:
  7 :  3
  6 :  3
  5 :  3
  3 :  5  6  7  2  1  0
  2 :  3
  1 :  3
  0 :  3

Function: remove_edge (e, gr)

Removes the edge e from the graph gr.

Example:

(%i1) load (graphs)$
(%i2) c3 : cycle_graph(3)$
(%i3) remove_edge([0,1], c3)$
(%i4) print_graph(c3)$
Graph on 3 vertices with 2 edges.
Adjacencies:
  2 :  0  1
  1 :  2
  0 :  2

Function: remove_vertex (v, gr): Removes the vertex v from the graph gr.

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.2.4 Reading and writing to files

Function: dimacs_export (gr, fl)
Function: dimacs_export (gr, fl, comment1, ..., commentn): Exports the graph into the file fl in the DIMACS format. Optional comments will be added to the top of the file.

Function: dimacs_import (fl): Returns the graph from file fl in the DIMACS format.

Function: graph6_decode (str): Returns the graph encoded in the graph6 format in the string str.

Function: graph6_encode (gr): Returns a string which encodes the graph gr in the graph6 format.

Function: graph6_export (gr_list, fl): Exports graphs in the list gr_list to the file fl in the graph6 format.

Function: graph6_import (fl): Returns a list of graphs from the file fl in the graph6 format.

Function: sparse6_decode (str): Returns the graph encoded in the sparse6 format in the string str.

Function: sparse6_encode (gr): Returns a string which encodes the graph gr in the sparse6 format.

Function: sparse6_export (gr_list, fl): Exports graphs in the list gr_list to the file fl in the sparse6 format.

Function: sparse6_import (fl): Returns a list of graphs from the file fl in the sparse6 format.

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

50.2.5 Visualization

Function: draw_graph (graph)

Function: draw_graph (graph, option1, ..., optionk)

Draws the graph using the draw package.

The algorithm used to position vertices is specified by the optional argument program. The default value is program=spring_embedding. draw_graph can also use the graphviz programs for positioning vertices, but graphviz must be installed separately.

Example 1:

(%i1) load (graphs)$
(%i2) g:grid_graph(10,10)$
(%i3) m:max_matching(g)$
(%i4) draw_graph(g,
   spring_embedding_depth=100,
   show_edges=m, edge_type=dots,
   vertex_size=0)$

Example 2:

(%i1) load (graphs)$
(%i2) g:create_graph(16,
    [
     [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
     [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
     [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
     [10,14],[15,14],[13,14]
    ])$
(%i3) t:minimum_spanning_tree(g)$
(%i4) draw_graph(
    g,
    show_edges=edges(t),
    show_edge_width=4,
    show_edge_color=green,
    vertex_type=filled_square,
    vertex_size=2
    )$

Example 3:

(%i1) load (graphs)$
(%i2) g:create_graph(16,
    [
     [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
     [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
     [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
     [10,14],[15,14],[13,14]
    ])$
(%i3) mi : max_independent_set(g)$
(%i4) draw_graph(
    g,
    show_vertices=mi,
    show_vertex_type=filled_up_triangle,
    show_vertex_size=2,
    edge_color=cyan,
    edge_width=3,
    show_id=true,
    text_color=brown
    )$

Example 4:

(%i1) load (graphs)$
(%i2) net : create_graph(
    [0,1,2,3,4,5],
    [
     [[0,1], 3], [[0,2], 2],
     [[1,3], 1], [[1,4], 3],
     [[2,3], 2], [[2,4], 2],
     [[4,5], 2], [[3,5], 2]
    ],
    directed=true
    )$
(%i3) draw_graph(
    net,
    show_weight=true,
    vertex_size=0,
    show_vertices=[0,5],
    show_vertex_type=filled_square,
    head_length=0.2,
    head_angle=10,
    edge_color="dark-green",
    text_color=blue
    )$

Example 5:

(%i1) load(graphs)$
(%i2) g: petersen_graph(20, 2);
(%o2)                         GRAPH
(%i3) draw_graph(g, redraw=true, program=planar_embedding);
(%o3)                         done

Example 6:

(%i1) load(graphs)$
(%i2) t: tutte_graph();
(%o2)                         GRAPH
(%i3) draw_graph(t, redraw=true, 
                    fixed_vertices=[1,2,3,4,5,6,7,8,9]);
(%o3)                         done

Option variable: draw_graph_program

Default value: spring_embedding

The default value for the program used to position vertices in draw_graph program.

draw_graph option: show_id

Default value: false

If true then ids of the vertices are displayed.

draw_graph option: show_label

Default value: false

If true then labels of the vertices are displayed.

draw_graph option: label_alignment

Default value: center

Determines how to align the labels/ids of the vertices. Can be left, center or right.

draw_graph option: show_weight

Default value: false

If true then weights of the edges are displayed.

draw_graph option: vertex_type

Default value: circle

Defines how vertices are displayed. See the point_type option for the draw package for possible values.

draw_graph option: vertex_size: The size of vertices.

draw_graph option: vertex_color: The color used for displaying vertices.

draw_graph option: show_vertices

Default value: []

Display selected vertices in the using a different color.

draw_graph option: show_vertex_type: Defines how vertices specified in show_vertices are displayed. See the point_type option for the draw package for possible values.

draw_graph option: show_vertex_size: The size of vertices in show_vertices.

draw_graph option: show_vertex_color: The color used for displaying vertices in the show_vertices list.

draw_graph option: vertex_partition

Default value: []

A partition [[v1,v2,...],...,[vk,...,vn]] of the vertices of the graph. The vertices of each list in the partition will be drawn in a different color.

draw_graph option: vertex_coloring: Specifies coloring of the vertices. The coloring col must be specified in the format as returned by vertex_coloring.

draw_graph option: edge_color: The color used for displaying edges.

draw_graph option: edge_width: The width of edges.

draw_graph option: edge_type: Defines how edges are displayed. See the line_type option for the draw package.

draw_graph option: show_edges: Display edges specified in the list e_list using a different color.

draw_graph option: show_edge_color: The color used for displaying edges in the show_edges list.

draw_graph option: show_edge_width: The width of edges in show_edges.

draw_graph option: show_edge_type: Defines how edges in show_edges are displayed. See the line_type option for the draw package.

draw_graph option: edge_partition: A partition [[e1,e2,...],...,[ek,...,em]] of edges of the graph. The edges of each list in the partition will be drawn using a different color.

draw_graph option: edge_coloring: The coloring of edges. The coloring must be specified in the format as returned by the function edge_coloring.

draw_graph option: redraw

Default value: false

If true, vertex positions are recomputed even if the positions have been saved from a previous drawing of the graph.

draw_graph option: head_angle

Default value: 15

The angle for the arrows displayed on arcs (in directed graphs).

draw_graph option: head_length

Default value: 0.1

The length for the arrows displayed on arcs (in directed graphs).

draw_graph option: spring_embedding_depth

Default value: 50

The number of iterations in the spring embedding graph drawing algorithm.

draw_graph option: terminal: The terminal used for drawing (see the terminal option in the draw package).

draw_graph option: file_name: The filename of the drawing if terminal is not screen.

draw_graph option: program: Defines the program used for positioning vertices of the graph. Can be one of the graphviz programs (dot, neato, twopi, circ, fdp), circular, spring_embedding or planar_embedding. planar_embedding is only available for 2-connected planar graphs. When program=spring_embedding, a set of vertices with fixed position can be specified with the fixed_vertices option.

draw_graph option: fixed_vertices: Specifies a list of vertices which will have positions fixed along a regular polygon. Can be used when program=spring_embedding.

Function: vertices_to_path (v_list): Converts a list v_list of vertices to a list of edges of the path defined by v_list.

Function: vertices_to_cycle (v_list): Converts a list v_list of vertices to a list of edges of the cycle defined by v_list.

[ << ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

This document was generated by Crategus on Dezember, 12 2012 using texi2html 1.76.