Trivial Graph Format
Encyclopedia
Trivial Graph Format is a simple text-based file format for describing graphs
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

. It consists of a list of node
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out 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...

 definitions, which map node IDs to labels, followed by a list of edges, which specify node pairs and an optional edge label. Node IDs can be arbitrary identifiers, whereas labels for both nodes and edges are plain strings.

The graph may be interpreted as a directed or undirected graph. For directed graphs, to specify the concept of bidirectionality in an edge, one may either specify two edges (forward and back), or differentiate the edge by means of a label. For more powerful specification of graphs, see the other graph file formats below.

Example

A simple graph with 2 nodes and 1 edge might look like this:

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

Ease of use

TGF is useful for easily importing arbitrary data into a graph manipulation tool such as yEd
YEd
yEd is a freely available, general-purpose diagramming software with amulti-document interface.It is a cross-platform application written in Java that runs on Windows, Linux, Mac OS, or any platform that supports the JVM....

. Because of the simplicity of the format, it is straightforward to use small programs or scripts to convert domain-specific data to this general format. For example, given a Makefile like this:


myprogram: myprogram.o libmytools.so
gcc -L. -lmylib -o $@ $<

myprogram.o: myprogram.c
gcc -c -o $@ $<

libmytools.so: mytools1.o mytools2.o
gcc -shared -o $@ $<

mytools1.o: mytools1.c
gcc -c -o $@ $<

mytools2.o: mytools2.c
gcc -c -o $@ $<

clean:
rm myprogram myprogram.o libmytools.so mytools1.o mytools2.o


It is possible to use a simple script, such as the following Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 program, to turn the Makefile dependencies into TGF output:
  1. !/usr/bin/python


import fileinput, re

depends = {}
for line in fileinput.input:
m = re.match('(.+):\s*(.*)',line) # find every depenency line of the form ": "
if m:
item = m.group(1)
dependency_list = m.group(2)
print item,item # node definition

if dependency_list: # there are dependencies
depends[item] = dependency_list.split # store the list into a dictionary for later

print "#" # end of node list, start of edge list

for item in depends:
for dependency in depends[item]:
print item,dependency # edge definition


This will produce a TGF graph which can then be visualized and analyzed using a graph manipulation tool. The above content yields the following graph:

Other Graph File Formats

  • DOT language
    DOT language
    DOT is a plain text graph description language. It is a simple way of describing graphs that both humans and computer programs can use. DOT graphs are typically files that end with the .gv extension. The .gv extension is preferred, as .dot also is used by Microsoft Office 2003.Various programs...

    , a plain text graph description language -- Graphviz
  • GraphML
    GraphML
    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...

    , a graph exchange format based on XML -- GraphML
  • GXL
    GXL
    GXL is designed to be a standard exchange format for graphs. GXL is an extensible markup language sublanguage and the syntax is given by an XML document type definition...

    , another graph exchange format based on XML -- GXL
  • GML
    Graph Modelling Language
    Graph Modelling Language is a hierarchical ASCII-based file format for describing graphs. It has been also named Graph Meta Language.-Example:A simple graph in GML format:graph [ comment "This is a sample graph" directed 1 id 42...

     is another widely used graph exchange format. -- GML
  • XGMML
    XGMML
    XGMML is an XML application based on GML which is used for graph description...

     an XML-based graph markup language closely related to GML
    GML
    GML may refer to:* Middle Low German , a language used around the North Sea and the Baltic Sea from 1100 to 1600* Gostomel Airport , an international cargo airport, near Kiev, Ukraine* Gradient Multi-Layer nano-film...

    -- XGMML

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK