graph-tool

#! /usr/bin/env python
# (C) 2006 by Tiago de Paula Peixoto <tiago@forked.de>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Library General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA

import sys

sys.path.append(".")

from libgraph_tool import *

from optparse import *
import os
import os.path
import re
import struct
import fcntl
import termios
import gzip
import bz2
import string
import time
import signal
from time import *

from math import *
try:
    from scipy import *
    from scipy.special import *
    from scipy.optimize import *
    from scipy.optimize.minpack import *
except ImportError:
    pass


#import gc # garbage collector
#gc.enable()
#gc.set_debug(gc.DEBUG_LEAK|gc.DEBUG_STATS)

prog_info = mod_info()
version_string = "%s %s\nWritten by %s\n\n%s" % (prog_info.name, prog_info.version, \
                                               prog_info.author,prog_info.copyright)

def getheightwidth():
    height, width = 20, 80
    try:
        height, width = struct.unpack("hhhh", fcntl.ioctl(0, termios.TIOCGWINSZ ,"\000"*8))[0:2]
    except IOError:
        pass
    return height, width

option_list = list()
class Opt:
    def __init__(self, name, value):
        self.name = name
        self.value = value

def push_option(option, opt_str, value, parser):
    option_list.append(Opt(opt_str.lstrip("--"), value))

parser = OptionParser(usage="%s [options]" % sys.argv[0], version=version_string, \
                      formatter=IndentedHelpFormatter(max_help_position=getheightwidth()[1]/2,width=getheightwidth()[1]))
basic =  parser.add_option_group("Basic options")
basic.add_option("--load", action="callback", callback=push_option, type="string", metavar="FILE", help="load graph from file")
basic.add_option("--save", action="callback", callback=push_option, type="string", metavar="FILE", help="save graph to file")

generation =  parser.add_option_group("Graph generation")
generation.add_option("--correlated-configurational-model", action="callback", type="string", metavar="OPTIONS", callback=push_option, help="generate graph using the configurational model with arbitrary degree correlations. Options are: N, pjk, pjk_ceil, pjk_m, inv_pjk_ceil, corr, corr_ceil, corr_m, inv_corr_ceil, undirected, directed, progress, seed. See documentation for details.")

filtering =  parser.add_option_group("Filtering")
filtering.add_option("--directed", action="callback", callback=push_option, help="treat graph as directed (default)")
filtering.add_option("--undirected", action="callback", callback=push_option, help="treat graph as undirected")
filtering.add_option("--reverse", action="callback", callback=push_option, help="reverse edges")
filtering.add_option("--vertex-filter", action="callback", callback=push_option, type="string", metavar="FILTER RULE", help="set generic vertex filter")
filtering.add_option("--vertex-range-filter", action="callback", callback=push_option, type="string", metavar="PROPERTY|RANGE", help="choose vertex property and range to filter")
filtering.add_option("--reset-vertex-filter", action="callback", callback=push_option, help="remove edge filter")
filtering.add_option("--edge-filter", action="callback", callback=push_option, type="string", metavar="FILTER RULE", help="set generic edge filter")
filtering.add_option("--edge-range-filter", action="callback", callback=push_option, type="string", metavar="PROPERTY|RANGE", help="choose edge property and range to filter")
filtering.add_option("--reset-edge-filter", action="callback", callback=push_option, help="remove edge filter")

modification =  parser.add_option_group("Graph Modification")
modification.add_option("--edit-vertex-property", action="callback", callback=push_option, type="string", metavar="PROPERTY|EXPRESSION", help="edit the selected vertex property")
modification.add_option("--edit-edge-property", action="callback", callback=push_option, type="string", metavar="PROPERTY|EXPRESSION", help="edit the selected edge property")
modification.add_option("--remove-vertex-property", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="remove vertex property from graph")
modification.add_option("--remove-edge-property", action="callback", callback=push_option, type="string", metavar="PROPERTY|RANGE", help="remove edge property from graph")
modification.add_option("--insert-vertex-index-property", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="insert vertex index as property")
modification.add_option("--insert-edge-index-property", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="insert edge index as property")

