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)