src/graphs.py
1"""The simple, unweighted GraphML, Pajek and node-link JSON conversion subset."""
2
3from xml.etree import ElementTree as ET
4import re
5import shlex
6
7from contract import lines, text
8from tables import json_lines, parse_json
9
10GRAPHML = "http://graphml.graphdrawing.org/xmlns"
11SAFE_ID = re.compile(r"[A-Za-z0-9_][A-Za-z0-9_.:-]{0,63}")
12
13
14def check(directed, nodes, edges):
15 if type(directed) is not bool or len(nodes) > 4096 or len(edges) > 25000:
16 raise ValueError("invalid graph or too many nodes or edges")
17 if any(not isinstance(n, str) or not SAFE_ID.fullmatch(n) for n in nodes):
18 raise ValueError("expected simple alphanumeric node IDs")
19 known = set(nodes)
20 if len(known) != len(nodes):
21 raise ValueError("duplicate node")
22 seen = set()
23 for source, target in edges:
24 if not isinstance(source, str) or not isinstance(target, str) or source not in known or target not in known:
25 raise ValueError("edge endpoints must name existing nodes")
26 key = (source, target) if directed else tuple(sorted((source, target)))
27 if key in seen:
28 raise ValueError("parallel edges are outside the simple-graph contract")
29 seen.add(key)
30 return directed, nodes, edges
31
32
33def graphml(data):
34 decoded = text(data)
35 if "<!" in decoded:
36 raise ValueError("GraphML markup declarations are unsupported")
37 try:
38 root = ET.fromstring(decoded)
39 except ET.ParseError as error:
40 raise ValueError("invalid GraphML") from error
41 qualify = lambda tag: "{" + GRAPHML + "}" + tag
42 if root.tag != qualify("graphml") or len(root) != 1 or root[0].tag != qualify("graph"):
43 raise ValueError("expected one GraphML graph without attributes")
44 graph = root[0]
45 direction = graph.get("edgedefault")
46 if direction not in {"directed", "undirected"}:
47 raise ValueError("invalid default edge direction")
48 nodes, edges = [], []
49 for item in graph:
50 if item.tag == qualify("node") and not len(item) and set(item.attrib) == {"id"}:
51 nodes.append(item.get("id"))
52 elif item.tag == qualify("edge") and not len(item) and {"source", "target"} <= item.attrib.keys() <= {"source", "target", "id"}:
53 edges.append((item.get("source"), item.get("target")))
54 else:
55 raise ValueError("GraphML only supports simple nodes and edges")
56 return check(direction == "directed", nodes, edges)
57
58
59def node_link(data):
60 graph = parse_json(text(data))
61 if (not isinstance(graph, dict) or graph.keys() != {"directed", "multigraph", "graph", "nodes", "links"}
62 or graph["multigraph"] is not False or graph["graph"] != {}):
63 raise ValueError("expected a simple node-link graph")
64 nodes, edges = graph.get("nodes"), graph.get("links")
65 if not isinstance(nodes, list) or any(not isinstance(n, dict) or n.keys() != {"id"} for n in nodes):
66 raise ValueError("invalid graph nodes")
67 if not isinstance(edges, list) or any(not isinstance(e, dict) or e.keys() != {"source", "target"} for e in edges):
68 raise ValueError("invalid graph links")
69 return check(graph.get("directed"), [n["id"] for n in nodes], [(e["source"], e["target"]) for e in edges])
70
71
72def pajek(data):
73 rows = [row for row in lines(data) if row.strip()]
74 if not rows or not re.fullmatch(r"\*Vertices [0-9]{1,4}", rows[0], re.IGNORECASE):
75 raise ValueError("expected a Pajek vertices header")
76 count = int(rows[0].split()[1])
77 if count > 4096 or len(rows) < count + 2:
78 raise ValueError("Pajek vertex count mismatch")
79 nodes = []
80 for index, row in enumerate(rows[1:count + 1], 1):
81 fields = shlex.split(row)
82 if len(fields) != 2 or fields[0] != str(index):
83 raise ValueError("expected consecutive Pajek indices and node names")
84 nodes.append(fields[1])
85 direction = rows[count + 1].strip().lower()
86 if direction not in {"*arcs", "*edges"}:
87 raise ValueError("expected Pajek arcs or edges")
88 edges = []
89 for row in rows[count + 2:]:
90 indices = row.split()
91 if len(indices) != 2 or any(not re.fullmatch(r"[1-9][0-9]{0,3}", s) or int(s) > count for s in indices):
92 raise ValueError("invalid Pajek edge")
93 edges.append(tuple(nodes[int(s) - 1] for s in indices))
94 return check(direction == "*arcs", nodes, edges)
95
96
97def execute(operation, inputs, params):
98 source, target = operation.split("_to_")
99 directed, nodes, edges = {"graphml": graphml, "json": node_link, "pajek": pajek}[source](inputs["source"])
100 return encode(directed, nodes, edges, target)
101
102
103def encode(directed, nodes, edges, target):
104 if target == "json":
105 return json_lines([dict(directed=directed, multigraph=False, graph={},
106 nodes=[{"id": n} for n in nodes], links=[{"source": s, "target": t} for s, t in edges])])
107 if target == "graphml":
108 root = ET.Element("graphml", xmlns=GRAPHML)
109 graph = ET.SubElement(root, "graph", edgedefault="directed" if directed else "undirected")
110 for node in nodes:
111 ET.SubElement(graph, "node", id=node)
112 for source, target in edges:
113 ET.SubElement(graph, "edge", source=source, target=target)
114 return ET.tostring(root, encoding="utf-8") + b"\n"
115 positions = {name: index for index, name in enumerate(nodes, 1)}
116 labels = [f'{index} "{name}"\n' for name, index in positions.items()]
117 edge_lines = [f"{positions[source]} {positions[target]}\n" for source, target in edges]
118 return ("".join([f"*Vertices {len(nodes)}\n", *labels, "*Arcs\n" if directed else "*Edges\n", *edge_lines])).encode()