<jupyter_start><jupyter_text>Graph RepresentationDefintions:We have a graph $G = (V, E, w)$, where $V = \{1, 2, ..., n\}$, $E$ is the set of edges, and $w$ is the weight of each vertex, the function mapping $V \rightarrow \mathbb{R}^{+}$.  Drawing UtilityTakes in a undirected graph, and a color map, and draw the graph out in a circular format.<jupyter_code>def draw_reduced(g, color_map = None):
    
    node_lables = nx.get_node_attributes(g, "weight")
    
    if node_lables:
        node_lables = {k: "{0}: {1}".format(k, v) for (k, v) in node_lables.items()}
    else:
        node_lables = {k: k for k in g.nodes}
    
    plt.figure()
    pos = nx.circular_layout(g)
    nx.draw(g, pos, node_size=2000, width = 1, node_color = color_map)
    nx.draw_networkx_labels(g, pos, node_lables)
    plt.show()  
    # plt.savefig("graph.png", dpi=1000)<jupyter_output><empty_output><jupyter_text>Gurobi maximum independent set solverTakes in a undirected graph, with optional assignment of weight to each vertex. Returns the maximum independent set, computed by the Gurobi solver. If using `display=True`, `draw_reduced()` must be supplied.<jupyter_code>def compute_max_ind_set(graph, display = False, debug = False):
    nodes = list(graph.nodes)
    model = Model('Maximum Independent Set')
    
    # Suppress output
    if not debug:
        model.setParam('OutputFlag', 0)

    # An indicator variable for whether a node is chosen
    indicators = model.addVars(nodes, vtype=GRB.BINARY, name = "x")
    
    # Set Constraint: If two nodes are bound by an edge, they cannot be both chosen
    model.addConstrs(((indicators[i] + indicators[j] <= 1) for (i, j) in graph.edges), "Max")
    
    # Set objective: Maximize the weighted sum of nodes, or if no weights, just the cardinality.
    weights = nx.get_node_attributes(graph, "weight")
    if weights:
        obj = sum([indicators[i] * weights[i] for i in nodes])
    else:
        obj = sum([indicators[i] for i in nodes])
        
    model.setObjective(obj, GRB.MAXIMIZE)
    model.optimize()
    
    # Find all selected nodes and save them in soln
    soln = []
    for i in range(len(indicators)):
        if indicators[i].x != 0:
            soln.append(i)
    
    if display:
        # Create color map from selected nodes, green for selected, grey for unselected.
        color_map = ["grey"] * len(graph.nodes)
        for i in soln:
            color_map[i] = "green"
        draw_reduced(graph, color_map)
    return soln<jupyter_output><empty_output><jupyter_text>One example: Random Binomial Graph<jupyter_code># Generate a random sparse graph and assign random weights to each vertex


rand_graph = nx.fast_gnp_random_graph(6, 0.20, directed=False)

# for v in rand_graph.nodes():
#     rand_graph.nodes[v]['weight'] = round(random.uniform(0, 1), 2)
    
#draw_reduced(rand_graph)
rand_output = compute_max_ind_set(rand_graph, display=True, debug=False)
len(rand_output)<jupyter_output><empty_output><jupyter_text>Generic Dataset GeneratorGenerates random graphs and compute their maximum independent set.  Stores data in `data/generic_binomial`.  Generates random graphs and stores them in individual files named as `binomial[ID].txt`, where `[ID]` is the ID of the graph. The ID ranges from 1 to n, where n is the size of the dataset.A CSV would also be included in the directory. The format of this file would be rows of:  ```filename, node1, node2, ... node[n]```The graph would be stored at `filename` and the solution would be presented as a list of nodes. Note that this only one solution specified in this training set, there might be other maximum solutions.<jupyter_code>import os
print(os.getcwd())
import tarfile

def make_tarfile(output_filename, source_dir):
    with tarfile.open(output_filename, "w:gz") as tar:
        tar.add(source_dir, arcname=os.path.basename(source_dir))
from tqdm import tqdm
import os
import csv
import pathlib
import numpy as np
import networkx as nx
dataset_name = "weighted_80"
root_dir = "data/" + dataset_name
label_filename = "label.csv"
weight_filename = 'weight.csv'

num_examples = 100
num_nodes = 80
edge_prob = 0.3

WEIGHTED = True

os.makedirs(os.path.join(root_dir), exist_ok=True)
with open(os.path.join(root_dir, label_filename), 'w+') as label_file:
    with open(os.path.join(root_dir, weight_filename), 'w+') as weight_file:
        label_writer = csv.writer(label_file, delimiter=',')
        weight_writer = csv.writer(weight_file, delimiter=',')
        label_writer.writerow(["Filename"] + list(range(num_nodes)))
        weight_writer.writerow(["Filename"] + list(range(num_nodes)))
        for i in tqdm(range(num_examples)):
            graph_filename = "binomial" + str(i) + ".txt"
            graph = nx.fast_gnp_random_graph(num_nodes, edge_prob, directed=False)
            
            if WEIGHTED:
                weights = np.round(np.random.rand(num_nodes), 3)
            else:
                weights = np.ones(num_nodes)
                
            for v in graph.nodes():
                graph.nodes[v]['weight'] = weights[v]
            
            with open(os.path.join(root_dir, graph_filename), 'wb+') as graph_file:
                nx.write_adjlist(graph, graph_file)
        
            output_list = compute_max_ind_set(graph)
            
            output = np.zeros(num_nodes, dtype=int)
            output[output_list] = 1
            label_writer.writerow([graph_filename] + list(output))
            weight_writer.writerow([graph_filename] + list(weights))
            label_file.flush()

make_tarfile(root_dir + '.tar.gz', root_dir)

print("done")
# make_tarfile("data/weighted_binomial" + '.tar.gz', "data/weighted_binomial_80")
# Compress dataset for Git
# import os
# dataset_name = "generic_binomial_100"
# root_dir = "data/" + dataset_name<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11031298101590559, 'fraction_numerical': 0.007183170856849667, 'mean_word_length': 3.3870967741935485, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '125317', 'license': 'MIT', 'n_tokens_mistral': 1934, 'n_tokens_neox': 1857, 'n_words': 542, 'path': 'notebooks/dataset_gen.ipynb', 'repo_name': 'Zeyuzhao/DeepKidney', 'size': '5847'}