Source code

Download source archive ↓

src/graph_exchange.py

1"""Simple static GML, GEXF and XGMML exchange for Galaxy Graph Converter."""
2
3from xml.etree import ElementTree as ET
4import re
5
6from contract import text
7from graphs import check, encode as encode_common, graphml, node_link, pajek
8
9GEXF = "http://www.gexf.net/1.2draft"
10XGMML = "http://www.cs.rpi.edu/XGMML"
11TOKEN = re.compile(r'\s+|#[^\n]*|[A-Za-z][A-Za-z_0-9]*|-?[0-9]+|"[^"\r\n]*"|\[|\]')
12
13
14def gml(data):
15    raw = text(data)
16    tokens = []
17    offset = 0
18    for match in TOKEN.finditer(raw):
19        if match.start() != offset:
20            raise ValueError("invalid GML token")
21        word = match[0]
22        offset = match.end()
23        if not (word[0].isspace() or word[0] == "#"):
24            tokens.append(word)
25        if len(tokens) > 175000:
26            raise ValueError("GML graph is too large")
27    if offset != len(raw) or tokens[:2] != ["graph", "["] or tokens[-1:] != ["]"]:
28        raise ValueError("expected one GML graph")
29    names = {}
30    edges = []
31    directed = False
32    cursor = 2
33    while cursor < len(tokens) - 1:
34        kind = tokens[cursor]
35        if kind == "directed" and tokens[cursor + 1] in ("0", "1") and cursor == 2:
36            directed = tokens[cursor + 1] == "1"
37            cursor += 2
38            continue
39        if kind not in {"node", "edge"} or tokens[cursor + 1] != "[":
40            raise ValueError("expected a GML node or edge")
41        # This subset deliberately forbids nested or attribute-bearing records.
42        end = cursor + 2
43        while end < len(tokens) - 1 and end - cursor <= 6 and tokens[end] not in {"[", "]"}:
44            end += 1
45        if tokens[end] != "]" or (end - cursor) % 2:
46            raise ValueError("invalid GML record")
47        record = dict(zip(tokens[cursor + 2:end:2], tokens[cursor + 3:end:2]))
48        if len(record) * 2 != end - cursor - 2:
49            raise ValueError("duplicate GML attributes")
50        if kind == "node":
51            if record.keys() not in ({"id", "label"}, {"id"}) or not re.fullmatch(r"-?[0-9]{1,16}", record["id"]):
52                raise ValueError("invalid GML node")
53            key = int(record["id"])
54            label = record.get("label", f'"{key}"')
55            if key in names or label[:1] != '"' or label[-1:] != '"':
56                raise ValueError("invalid or duplicate GML label")
57            names[key] = label[1:-1]
58        else:
59            if record.keys() != {"source", "target"} or any(not re.fullmatch(r"-?[0-9]{1,16}", v) for v in record.values()):
60                raise ValueError("invalid GML edge")
61            edges.append((int(record["source"]), int(record["target"])))
62        cursor = end + 1
63    if any(a not in names or b not in names for a, b in edges):
64        raise ValueError("unknown GML edge endpoint")
65    return check(directed, list(names.values()), [(names[a], names[b]) for a, b in edges])
66
67
68def xml_root(data):
69    raw = text(data)
70    if "<!" in raw:
71        raise ValueError("XML declarations defining markup are outside the graph format")
72    try:
73        return ET.fromstring(raw)
74    except ET.ParseError as error:
75        raise ValueError("invalid graph XML") from error
76
77
78def gexf(data):
79    root = xml_root(data)
80    tag = lambda name: "{" + GEXF + "}" + name
81    if root.tag != tag("gexf") or root.get("version") != "1.2":
82        raise ValueError("expected GEXF 1.2")
83    graphs = [e for e in root if e.tag != tag("meta")]
84    if len(graphs) != 1 or graphs[0].tag != tag("graph"):
85        raise ValueError("expected one static GEXF graph")
86    graph = graphs[0]
87    directed = graph.get("defaultedgetype", "undirected")
88    if directed not in ("directed", "undirected") or graph.get("mode", "static") != "static":
89        raise ValueError("dynamic or mixed-direction GEXF graphs are unsupported")
90    if sorted(e.tag for e in graph) != sorted((tag("nodes"), tag("edges"))):
91        raise ValueError("expected a nodes and an edges collection in GEXF")
92    nodes, edges = [], []
93    for node in graph.find(tag("nodes")):
94        identifier = node.get("id")
95        if (node.tag != tag("node") or len(node) or identifier is None
96                or node.get("label", identifier) != identifier or not node.attrib.keys() <= {"id", "label"}):
97            raise ValueError("GEXF node contains unsupported attributes")
98        nodes.append(identifier)
99    for edge in graph.find(tag("edges")):
100        if (edge.tag != tag("edge") or len(edge) or not
101                {"source", "target"} <= edge.attrib.keys() <= {"id", "source", "target"}):
102            raise ValueError("expected an unweighted GEXF edge")
103        edges.append((edge.get("source"), edge.get("target")))
104    return check(directed == "directed", nodes, edges)
105
106
107def xgmml(data):
108    root = xml_root(data)
109    tag = lambda name: "{" + XGMML + "}" + name
110    if root.tag != tag("graph") or root.get("directed", "0") not in ("0", "1"):
111        raise ValueError("expected one XGMML graph")
112    nodes, edges = [], []
113    for element in root:
114        if len(element):
115            raise ValueError("expected an unweighted, attribute-free XGMML graph")
116        if element.tag == tag("node") and {"id"} <= element.attrib.keys() <= {"id", "label"}:
117            identifier = element.get("id")
118            if element.get("label", identifier) != identifier:
119                raise ValueError("XGMML node identifiers and labels must agree")
120            nodes.append(identifier)
121        elif element.tag == tag("edge") and {"source", "target"} <= element.attrib.keys() <= {"id", "source", "target"}:
122            edges.append((element.get("source"), element.get("target")))
123        else:
124            raise ValueError("invalid XGMML element")
125    return check(root.get("directed", "0") == "1", nodes, edges)
126
127
128def encode_gml(directed, nodes, edges):
129    index = {n: i for i, n in enumerate(nodes)}
130    result = ["graph [\n", f"  directed {int(directed)}\n"]
131    result.extend(f'  node [ id {i} label "{n}" ]\n' for n, i in index.items())
132    result.extend(f"  edge [ source {index[s]} target {index[t]} ]\n" for s, t in edges)
133    return ("".join(result) + "]\n").encode()
134
135
136def encode_gexf(directed, nodes, edges):
137    root = ET.Element("gexf", xmlns=GEXF, version="1.2")
138    graph = ET.SubElement(root, "graph", defaultedgetype="directed" if directed else "undirected", mode="static")
139    node_list = ET.SubElement(graph, "nodes")
140    for node in nodes:
141        ET.SubElement(node_list, "node", id=node, label=node)
142    edge_list = ET.SubElement(graph, "edges")
143    for i, (source, target) in enumerate(edges):
144        ET.SubElement(edge_list, "edge", id=str(i), source=source, target=target)
145    return ET.tostring(root, encoding="utf-8") + b"\n"
146
147
148def encode_xgmml(directed, nodes, edges):
149    root = ET.Element("graph", xmlns=XGMML, directed=str(int(directed)))
150    for node in nodes:
151        ET.SubElement(root, "node", id=node, label=node)
152    for source, target in edges:
153        ET.SubElement(root, "edge", source=source, target=target)
154    return ET.tostring(root, encoding="utf-8") + b"\n"
155
156
157def execute(route, inputs, params):
158    source, target = route.split("_to_")
159    readers = {"gml": gml, "gexf": gexf, "xgmml": xgmml, "graphml": graphml, "json": node_link, "pajek": pajek}
160    writers = {"gml": encode_gml, "gexf": encode_gexf, "xgmml": encode_xgmml}
161    graph = readers[source](inputs["source"])
162    if target in writers:
163        return writers[target](*graph)
164    return encode_common(*graph, target)