<commit_before>#!/usr/bin/env python3
# Reading graphs from files and writing into files
# <NAME> et <NAME> - 2015


def readval(file, ty):
    """Reads a line from file with an item of type ty"""
    return ty(file.readline())


def readtab(fi, ty):
    """Reads a line from file with a space separated list
       of items of type ty"""
    return tuple(map(ty, fi.readline().split()))


def read_graph(filename, directed=False, weighted=False, default_weight=None):
    """Read a graph from a text file

    :param filename: plain text file. All numbers are separated by space.
              Starts with a line containing n (#vertices) and m (#edges).
              Then m lines follow, for each edge.
              Vertices are numbered from 0 to n-1.
              Line for unweighted edge u,v contains two integers u, v.
              Line for weighted edge u,v contains three integers u, v, w[u,v].

    :param directed: true for a directed graph, false for undirected
    :param weighted: true for an edge weighted graph
    :returns: graph as adjacency list, possibly followed by weight matrix
    :complexity: O(n + m) for unweighted graph,
                 :math:`O(n^2)` for weighted graph
    """
    with open(filename, 'r') as f:
        while True:
            line = f.readline()         # ignore leading comments
            if line[0] != '#':
                break
        nb_nodes, nb_edges = tuple(map(int, line.split()))
        graph = [[] for u in range(nb_nodes)]
        if weighted:
            weight = [[default_weight] * nb_nodes for v in range(nb_nodes)]
            for v in range(nb_nodes):
                weight[v][v] = 0
            for _ in range(nb_edges):
                u, v, w = readtab(f, int)
                graph[u].append(v)
                weight[u][v] = w
                if not directed:
                    graph[v].append(u)
                    weight[v][u] = w
            return graph, weight
        else:
            for _ in range(nb_edges):
                # si le fichier contient des poids, ils seront ignorés
                u, v = readtab(f, int)[:2]
                graph[u].append(v)
                if not directed:
                    graph[v].append(u)
            return graph


def write_graph(dotfile, graph, directed=False,
                node_label=None, arc_label=None, comment="",
                node_mark=set(), arc_mark=set()):
    """Writes a graph to a file in the DOT format

    :param dotfile: the filename.
    :param graph: adjacency list or adjacency dictionary
    :param directed: true if graph is directed, false if undirected
    :param weight: weight matrix or adjacency dictionary or None
    :param node_label: vertex label table or None
    :param arc_label: arc label matrix or None
    :param comment: comment string for the dot file or None
    :param node_mark: set of nodes to be shown in gray
    :param arc_marc: set of arcs to be shown in red
    :complexity: `O(|V| + |E|)`
    """
    with open(dotfile, 'w') as f:
        if directed:
            f.write("digraph G{\n")
        else:
            f.write("graph G{\n")
        if comment:
            f.write('label="%s";\n' % comment)
        V = range(len(graph))
        #                              -- vertices
        for u in V:
            if node_mark and u in node_mark:
                f.write('%d [style=filled, color="lightgrey", ' % u)
            else:
                f.write('%d [' % u)
            if node_label:
                f.write('label="%u [%s]"];\n' % (u, node_label[u]))
            else:
                f.write('shape=circle, label="%u"];\n' % u)
        #                              -- edges
        if isinstance(arc_mark, list):
            arc_mark = set((u, arc_mark[u]) for u in V)
        for u in V:
            for v in graph[u]:
                if not directed and u > v:
                    continue   # don't show twice the edge
                if arc_label and arc_label[u][v] == None:
                    continue   # suppress arcs with no label
                if directed:
                    arc = "%d -> %d " % (u, v)
                else:
                    arc = "%d -- %d " % (u, v)
                if arc_mark and ( (v,u) in arc_mark or (not directed and (u,v) in arc_mark) ):
                    pen = 'color="red"'
                else:
                    pen = ""
                if arc_label:
                    tag = 'label="%s"' % arc_label[u][v]
                else:
                    tag = ""
                if tag and pen:
                    sep = ", "
                else:
                    sep = ""
                f.write(arc + "[" + tag + sep + pen + "];\n")
        f.write("}")