statistics =  parser.add_option_group("Basic Statistics")
statistics.add_option("--number-of-vertices", action="callback", callback=push_option, type="string", metavar="FILE", help="get the number of vertices")
statistics.add_option("--number-of-edges", action="callback", callback=push_option, type="string", metavar="FILE", help="get the number of edges")
statistics.add_option("--vertex-histogram", action="callback", callback=push_option, type="string", metavar="DEGREE|FILE", help="get the vertex degree/property histogram")
statistics.add_option("--edge-histogram", action="callback", callback=push_option, type="string", metavar="PROPERTY|FILE", help="get the edge property histogram")
statistics.add_option("--combined-vertex-histogram", action="callback", callback=push_option, type="string", metavar="DEGREE1|DEGREE2|FILE", help="get the combined (DEGREE1,DEGREE2) histogram. Scalar properties are also accepted as DEGREE1 or DEGREE2")
statistics.add_option("--distance-histogram", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]FILE", help="get the distance histogram")
statistics.add_option("--average-distance", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]FILE", help="get the averarge distance")
statistics.add_option("--average-harmonic-distance", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]FILE", help="get the averarge harmonic distance")
statistics.add_option("--sampled-distance-histogram", action="callback", callback=push_option, type="string", metavar="OPTIONS|FILE", help="get the sampled distance histogram. Options are samples, weight (optional), seed (default: from clock)")
statistics.add_option("--average-sampled-distance", action="callback", callback=push_option, type="string", metavar="OPTIONS|FILE", help="get the average sampled distance. Options are samples, weight (optional), seed (default: from clock)")
statistics.add_option("--average-sampled-harmonic-distance", action="callback", callback=push_option, type="string", metavar="OPTIONS|FILE", help="get the average sampled harmonic distance. Options are samples, weight (optional), seed (default: from clock)")
statistics.add_option("--label-components", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="label components to PROPERTY")
statistics.add_option("--label-parallel-edges", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="label parallel edges to PROPERTY")
statistics.add_option("--average-vertex-property", action="callback", callback=push_option, type="string", metavar="PROPERTY|FILE", help="get the average of the vertex property")
statistics.add_option("--average-edge-property", action="callback", callback=push_option, type="string", metavar="PROPERTY|FILE", help="get the average of the edge property")
statistics.add_option("--reciprocity", action="callback", callback=push_option, type="string", metavar="FILE", help="get the edge reciprocity")
statistics.add_option("--minimum-spanning-tree", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]PROPERTY", help="mark the minimum spanning tree edges in PROPERTY")
statistics.add_option("--line-graph", action="callback", callback=push_option, type="string", metavar="FILE[|FORMAT]", help="save the corresponding line graph to FILE")

correlations =  parser.add_option_group("Correlations")
correlations.add_option("--average-combined-vertex-correlation", action="callback", callback=push_option, type="string", metavar="DEGREE1|DEGREE2|FILE", help="get the average of DEGREE2 in function of DEGREE1. Scalar properties are also accepted as DEGREE1 or DEGREE2")
correlations.add_option("--vertex-correlation-histogram", action="callback", callback=push_option, type="string", metavar="DEGREE1|DEGREE2[|WEIGHT]|FILE", help="get the degree correlation histogram. Scalar properties are also accepted in place of DEGREE. An optional edge weight property can be passed by WEIGHT")
correlations.add_option("--average-nearest-neighbours-correlation", action="callback", callback=push_option, type="string", metavar="ORIGIN-DEGREE|DEGREE[|WEIGHT]|FILE", help="get the average nearest neighbours correlation. An optional edge weight property can be passed by WEIGHT")
correlations.add_option("--edge-vertex-correlation-histogram", action="callback", callback=push_option, type="string", metavar="DEGREE1|EDGE-PROP|DEGREE2|FILE", help="get the source degree vs. edge scalar vs. target degree correlation histogram. Scalar properties are also accepted in place of DEGREE-TYPE")
correlations.add_option("--assortativity-coefficient", action="callback", callback=push_option, type="string", metavar="DEGREE|FILE", help="get the assortativity coefficient. Scalar properties are also accepted in place of DEGREE")
correlations.add_option("--scalar-assortativity-coefficient", action="callback", callback=push_option, type="string", metavar="DEGREE|FILE", help="get the scalar assortativity coefficient. Scalar properties are also accepted in place of DEGREE")

clustering =  parser.add_option_group("Clustering")
clustering.add_option("--set-local-clustering-to-property", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="set the local clustering coefficient to vertex property")
clustering.add_option("--global-clustering-coefficient", action="callback", callback=push_option, type="string", metavar="FILE", help="get the global clustering coefficient")
clustering.add_option("--set-extended-clustering-to-property", action="callback", callback=push_option, type="string", metavar="PREFIX|MAX", help="set the extended clustering coefficients c1 to cMAX to vertex properties PREFIX1 to PREFIXMAX")

layout =  parser.add_option_group("Layout")
layout.add_option("--compute-spring-block-layout", action="callback", callback=push_option, type="string", metavar="ITERATIONS[|SEED]", help="compute the spring block layout")
layout.add_option("--compute-gursoy-atun-layout", action="callback", callback=push_option, type="string", metavar="ITERATIONS[|SEED]", help="compute the Gursoy-Atun layout")

