Network Graph Toolkit

The NGraph Toolkit consists of over thirty programs, filters, and scripts for the analysis of large networks represented as mathematical graphs. These are stand-alone programs written in C++, C shell, and Bash scripts. The core algorithms are provided by the NGraph C++ library, which is used to build some of the following applications:

• adj2g.cc: convert free form adjacency list to graph (.g) file
• adjm2g.cc: convert multi-line adjacency list to graph (.g) file
• annotate_groups.cc : replace integer in .group files with vertex labels (.v)
• cg2savg.cc: convert 3D coordinate file (.crd) and a graph (.g) file to a SAVG file
• g2adj: convert graph file (.g) into a adjacency file, each node and neighbors on same line
• g2madj: convert graph file (.g) into a multi-line adjacency file
• g2dccf.cc [-u]: list degree (in & out) and clustering coefficient for each vertex
• g2degree.cc [-u]: list degree (in & out) for each vertex
• g2dot.c: convert graph (.g) file to (directed) GraphViz format (.dot)
• g2mtx.cc [-u]: convert graph (.g) file into (symmetric) Matrix Market format
• g2vertices.cc : counts the number of distinct nodes in a (integer) graph
• gprune.cc (removes terminal branches form directed graph)
• g2udot.cc: convert graph (.g) file to (undirected) GraphViz format (.dot)
• g2ug.cc : converted directed graph to (compact) undirected graph (.g) file
• g2ug.csh : script to convert multiple graph files
• gi2g1.cc: convert integer graph to contiguous 1-based integer (.g) file
• graph_summary.cc: prints out degree correlation and clustering coefficient for (.g) files
• graph_summary.csh: script for processing multiple graph files
• gs2g1.cc: convert string graph to contiguous 1-based integer (.g) file
• gtranspose: reverse edge directions on graph (.g) file
• gu2dot.c: convert graph (.g) file to (undirected) GraphViz format (.dot)
• mmio.c/mmio.h: Matrix Market I/O functions (used by g2mtx, mtx2g)
• mtx2g .c: convert Matrix Market format into graph (.g) file
• mtx2g.csh : script to process multiple mtx files
• q2g.cc [-u] : convert clique graph (one per line format, .q) into a [undirected] graph (.g) file
• subgraph.cc: given a .g graph and a vertex (subset), return the subgraph formed
• symm_diff.cc : find (word-wise) symmetric difference of two text files
• symm_diff_line.cc : find (line-wise) symmetric difference of two text files
• token.hpp : class to dispense tokens from a given string (used by adj2g, adjm2g, q2g)
• url_index : creates a list of urls, given a graph (.g) file and a URL (.t) file
• d2dd: takes a degree list and creates a discrete distribution file (.dd)

File extensions

• (d|u) : directed / undirected
• .gv : vertex list
• .ge : edge list
• .gr : degree
• .grb : degree distribution
• .gf : clustering coeff
• .go : correlation

Graph formats

• *.g : simple (edge-list) format (.g, .gu, .gd) of non-negative integer vertices
• *.gs : text (string) edge-list graph format
• *.dot : GraphViz format
• *.adj : adjacency list format (vertex and neighbors on one line)
• *.mtx: Matrix Market sparse matrix (adjacency matrix) format
• *.net : Pajek format
• *.gdf : Guess format
• *.graphml : GraphML format

Graph File extensions

• [a] : annotated (nodes or edges have optional ':' followed by generic string)
• (u|d) : undirected / directied
• (i | s) : unsigned integer / string
• (0|1) : 0-based / 1-based

• *.g : edge-list graph format (assumes no loops, multiple edges, or isolated vertices)
• *.g1 : graph with contiguous 1-based vertices
• *.g0 : graph with contiguous 0-based vertices
• *.gu : undirected (compact) graph
• *.gd: directed graph
• *.gv : vertex list (one per line: node name, with optional attributes)
• *.gr : vertex and degree (undirected)
• *.gdr : vertex and degree in, out (directed)
• *.cf : clustering coefficients

We would appreciate acknowledgement if the software is incorporated in redistributable libraries or applications.

• NGraph: Network Graph Toolkit
  • C++ source code: ngraph_toolkit_4_5.zip (9 KB)

Roldan Pozo