# snip{ tree_representations
def tree_prec_to_adj(prec, root=0):
    """Transforms a tree given as predecessor table into adjacency list form

    :complexity: linear
    """
    n = len(prec)
    graph = [[prec[u]] for u in range(n)]   # ajouter les prédécesseurs
    graph[root] = []
    for u in range(n):                      # ajouter les descendants
        if u != root:
            graph[prec[u]].append(u)
    return graph


def tree_adj_to_prec(graph, root=0):
    """Transforms a tree given as adjacency list into predecessor table form

    if graph is not a tree: will return a DFS spanning tree

    :complexity: linear
    """
    n = len(graph)
    prec = [None] * len(graph)
    prec[root] = root            # marquer pour ne pas revisiter la racine
    to_visit = [root]
    while to_visit:              # parcours DFS
        node = to_visit.pop()
        for neighbor in graph[node]:
            if prec[neighbor] is None:
                prec[neighbor] = node
                to_visit.append(neighbor)
    prec[root] = None            # mettre la marque standard pour la racine
    return prec
# snip}


# snip{ add_reverse_arcs
def add_reverse_arcs(graph, capac):
    """Utility function for flow algorithms that need for every arc (u,v),
    the existence of an (v,u) arc with zero capacity."""
    for u in range(len(graph)):
        for v in graph[u]:
            if u not in graph[v]:
                graph[v].append(u)
                capac[v][u] = 0
# snip}



def weight_to_graph(weight):
    """transforms a squared weight matrix in a adjacency table
    encoding the directed graph corrsponding to the entries of the matrix
    different from None """
    graph = [[] for _ in range(len(weight))]
    for u in range(len(graph)):
        for v in range(len(graph)):
            if weight[u][v] != None:<commit_msg>add_reverse_arcs works also without capacity<commit_after>#!/usr/bin/env python3
# Reading graphs from files and writing into files
# <NAME> et <NAME> - 2015


def readval(file, ty):
    """Reads a line from file with an item of type ty"""
    return ty(file.readline())


def readtab(fi, ty):
    """Reads a line from file with a space separated list
       of items of type ty"""
    return tuple(map(ty, fi.readline().split()))


def read_graph(filename, directed=False, weighted=False, default_weight=None):
    """Read a graph from a text file

    :param filename: plain text file. All numbers are separated by space.
              Starts with a line containing n (#vertices) and m (#edges).
              Then m lines follow, for each edge.
              Vertices are numbered from 0 to n-1.
              Line for unweighted edge u,v contains two integers u, v.
              Line for weighted edge u,v contains three integers u, v, w[u,v].

    :param directed: true for a directed graph, false for undirected
    :param weighted: true for an edge weighted graph
    :returns: graph as adjacency list, possibly followed by weight matrix
    :complexity: O(n + m) for unweighted graph,
                 :math:`O(n^2)` for weighted graph
    """
    with open(filename, 'r') as f:
        while True:
            line = f.readline()         # ignore leading comments
            if line[0] != '#':
                break
        nb_nodes, nb_edges = tuple(map(int, line.split()))
        graph = [[] for u in range(nb_nodes)]
        if weighted:
            weight = [[default_weight] * nb_nodes for v in range(nb_nodes)]
            for v in range(nb_nodes):
                weight[v][v] = 0
            for _ in range(nb_edges):
                u, v, w = readtab(f, int)
                graph[u].append(v)
                weight[u][v] = w
                if not directed:
                    graph[v].append(u)
                    weight[v][u] = w
            return graph, weight
        else:
            for _ in range(nb_edges):
                # si le fichier contient des poids, ils seront ignorés
                u, v = readtab(f, int)[:2]
                graph[u].append(v)
                if not directed:
                    graph[v].append(u)
            return graph