community =  parser.add_option_group("Community")
community.add_option("--community-structure", action="callback", callback=push_option, type="string", metavar="PROPERTY|OPTIONS", help="calculate the community structure and assign it to PROPERTY. Options are: g (default: 1.0), N (default: 1000), Tmin (default: 0.01), Tmax (default: 1.0), spins (default: number of vertices), corr_type (default: uncorrelated), weight, seed (default: from clock), verbose, history.  The value of corr_type can be 'random', 'uncorrelated' or 'correlated'.")
community.add_option("--modularity", action="callback", callback=push_option, type="string", metavar="PROPERTY[|WEIGHT]|FILE", help="calculate the modularity, given a community partition specified by PROPERTY")
community.add_option("--community-graph", action="callback", callback=push_option, type="string", metavar="PROPERTY|FILE[|FORMAT]", help="obtain the graph of communities, given a community partition specified by PROPERTY")

layout =  parser.add_option_group("History")
layout.add_option("--for", action="callback", callback=push_option, type="string", metavar="INIT|CONDITION|STEP", help="simplified scripting")
layout.add_option("--history", action="callback", callback=push_option, type="string", metavar="INIT|CONDITION|STEP", help="simplified scripting (does not overwrite previous results)")
layout.add_option("--refresh-rate", type="string", metavar="TIME", default="1h", help="for/history files refresh rate")

try:
    import optcomplete
    optcomplete.autocomplete(parser)
except ImportError:
    pass

(options, args) = parser.parse_args()

graph = GraphInterface()

def parse_values(value):
    "this will parse the options with multiple values"
    p = re.compile(r"([^\|'\"]+|[^\|]+'[^']*'[^\|'\"]+|[^\|]+\"[^\"]*\")(?:\||$)")
    values = p.findall(value)
    values = [x.strip() for x in values]
    return values

def get_suboption(suboption, string):
    p = re.compile(r"([^,'\"]+|[^,]+'[^']*'|[^,]+\"[^\"]*\")(?:,|$)")
    opts = p.findall(string)
    for opt in opts:
        if opt.split("=",1)[0].strip() == suboption:
            if "=" in opt:            
                return opt.split("=",1)[1].strip("\"").strip("'")
            else:
                return True
    return False

def degree(name):
    "this will retrieve the degree type from string"
    deg = name
    if name == "in-degree" or name == "in":
        deg = Degree.In
    if name == "out-degree" or name == "out":
        deg = Degree.Out
    if name == "total-degree" or name == "total":
        deg = Degree.Total
    return deg

def get_mean(hist):
    avg,dev,count = 0.0,0.0,0.0
    try:
        for k,v in hist.iteritems():
            avg += k*v
            count += v
        avg /= count
        for k,v in hist.iteritems():
            dev += (k - avg)**2
        dev = sqrt(dev/(count**2))
    except ZeroDivisionError:
        avg = dev = float("nan") # nans are ok, since graph can be empty
    return (avg,dev)

class OptionError(Exception):
    def __init__(self, option, error):
        self.what = "error parsing option %s: %s" % (option,error)
    def __str__(self):
        return self.what

def generate_graph(parameters):
    "this option will generate a graph with the given parameters"
    seed = int(time())
    N = 10000
    pjk = "1.0"
    pjk_ceil = "pjk(j,k)"
    m_pjk = "1.0"
    inv_pjk_ceil = ""
    corr = "1.0"
    corr_ceil = "corr(jl,kl,j,k)"
    m_corr = "1.0"
    inv_corr_ceil = "inv_pjk_ceil(p,r)"
    try:
        if get_suboption("N",parameters) != False:
            N = int(get_suboption("N",parameters))
        if get_suboption("pjk",parameters) != False:
            pjk = get_suboption("pjk",parameters)
            corr = "pjk(j,k)"
        if get_suboption("pjk_ceil",parameters) != False:
            pjk_ceil = get_suboption("pjk_ceil",parameters)
        if get_suboption("pjk_m",parameters) != False:
            m_pjk = get_suboption("pjk_m",parameters)
            m_corr = m_pjk
        if get_suboption("inv_pjk_ceil",parameters) != False:
            inv_pjk_ceil = get_suboption("inv_pjk_ceil",parameters)
        if get_suboption("corr",parameters) != False:
            corr = get_suboption("corr",parameters)
        if get_suboption("corr_ceil",parameters) != False:
            corr_ceil = get_suboption("corr_ceil",parameters)
        if get_suboption("corr_m",parameters) != False:
            corr_m = get_suboption("corr_m",parameters)
        if get_suboption("inv_corr_ceil",parameters) != False:
            inv_corr_ceil = get_suboption("inv_corr_ceil",parameters)            
        undirected = get_suboption("undirected",parameters)
        verbose = get_suboption("progress", parameters)
        if get_suboption("seed",parameters) != False:
            seed = int(get_suboption("seed",parameters))
    except ValueError, e:
        raise OptionError(opt.name, e)

    # some predefined functions
    variables = globals()
    
    def inv_poisson(p,m):
        return round(fsolve(lambda k,l: gammaincc(k,l)-p, m, (m))-0.5+1e-15)
    variables["inv_poisson"] = inv_poisson
    
    def inv_exponential(p,m):
        return round(log(1-p)/log(float(m)/(m+1))-0.5+1e-15)
    variables["inv_exponential"] = inv_exponential
    
    def inv_power_law(p,b):
        return round((1-p)**(-1/(b-1)) - 1)
    variables["inv_power_law"] = inv_power_law
    
    def step(x):
        if x >= 0:
            return 1.0
        else:
            return 0.0
    variables["step"] = step

    # read main funtions
    def pjk_f(j,k):
        return eval("%s" % pjk, variables, locals())
    variables["pjk"] = pjk_f
    
    def pjk_ceil_f(j,k):
        return eval("%s" % pjk_ceil, variables, locals())
    variables["pjk_ceil"] = pjk_ceil_f

    m_pjk = float(m_pjk)
    variables["m_pjk"] = m_pjk
    
    if "file:" in inv_pjk_ceil:
        exec open(inv_pjk_ceil.replace("file:","").strip()).read() in variables
    else:
        def inv_pjk_ceil_f(p,r):
            variables["p"] = p
            variables["r"] = r
            retval = eval("%s" % inv_pjk_ceil, variables, locals())
            del(variables["p"])
            del(variables["r"])
            return (int(round(retval[0])), int(round(retval[1])))
        variables["inv_pjk_ceil"] = inv_pjk_ceil_f
        
    def corr_f(jl,kl,j,k):
        return eval("%s" % corr, variables, locals())
    variables["corr"] = corr_f
    
    def corr_ceil_f(jl,kl,j,k):
        return eval("%s" % corr_ceil, variables, locals())
    variables["corr_ceil"] = corr_ceil_f
    
    m_corr = float(m_corr)
    variables["m_corr"] = m_corr
        
    if "file:" in inv_corr_ceil:
        exec open(inv_corr_ceil.replace("file:","").strip()).read() in variables
    else:
        def inv_corr_ceil_f(p,r,j,k):
            retval = eval("%s" % inv_corr_ceil, variables, locals())
            return (int(round(retval[0])), int(round(retval[1])))
        variables["inv_corr_ceil"] = inv_corr_ceil_f

    graph.GenerateCorrelatedConfigurationalModel(N, variables["pjk"], variables["pjk_ceil"], variables["inv_pjk_ceil"], m_pjk, variables["corr"],
                                                 variables["corr_ceil"], variables["inv_corr_ceil"], m_corr, undirected, seed, verbose)


def parse_option(opt, just_file=False):
    "this will execute an option, and return either None, or a tuple with the result and the respective file name, if it exists"
    if opt.name == "load":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '$s'" % opt.value)
        if just_file:
            return None
        if len(values) == 1:
            graph.ReadFromFile(values[0])
        else:
            graph.ReadFromFile(values[0], values[1])
    elif opt.name == "save":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '$s'" % opt.value)
        if just_file:
            return None
        if len(values) == 1:
            graph.WriteToFile(values[0])
        else:
            graph.WriteToFile(values[0], values[1])
    elif opt.name == "correlated-configurational-model":
        if just_file:
            return None
        generate_graph(opt.value)
    elif opt.name == "number-of-vertices":
        if just_file:
            return opt.value
        return (graph.GetNumberOfVertices(), opt.value)
    elif opt.name == "number-of-edges":
        if just_file:
            return opt.value
        return (graph.GetNumberOfEdges(), opt.value)
    elif opt.name == "combined-vertex-histogram":
        values = parse_values(opt.value)
        if len(values) != 3:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return values[2]
        return (graph.GetCombinedVertexHistogram(degree(values[0]),degree(values[1])), values[2])
    elif opt.name == "average-combined-vertex-correlation":
        values = parse_values(opt.value)
        if len(values) != 3:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return values[2]
        return (graph.GetAverageCombinedVertexCorrelation(degree(values[0]),degree(values[1])), values[2])
    elif opt.name == "distance-histogram":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        file_name, weight = values[0],""
        if len(values) > 1:
            weight = values[0]
            file_name = values[1]
        if just_file:
            return file_name
        return (graph.GetDistanceHistogram(weight), file_name)
    elif opt.name == "average-distance":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        file_name, weight = values[0],""
        if len(values) > 1:
            weight = values[0]
            file_name = values[1]
        if just_file:
            return file_name
        return ("%f\t%f" % get_mean(graph.GetDistanceHistogram(weight)), file_name)
    elif opt.name == "average-harmonic-distance":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        file_name, weight = values[0],""
        if len(values) > 1:
            weight = values[0]
            file_name = values[1]
        if just_file:
            return file_name
        hist = graph.GetDistanceHistogram(weight)
        avg, err = get_mean(dict((1.0/k,v) for k,v in hist.iteritems()))
        return ("%f\t%f" % (1.0/avg,err/(avg**2)) , file_name)
    elif opt.name == "sampled-distance-histogram":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if get_suboption("weight", values[0]) != False:
            weight = get_suboption("weight", values[0])
        else:
            weight = ""
        if get_suboption("samples", values[0]) != False:
            samples = int(get_suboption("samples", values[0]))
        else:
            raise OptionError(opt.name, "you must provide the number of samples")
        if get_suboption("seed", values[0]) != False:
            seed = int(get_suboption("seed", values[0]))
        else:
            seed = int(time())
        if just_file:
            return values[1]
        return (graph.GetSampledDistanceHistogram(weight, samples, seed), values[1])
    elif opt.name == "average-sampled-distance":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if get_suboption("weight", values[0]) != False:
            weight = get_suboption("weight", values[0])
        else:
            weight = ""
        if get_suboption("samples", values[0]) != False:
            samples = int(get_suboption("samples", values[0]))
        else:
            raise OptionError(opt.name, "you must provide the number of samples")
        if get_suboption("seed", values[0]) != False:
            seed = int(get_suboption("seed", values[0]))
        else:
            seed = int(time())
        if just_file:
            return values[1]
        return ("%f\t%f" % get_mean(graph.GetSampledDistanceHistogram(weight, samples, seed)), values[1])
    elif opt.name == "average-sampled-harmonic-distance":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if get_suboption("weight", values[0]) != False:
            weight = get_suboption("weight", values[0])
        else:
            weight = ""
        if get_suboption("samples", values[0]) != False:
            samples = int(get_suboption("samples", values[0]))
        else:
            raise OptionError(opt.name, "you must provide the number of samples")
        if get_suboption("seed", values[0]) != False:
            seed = int(get_suboption("seed", values[0]))
        else:
            seed = int(time())
        if just_file:
            return values[1]
        hist = graph.GetSampledDistanceHistogram(weight, samples, seed)
        avg, err = get_mean(dict((1.0/k,v) for k,v in hist.iteritems()))
        return ("%f\t%f" % (1.0/avg,1.0/err) , values[1])
    elif opt.name == "label-components":
        if just_file:
            return
        graph.LabelComponents(opt.value)
    elif opt.name == "label-parallel-edges":
        if just_file:
            return
        graph.LabelParallelEdges(opt.value)
    elif opt.name == "vertex-histogram":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg = degree(values[0])
        if just_file:
            return values[1]
        return (graph.GetVertexHistogram(deg), values[1])
    elif opt.name == "edge-histogram":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return values[1]
        return (graph.GetEdgeHistogram(values[0]), values[1])
    elif opt.name == "reciprocity":
        if just_file:
            return opt.value
        return (graph.GetReciprocity(), opt.value)
    elif opt.name == "minimum-spanning-tree":
        values = parse_values(opt.value)
        if len(values) > 2 or len(values) < 1:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return None
        prop, weight = values[0],""
        if len(values) > 1:
            weight = values[0]
            prop = values[1]
        graph.GetMinimumSpanningTree(weight,prop)
    elif opt.name == "line-graph":
        values = parse_values(opt.value)
        if len(values) < 1 or len(values) > 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return None
        if len(values) > 1:
            format = values[1]
        else:
            format = ""
        graph.GetLineGraph(values[0], format)
    elif opt.name == "vertex-correlation-histogram":
        values = parse_values(opt.value)
        if len(values) < 3 or len(values) > 4:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg1 = degree(values[0])
        deg2 = degree(values[1])
        if len(values) == 4:
            weight = values[2]
            file_name = values[3]
        else:
            weight = ""
            file_name = values[2]
        if just_file:
            return file_name
        return (graph.GetVertexCorrelationHistogram(deg1, deg2, weight), file_name)
    elif opt.name == "edge-vertex-correlation-histogram":
        values = parse_values(opt.value)
        if len(values) != 4:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg1 = degree(values[0])
        deg2 = degree(values[2])
        if just_file:
            return values[3]
        return (graph.GetEdgeVertexCorrelationHistogram(deg1,values[1],deg2), values[3])
    elif opt.name == "average-nearest-neighbours-correlation":
        values = parse_values(opt.value)
        if len(values) < 3 or len(values) > 4:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg1 = degree(values[0])
        deg2 = degree(values[1])
        if len(values) == 4:
            weight = values[2]
            file_name = values[3]
        else:
            weight = ""
            file_name = values[2]
        if just_file:
            return file_name
        return (graph.GetAverageNearestNeighboursCorrelation(deg1, deg2, weight), file_name)
    elif opt.name == "assortativity-coefficient":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg = degree(values[0])
        if just_file:
            return values[1]
        (r,err) = graph.GetAssortativityCoefficient(deg)
        ret = "%f\t%f" % (r,err)
        return (ret, values[1])
    elif opt.name == "scalar-assortativity-coefficient":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        deg = degree(values[0])
        if just_file:
            return values[1]
        (r,err) = graph.GetScalarAssortativityCoefficient(deg)
        ret = "%f\t%f" % (r,err)
        return (ret, values[1])
    elif opt.name == "average-vertex-property" or opt.name == "average-edge-property":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if opt.name == "average-vertex-property":
            deg = degree(values[0])
            hist = graph.GetVertexHistogram(deg)
        else:
            hist = graph.GetEdgeHistogram(values[0])
        ret = "%f\t%f" % get_mean(hist)
        if just_file:
            return values[1]
        return (ret,values[1])
    elif opt.name == "global-clustering-coefficient":
        if just_file:
            return opt.value
        (avg, dev) = graph.GetGlobalClustering()
        ret = "%f\t%f" % (avg, dev)
        return (ret, opt.value)
    elif opt.name == "set-local-clustering-to-property":
        if just_file:
            return None
        graph.SetLocalClusteringToProperty(opt.value)
    elif opt.name == "set-extended-clustering-to-property":
        if just_file:
            return None
        values = parse_values(opt.value)
        if len(values) == 0 or len(values) > 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        graph.SetExtendedClusteringToProperty(values[0],int(values[1]))
    elif opt.name == "community-structure":
        if just_file:
            return None
        values = parse_values(opt.value)
        if len(values) < 1 or len(values) > 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        prop = values[0]
        if len(values) > 1:
            param = values[1]
        else:
            param = ""
        try:
            if  get_suboption("g", param) != False:
                g = float( get_suboption("g", param))
            else:
                g = 1.0
            if  get_suboption("N", param) != False:
                N = int( get_suboption("N", param))
            else:
                N = 1000
            if  get_suboption("Tmin", param) != False:
                Tmin = float( get_suboption("Tmin", param))
            else:
                Tmin = 0.0
            if  get_suboption("Tmax", param) != False:
                Tmax = float( get_suboption("Tmax", param))
            else:
                Tmax = 100.0
            if  get_suboption("spins", param) != False:
                spins = int( get_suboption("spins", param))
            else:
                spins = 0
            if  get_suboption("corr_type", param) != False:
                if  get_suboption("corr_type", param)  == "random":
                    corr = CommCorr.ErdosReyni
                elif  get_suboption("corr_type", param)  == "uncorrelated":
                    corr = CommCorr.Uncorrelated
                elif  get_suboption("corr_type", param)  == "correlated":
                    corr = CommCorr.Correlated
                else:
                    raise OptionError(opt.name, "invalid correlation type value '%s'" %  get_suboption("corr_type", param) )
            else:
                corr = CommCorr.Uncorrelated
            if  get_suboption("seed", param) != False:
                seed = int( get_suboption("seed", param))
            else:
                seed = int(clock())
            if  get_suboption("weight", param) != False:
                weight =  get_suboption("weight", param)
            else:
                weight = ""
            verbose =  get_suboption("verbose", param) != False
            if  get_suboption("history", param) != False:
                history =  get_suboption("history", param)
            else:
                history = ""
                                                    
        except ValueError,e:
            raise OptionError(opt.name, "invalid value '%s': %s" % (opt.value, e))
        graph.GetCommunityStructure(g, corr, N, Tmin, Tmax, spins, seed, verbose, history, weight, prop)
    elif opt.name == "modularity":
        values = parse_values(opt.value)
        if len(values) < 2 or len(values) > 3:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        prop, weight, file_name = values[0], "", values[1]
        if len(values) > 2:
            weight = values[1]
            file_name = values[2]
        if just_file:
            return file_name
        return (graph.GetModularity(weight, prop), file_name)
    elif opt.name == "community-graph":
        values = parse_values(opt.value)
        if len(values) < 2 or len(values) > 3:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        prop, file_name = values[0], values[1]
        if len(values) > 2:
            format = values[2]
        else:
            format = ""
        if just_file:
            return
        return (graph.GetCommunityNetwork(prop, file_name, format))
    elif opt.name == "compute-spring-block-layout":
        if just_file:
            return None
        values = parse_values(opt.value)
        if len(values) == 0 or len(values) > 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        iterations,seed = 0,0
        try:
            iterations = int(values[0])
            if len(values) > 1:
                seed = int(values[1])
            else:
                seed = int(time())
        except ValueError:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        graph.ComputeGraphLayoutSpringBlock(iterations,seed)
    elif opt.name == "compute-gursoy-atun-layout":
        if just_file:
            return None
        values = parse_values(opt.value)
        if len(values) == 0 or len(values) > 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        iterations,seed = 0,0
        try:
            iterations = int(values[0])
            if len(values) > 1:
                seed = int(values[1])
            else:
                seed = int(time())
        except ValueError:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        graph.ComputeGraphLayoutGursoy(iterations,seed)
    elif opt.name == "vertex-filter" or opt.name == "edge-filter":
        if just_file:
            return None
        filter_vars = dict()
        def filter_function():
            return not (eval(opt.value,filter_vars))
        if opt.name == "vertex-filter":
            graph.SetGenericVertexFilter((filter_function,filter_vars))
        else:
            graph.SetGenericEdgeFilter((filter_function,filter_vars))
    elif opt.name == "vertex-range-filter" or opt.name == "edge-range-filter":
        if just_file:
            return None
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if (len(values[1].split()) != 2):
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        filter_range = (0,0)
        try:
            vals = values[1].split()
            filter_range = (float(vals[0]), float(vals[1]))
        except ValueError:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if opt.name == "vertex-range-filter":
            graph.SetVertexFilterProperty(values[0])
            graph.SetVertexFilterRange(filter_range)
        if opt.name == "edge-range-filter":
            graph.SetEdgeFilterProperty(values[0])
            graph.SetEdgeFilterRange(filter_range)
    elif opt.name == "reset-vertex-filter":
        if just_file:
            return None
        graph.SetVertexFilterProperty("")
        graph.SetGenericVertexFilter(None)
    elif opt.name == "reset-edge-filter":
        if just_file:
            return None
        graph.SetEdgeFilterProperty("")
        graph.SetGenericEdgeFilter(None)
    elif opt.name == "directed":
        if just_file:
            return None
        graph.SetDirected(True)
    elif opt.name == "undirected":
        if just_file:
            return None
        graph.SetDirected(False)
    elif opt.name == "reverse":
        if just_file:
            return None
        graph.SetReversed(not graph.GetReversed())
    elif opt.name == "edit-vertex-property" or opt.name == "edit-edge-property":
        values = parse_values(opt.value)
        if len(values) != 2:
            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
        if just_file:
            return None
        edit_vars = dict()
        if "file:" in values[1]:
            expressions = values[1].split("file:")
            if len(expressions) > 1:
                exec expressions[0] in edit_vars
                exec open(expressions[1].strip()).read() in edit_vars
            else:
                exec open(expressions[0].strip()).read() in edit_vars            
            edit_function = edit_vars["edit_function"]
        else:
            def edit_function():
                return (eval(values[1],edit_vars))
        if opt.name == "edit-vertex-property":
            graph.EditVertexProperty(values[0],(edit_function,edit_vars))
        else:
            graph.EditEdgeProperty(values[0],(edit_function,edit_vars))
    elif opt.name == "remove-vertex-property":
        if just_file:
            return None
        graph.RemoveVertexProperty(opt.value)
    elif opt.name == "remove-edge-property":
        if just_file:
            return None
        graph.RemoveEdgeProperty(opt.value)
    elif opt.name == "insert-edge-index-property":
        if just_file:
            return None
        graph.InsertEdgeIndexProperty(opt.value)
    elif opt.name == "insert-vertex-index-property":
        if just_file:
            return None
        graph.InsertVertexIndexProperty(opt.value)          
        
def open_file(name, mode="w"):
    if name == "-":
        return sys.stdout
    if name.endswith("bz2"):
        return bz2.BZ2File(name, mode)
    if name.endswith("gz"):
        return gzip.GzipFile(name, mode)
    return file(name, mode)

def write_data(data, file, prefix=None):
    if prefix != None:
        prefix = "%s\t" % prefix
    else:
        prefix = ""
    if data.__class__ == dict:
        # it is a histogram
        keys = data.keys()
        keys.sort()
        for k in keys:
            file.write(prefix)
            if k.__class__ == tuple:
                # higher dimensional histogram
                for i in xrange(0,len(k)):
                    file.write("%s\t" % str(k[i]))                
            else:
                file.write("%s\t" % (str(k)))
            if data[k].__class__ == tuple:
                for i in xrange(0,len(data[k])):
                    file.write("%s\t" % str(data[k][i]))
                file.write("\n")
            else:
                file.write("%s\n" % str(data[k]))
    else:
        # single value
        file.write("%s%s\n" % (prefix,str(data)))
    if file.__class__ != bz2.BZ2File:
        file.flush()

class HistoryException (Exception):
    def __init__(self, file=None, old=None, what=None):
        if what == None:
            self.what = "error copying contents from file '%s' to file '%s'" % (old,file)
        else:
            self.what = what
    def __str__(self):
        return self.what

class HistoryFile:
    def __init__(self, file_name, overwrite):
        self.file_name = os.path.expanduser(file_name)
        self.last_prefix = None
        self.file = None
        self.time = clock()
        self.temp = self.file_name + "___temp"
        if self.file_name.endswith(".bz2"):
            self.temp = self.file_name.rstrip(".bz2") + "___temp.bz2"
        if self.file_name.endswith(".gz"):
            self.temp = self.file_name.rstrip(".gz") + "___temp.gz"
        match = re.compile("([0-9]+)([d,h,m,s])").match(options.refresh_rate)
        if match != None:
            self.rate = int(match.group(1))
            modifier = match.group(2)
            if modifier == "m":
                self.rate *= 60
            if modifier == "h":
                self.rate *= 60
            if modifier == "d":
                self.rate *= 24
        else:
            raise HistoryException(what="invalid history refresh rate value: %s" % options.represh_rate)
        if os.path.exists(self.file_name) and self.file_name != "-" and not overwrite:            
            # test the integrity of the compressed files
            try:
                if self.file_name.endswith(".bz2") or self.file_name.endswith(".gz"):
                    for line in open_file(self.file_name,"r"):
                        pass
            except (IOError, EOFError):
                if not os.path.exists(self.temp):
                    old = open_file(self.temp, "w")
                    old.write("")
                    old.close()
                os.rename(self.temp, self.file_name)
            #upadate last_prefix
            for line in open_file(self.file_name, "r"):
                self.last_prefix = line.split()[0]
            self.refresh()
        else:
            self.file = open_file(self.file_name, "w")

    def __del__(self):
        if self.file != None:
            self.file.close()
        if self.temp != None:
            if os.path.exists(self.temp):
                os.remove(self.temp)

    def refresh(self):
        try:                                                                        
            if self.file_name.endswith(".bz2") or  self.file_name.endswith(".gz"):
                os.rename(self.file_name, self.temp)
                # copy history from old file to new file
                self.file = open_file(self.file_name, "w")
                for line in open_file(self.temp, "r"):
                    self.file.write(line)
            else:
                self.file = open_file(self.file_name, "a")
        except:
            os.rename(self.old, self.file_name)
            raise HistoryException(self.file_name, self.temp)
    
            
    def write(self, data, prefix):
        write_data(data, self.file, prefix)
        if clock() - self.time > self.rate:
            self.file.close()
            self.refresh()
            self.time = clock()

