little_tools/graphml2dimacs.py

#!/usr/bin/python3.5
import sys
import re
import xml.etree.ElementTree as ET

ET.register_namespace('', "http://graphml.graphdrawing.org/xmlns")
def get_namespace(element):
  m = re.match('\{.*\}', element.tag)
  return m.group(0) if m else ''

adjacency_list = [[]]
node_map = {}
node_weight = [0]
nodex_index = 1

tree = ET.parse(sys.argv[1])
namespace = get_namespace(tree.getroot())
for elem in tree.iterfind(namespace + 'key[@attr.name="weight"]') :
    weight_id = elem.attrib["id"]

root = tree.find(namespace + "graph")
for elem in root:
    # get node
    if elem.tag == namespace + 'node':
        # print (elem.attrib['id'], " weight: ")
        node_map[elem.attrib['id']] = nodex_index
        while len(adjacency_list) - 1 < nodex_index:
            adjacency_list.append([])
        nodex_index += 1

        # get weight
        for sub_elem in elem:
            # print (sub_elem.attrib['key'])
            if sub_elem.attrib['key'] == weight_id:
                # print (sub_elem.text)
                node_weight.append(int(float(sub_elem.text)))
    # get edge
    elif elem.tag == namespace + 'edge':
        source_index = node_map[elem.attrib['source']]
        target_index = node_map[elem.attrib['target']]
        adjacency_list[source_index].append(target_index);
        adjacency_list[target_index].append(source_index);

# for i in range(0, len(node_weight)):
#     print ("%s(%s) " % (i, node_weight[i]))

# before mapp
# nodex_index = 0
# for node_list in adjacency_list:
#     if (nodex_index == 0) :
#         nodex_index = 1
#         continue;
#     print (nodex_index , end=' : ')
#     for v in node_list:
#         print (v, end=' ')
#     print ()
#     nodex_index += 1

node_map.clear()
new_node_index = 1
nodex_index = 0
for node_list in adjacency_list:
    if (nodex_index == 0):
        nodex_index = 1
        continue
    if (len(node_list) != 0):
        node_map[nodex_index] = new_node_index
        new_node_index += 1
    nodex_index += 1

# new node_weight
new_node_weight = []
node_index = 0
for i in range(1, len(adjacency_list)):
    if (i in node_map):
        if (len(new_node_weight) - 1 < node_map[i]):
            new_node_weight.extend([0]*(node_map[i] + 1 - len(new_node_weight)))
        new_node_weight[node_map[i]] = node_weight[i]

# new graph
node_count = new_node_index - 1
edge_count = 0
for node_list in adjacency_list:
    edge_count += len(node_list)
edge_count = (int)(edge_count / 2)
print ("p edge %s %s" % (node_count, edge_count))
for i in range(1, len(new_node_weight)):
    print ("v %s %s" % (i, new_node_weight[i]))

nodex_index = 0
for node_list in adjacency_list:
    if (nodex_index == 0):
        nodex_index = 1
        continue
    if (len(node_list) == 0):
        nodex_index += 1
        continue

    for v in node_list:
        if (node_map[nodex_index] < node_map[v]):
            print ("e %s %s" % (node_map[nodex_index], node_map[v]))
    nodex_index += 1

# for key in node_map:
#     print ("%s -> %s" %(key, node_map[key]), end = ', ')