def write_graph(dotfile, graph, directed=False,
                node_label=None, arc_label=None, comment="",
                node_mark=set(), arc_mark=set()):
    """Writes a graph to a file in the DOT format

    :param dotfile: the filename.
    :param graph: adjacency list or adjacency dictionary
    :param directed: true if graph is directed, false if undirected
    :param weight: weight matrix or adjacency dictionary or None
    :param node_label: vertex label table or None
    :param arc_label: arc label matrix or None
    :param comment: comment string for the dot file or None
    :param node_mark: set of nodes to be shown in gray
    :param arc_marc: set of arcs to be shown in red
    :complexity: `O(|V| + |E|)`
    """
    with open(dotfile, 'w') as f:
        if directed:
            f.write("digraph G{\n")
        else:
            f.write("graph G{\n")
        if comment:
            f.write('label="%s";\n' % comment)
        V = range(len(graph))
        #                              -- vertices
        for u in V:
            if node_mark and u in node_mark:
                f.write('%d [style=filled, color="lightgrey", ' % u)
            else:
                f.write('%d [' % u)
            if node_label:
                f.write('label="%u [%s]"];\n' % (u, node_label[u]))
            else:
                f.write('shape=circle, label="%u"];\n' % u)
        #                              -- edges
        if isinstance(arc_mark, list):
            arc_mark = set((u, arc_mark[u]) for u in V)
        for u in V:
            for v in graph[u]:
                if not directed and u > v:
                    continue   # don't show twice the edge
                if arc_label and arc_label[u][v] == None:
                    continue   # suppress arcs with no label
                if directed:
                    arc = "%d -> %d " % (u, v)
                else:
                    arc = "%d -- %d " % (u, v)
                if arc_mark and ( (v,u) in arc_mark or (not directed and (u,v) in arc_mark) ):
                    pen = 'color="red"'
                else:
                    pen = ""
                if arc_label:
                    tag = 'label="%s"' % arc_label[u][v]
                else:
                    tag = ""
                if tag and pen:
                    sep = ", "
                else:
                    sep = ""
                f.write(arc + "[" + tag + sep + pen + "];\n")
        f.write("}")


# snip{ tree_representations
def tree_prec_to_adj(prec, root=0):
    """Transforms a tree given as predecessor table into adjacency list form

    :complexity: linear
    """
    n = len(prec)
    graph = [[prec[u]] for u in range(n)]   # ajouter les prédécesseurs
    graph[root] = []
    for u in range(n):                      # ajouter les descendants
        if u != root:
            graph[prec[u]].append(u)
    return graph


def tree_adj_to_prec(graph, root=0):
    """Transforms a tree given as adjacency list into predecessor table form

    if graph is not a tree: will return a DFS spanning tree

    :complexity: linear
    """
    n = len(graph)
    prec = [None] * len(graph)
    prec[root] = root            # marquer pour ne pas revisiter la racine
    to_visit = [root]
    while to_visit:              # parcours DFS
        node = to_visit.pop()
        for neighbor in graph[node]:
            if prec[neighbor] is None:
                prec[neighbor] = node
                to_visit.append(neighbor)
    prec[root] = None            # mettre la marque standard pour la racine
    return prec
# snip}


# snip{ add_reverse_arcs
def add_reverse_arcs(graph, capac = None):
    """Utility function for flow algorithms that need for every arc (u,v),
    the existence of an (v,u) arc with zero capacity.

    graph can be in adjacency list, possibly with capacity matrix capac.
    or graph can be in adjacency dictionnary, then capac parameter is ignored.

    """
    for u in range(len(graph)):
        for v in graph[u]:
            if u not in graph[v]:
                if type(graph[v]) is list:
                    graph[v].append(u)
                    if capac:
                        capac[v][u] = 0
                else:
                    assert type(graph[v]) is dict
                    graph[v][u] = 0
# snip}



def weight_to_graph(weight):
    """transforms a squared weight matrix in a adjacency table
    encoding the directed graph corrsponding to the entries of the matrix
    different from None """
    graph = [[] for _ in range(len(weight))]
    for u in range(len(graph)):
        for v in range(len(graph)):
            if weight[u][v] != None:
{'fraction_non_alphanumeric': 0.10370096225018505, 'fraction_numerical': 0.002146558105107328, 'mean_word_length': 1.6780971258671953, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6296635', 'n_tokens_mistral': 4029, 'n_tokens_neox': 3818, 'n_words': 1384}