# signal handling
graph.InitSignalHandling()

# parse each option in order
try:
    history_range = None
    overwrite_history = False
    for opt in option_list:
        if opt.name == "for" or opt.name == "history":
            # the rest of the commands are to be treated as history template
            history_range = opt
            if opt.name == "for":
                overwrite_history = True
            break
        retval = parse_option(opt)
        if retval != None:
            if retval[1] != None:
                prefix = None
                if retval[1] == "-":
                    if opt.value.strip() != "-":
                        print "#",opt.name.replace("-"," "), "("+opt.value.replace("|",", ").replace(", -","")+"):"
                    else:
                        print "#",opt.name.replace("-"," ")+":"
                write_data(retval[0], open_file(retval[1]), prefix)
                if retval[1] == "-":
                    print
                
    # deal with history
    if history_range != None:
        from string import Template
        class MyTemplate(Template):
            delimiter = "%"
        values = parse_values(history_range.value)
        if len(values) != 3:
            raise OptionError("history", "invalid value '%s'" % history_range.value)
        histories = option_list[option_list.index(history_range)+1:]
        history_files = dict() # open history files
        variables = dict() # template variables
        exec values[0] in variables #init
        exec "___continue = %s" % values[1] in variables # condition
        count = 0
        while variables["___continue"]:
            for opt in histories:
                new_opt = Opt(opt.name,opt.value)
                uses_prefix = True
                if new_opt.value != None:
                    if "%prefix" in opt.value:
                        uses_prefix = False
                    t = MyTemplate(new_opt.value)
                    try:
                        new_opt.value = t.substitute(variables)
                    except KeyError:
                        raise OptionError(opt.name, "invalid value '%s'" % opt.value)
                file_name = parse_option(new_opt, just_file=True)
                if file_name != None:
                    prefix = str(count)
                    if variables.has_key("prefix"):
                        prefix = str(variables["prefix"])
                    hist_key = opt.name + opt.value
                    if not history_files.has_key(hist_key):
                        history_files[hist_key] = HistoryFile(file_name, overwrite_history)
                    else:
                        if history_files[hist_key].file_name != os.path.expanduser(file_name):
                            history_files[hist_key] = HistoryFile(file_name, overwrite_history)
                    try:
                        if history_files[hist_key].last_prefix != None:
                            is_new = float(prefix) > float(history_files[hist_key].last_prefix)
                        else:
                            is_new = True
                    except ValueError:
                        is_new = True
                    if is_new or overwrite_history:
                        data = parse_option(new_opt)[0]
                        if uses_prefix:
                            history_files[hist_key].write(data, prefix)
                        else:
                            history_files[hist_key].write(data, "")
                else:
                    parse_option(new_opt)
            exec values[2] in variables # step
            exec "___continue = %s" % values[1] in variables # condition