Trivial Graph Format

Last updated

Trivial Graph Format (TGF) is a simple text-based adjacency list file format for describing graphs, [1] widely used because of its simplicity. [2]

Contents

Format

The format consists of a list of node definitions, which map node IDs to labels, followed by a list of edges, which specify node pairs and an optional edge label. Because of its lack of standardization, the format has many variations. [1] For instance, some implementations of the format require the node IDs to be integers, [3] while others allow more general alphanumeric identifiers.

Each node definition is a single line of text starting with the node ID, separated by a space from its label. The node definitions are separated from the edge definitions by a line containing the "#" character. Each edge definition is another line of text, starting with the two IDs for the endpoints of the edge separated by a space. If the edge has a label, it appears on the same line after the endpoint IDs. [3]

The graph may be interpreted as a directed or undirected graph. For directed graphs, to specify the concept of bi-directionality in an edge, one may either specify two edges (forward and back) or differentiate the edge by means of a label.

Example

A simple graph with two nodes and one edge might look like:

1 First node 2 Second node # 1 2 Edge between the two 

See also

Related Research Articles

Graph theory Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Tree (data structure) Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Bipartite graph Graph in which every vertex is connected to at least one other

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph (discrete mathematics) Mathematical structure consisting of vertices and edges connecting some pairs of vertices

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

YAML Human-readable data serialization format

YAML is a human-readable data-serialization language. It is commonly used for configuration files and in applications where data is being stored or transmitted. YAML targets many of the same communications applications as Extensible Markup Language (XML) but has a minimal syntax which intentionally differs from SGML. It uses both Python-style indentation to indicate nesting, and a more compact format that uses [...] for lists and {...} for maps so that JSON files are valid YAML 1.2.

Adjacency list Data structure representing a graph

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

A comma-separated values (CSV) file is a delimited text file that uses a comma to separate values. Each line of the file is a data record. Each record consists of one or more fields, separated by commas. The use of the comma as a field separator is the source of the name for this file format. A CSV file typically stores tabular data in plain text, in which case each line will have the same number of fields.

DOT is a graph description language. DOT graphs are typically files with the filename extension gv or dot. The extension gv is preferred, to avoid confusion with the extension dot used by versions of Microsoft Word before 2007.

Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

Bridge (graph theory) Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Connectivity (graph theory) Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

Multigraph

In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

Graph Modeling Language (GML) is a hierarchical ASCII-based file format for describing graphs. It has been also named Graph Meta Language.

GraphML is an XML-based file format for graphs. The GraphML file format results from the joint effort of the graph drawing community to define a common format for exchanging graph structure data. It uses an XML-based syntax and supports the entire range of possible graph structure constellations including directed, undirected, mixed graphs, hypergraphs, and application-specific attributes.

PLY (file format)

PLY is a computer file format known as the Polygon File Format or the Stanford Triangle Format. It was principally designed to store three-dimensional data from 3D scanners. The data storage format supports a relatively simple description of a single object as a list of nominally flat polygons. A variety of properties can be stored, including: color and transparency, surface normals, texture coordinates and data confidence values. The format permits one to have different properties for the front and back of a polygon. There are two versions of the file format, one in ASCII, the other in binary.

SPQR tree

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

Two-dimensional space Geometric model of the planar projection of the physical universe

Two-dimensional space is a geometric setting in which two values are required to determine the position of an element. The set 2 of pairs of real numbers with appropriate structure often serves as the canonical example of a two-dimensional Euclidean space. For a generalization of the concept, see dimension.

Directed graph Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges often called arcs.

References

  1. 1 2 Roughan, Matthew; Tuke, Jonathan (August 2015), "The Hitchhikers Guide to Sharing Graph Data" (PDF), 2015 3rd International Conference on Future Internet of Things and Cloud, IEEE, doi:10.1109/ficloud.2015.76
  2. Pitas, Ioannis (2016), "1.5 Graph storage formats and visualization", Graph-Based Social Media Analysis, Chapman & Hall/CRC Data Mining and Knowledge Discovery Series, 39, CRC Press, p. 14, ISBN   9781498719056
  3. 1 2 Canabrava, Tomaz; Cord-Landwehr, Andreas (April 10, 2016), "Chapter 4. Import and Export", The Rocs Handbook, Revision Rocs 2.1.50 (Applications 16.04)