facett-graphnav/src/io.rs
//! **GEXF / GraphML import + export** — Gephi's front door. The navigator round-trips
//! the two interchange formats every serious graph tool speaks:
//!
//! - **GEXF** (`.gexf`, Gephi's native) — `<nodes>`/`<edges>` with per-node
//! `<attvalues>`; node label + properties + computed metrics ride as declared
//! `<attribute>`s.
//! - **GraphML** (`.graphml`, yEd/NetworkX/igraph) — `<node>`/`<edge>` with `<data>`
//! children keyed by `<key>` declarations.
//!
//! Export is deterministic string XML (no dep). Import is a tolerant, dependency-free
//! pull tokenizer sufficient for the structure Gephi / NetworkX / yEd emit: it reads
//! `id/label/source/target/weight` attributes and `<attvalue>` / `<data>` property
//! children into the [`PropGraph`] model. Attributes we don't model are ignored, not
//! fatal — the point is to get the nodes + edges + weights in.
use std::collections::BTreeMap;
use crate::model::{Edge, Node, PropGraph};
// ── export ───────────────────────────────────────────────────────────────────
/// XML-escape a string for an attribute value / text node.
fn esc(s: &str) -> String {
let mut out = String::with_capacity(s.len());
for c in s.chars() {
match c {
'&' => out.push_str("&"),
'<' => out.push_str("<"),
'>' => out.push_str(">"),
'"' => out.push_str("""),
'\'' => out.push_str("'"),
_ => out.push(c),
}
}
out
}
/// A per-node **extra attribute column** exported alongside the model properties
/// (e.g. computed centralities): the attribute name + one string value per node
/// (aligned to `graph.nodes`).
pub type ExtraColumn<'a> = (&'a str, Vec<String>);
/// The union of property keys across all nodes, first-seen order preserved by sort.
fn node_prop_keys(g: &PropGraph) -> Vec<String> {
let mut keys: BTreeMap<String, ()> = BTreeMap::new();
for n in &g.nodes {
for k in n.props.keys() {
keys.insert(k.clone(), ());
}
}
keys.into_keys().collect()
}
/// Serialise `g` as **GEXF** 1.2. `extra` columns are declared + emitted as attvalues
/// after the model properties (computed metrics land here).
#[must_use]
pub fn to_gexf(g: &PropGraph, extra: &[ExtraColumn]) -> String {
let prop_keys = node_prop_keys(g);
// Attribute id space: label(implicit) then props then extra columns.
let mut attr_ids: Vec<(String, &'static str)> = Vec::new();
for k in &prop_keys {
attr_ids.push((k.clone(), "string"));
}
for (name, _) in extra {
attr_ids.push(((*name).to_string(), "double"));
}
let mut s = String::new();
s.push_str("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
s.push_str("<gexf xmlns=\"http://gexf.net/1.2\" version=\"1.2\">\n");
s.push_str(" <graph defaultedgetype=\"directed\" mode=\"static\">\n");
// Attribute declarations.
s.push_str(" <attributes class=\"node\">\n");
for (i, (name, ty)) in attr_ids.iter().enumerate() {
s.push_str(&format!(" <attribute id=\"{i}\" title=\"{}\" type=\"{ty}\"/>\n", esc(name)));
}
s.push_str(" </attributes>\n");
// Nodes.
s.push_str(" <nodes>\n");
for (ni, n) in g.nodes.iter().enumerate() {
s.push_str(&format!(" <node id=\"{}\" label=\"{}\">\n", esc(&n.id), esc(n.caption())));
s.push_str(" <attvalues>\n");
for (ai, (name, _ty)) in attr_ids.iter().enumerate() {
let val = if ai < prop_keys.len() {
n.props.get(name).cloned()
} else {
extra.get(ai - prop_keys.len()).and_then(|(_, col)| col.get(ni).cloned())
};
if let Some(v) = val {
s.push_str(&format!(" <attvalue for=\"{ai}\" value=\"{}\"/>\n", esc(&v)));
}
}
// Always carry the node's label(type) as an explicit attvalue via a reserved key.
s.push_str(&format!(" <attvalue for=\"label\" value=\"{}\"/>\n", esc(&n.label)));
s.push_str(" </attvalues>\n");
s.push_str(" </node>\n");
}
s.push_str(" </nodes>\n");
// Edges.
s.push_str(" <edges>\n");
for (i, e) in g.edges.iter().enumerate() {
let w = e.props.get("weight").cloned().unwrap_or_else(|| "1.0".into());
s.push_str(&format!(
" <edge id=\"{i}\" source=\"{}\" target=\"{}\" label=\"{}\" weight=\"{}\"/>\n",
esc(&e.from),
esc(&e.to),
esc(&e.etype),
esc(&w),
));
}
s.push_str(" </edges>\n");
s.push_str(" </graph>\n");
s.push_str("</gexf>\n");
s
}
/// Serialise `g` as **GraphML**. `extra` columns are declared as `<key for="node">`
/// and emitted as `<data>` children.
#[must_use]
pub fn to_graphml(g: &PropGraph, extra: &[ExtraColumn]) -> String {
let prop_keys = node_prop_keys(g);
let mut s = String::new();
s.push_str("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
s.push_str("<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\">\n");
// Key declarations: label (node), each prop (node), each extra (node), weight (edge).
s.push_str(" <key id=\"label\" for=\"node\" attr.name=\"label\" attr.type=\"string\"/>\n");
for k in &prop_keys {
s.push_str(&format!(" <key id=\"n_{0}\" for=\"node\" attr.name=\"{0}\" attr.type=\"string\"/>\n", esc(k)));
}
for (name, _) in extra {
s.push_str(&format!(" <key id=\"m_{0}\" for=\"node\" attr.name=\"{0}\" attr.type=\"double\"/>\n", esc(name)));
}
s.push_str(" <key id=\"etype\" for=\"edge\" attr.name=\"etype\" attr.type=\"string\"/>\n");
s.push_str(" <key id=\"weight\" for=\"edge\" attr.name=\"weight\" attr.type=\"double\"/>\n");
s.push_str(" <graph edgedefault=\"directed\">\n");
for (ni, n) in g.nodes.iter().enumerate() {
s.push_str(&format!(" <node id=\"{}\">\n", esc(&n.id)));
s.push_str(&format!(" <data key=\"label\">{}</data>\n", esc(&n.label)));
for k in &prop_keys {
if let Some(v) = n.props.get(k) {
s.push_str(&format!(" <data key=\"n_{}\">{}</data>\n", esc(k), esc(v)));
}
}
for (name, col) in extra {
if let Some(v) = col.get(ni) {
s.push_str(&format!(" <data key=\"m_{}\">{}</data>\n", esc(name), esc(v)));
}
}
s.push_str(" </node>\n");
}
for e in &g.edges {
let w = e.props.get("weight").cloned().unwrap_or_else(|| "1.0".into());
s.push_str(&format!(" <edge source=\"{}\" target=\"{}\">\n", esc(&e.from), esc(&e.to)));
s.push_str(&format!(" <data key=\"etype\">{}</data>\n", esc(&e.etype)));
s.push_str(&format!(" <data key=\"weight\">{}</data>\n", esc(&w)));
s.push_str(" </edge>\n");
}
s.push_str(" </graph>\n");
s.push_str("</graphml>\n");
s
}
// ── a tiny, tolerant XML pull tokenizer ────────────────────────────────────────
/// One XML event.
#[derive(Clone, Debug, PartialEq)]
enum Ev {
/// `<name attr=...>` — carries whether it self-closed (`<name/>`).
Start { name: String, attrs: BTreeMap<String, String>, self_closing: bool },
/// `</name>`.
End { name: String },
/// Character data between tags (entity-decoded).
Text(String),
}
/// Decode the five predefined XML entities (enough for Gephi/NetworkX/yEd output).
fn unescape(s: &str) -> String {
s.replace("<", "<").replace(">", ">").replace(""", "\"").replace("'", "'").replace("&", "&")
}
/// Tokenize `xml` into events. Skips the `<?xml?>` prolog, comments, and DOCTYPE;
/// ignores namespaces on tag names by keeping the local part. Best-effort — malformed
/// fragments yield the events parsed so far rather than erroring.
fn tokenize(xml: &str) -> Vec<Ev> {
let b = xml.as_bytes();
let mut i = 0;
let n = b.len();
let mut out = Vec::new();
while i < n {
if b[i] == b'<' {
// Comment.
if xml[i..].starts_with("<!--") {
if let Some(end) = xml[i..].find("-->") {
i += end + 3;
} else {
break;
}
continue;
}
// Prolog / DOCTYPE / processing instruction.
if xml[i..].starts_with("<?") || xml[i..].starts_with("<!") {
if let Some(end) = xml[i..].find('>') {
i += end + 1;
} else {
break;
}
continue;
}
// Find the tag's closing '>'.
let Some(rel) = xml[i..].find('>') else { break };
let inner = &xml[i + 1..i + rel];
i += rel + 1;
if let Some(name) = inner.strip_prefix('/') {
out.push(Ev::End { name: local(name.trim()) });
} else {
let self_closing = inner.ends_with('/');
let inner = inner.trim_end_matches('/').trim();
let (name, attrs) = parse_tag(inner);
out.push(Ev::Start { name, attrs, self_closing });
}
} else {
// Text run up to the next '<'.
let Some(rel) = xml[i..].find('<') else {
let t = xml[i..].trim();
if !t.is_empty() {
out.push(Ev::Text(unescape(t)));
}
break;
};
let t = xml[i..i + rel].trim();
if !t.is_empty() {
out.push(Ev::Text(unescape(t)));
}
i += rel;
}
}
out
}
/// The local part of a possibly-namespaced name (`gexf:node` → `node`).
fn local(name: &str) -> String {
name.rsplit(':').next().unwrap_or(name).to_string()
}
/// Split a start-tag interior into its local name + attribute map.
fn parse_tag(inner: &str) -> (String, BTreeMap<String, String>) {
let mut it = inner.splitn(2, char::is_whitespace);
let name = local(it.next().unwrap_or("").trim());
let mut attrs = BTreeMap::new();
let rest = it.next().unwrap_or("");
let bytes = rest.as_bytes();
let mut i = 0;
while i < bytes.len() {
// key
while i < bytes.len() && (bytes[i] as char).is_whitespace() {
i += 1;
}
let ks = i;
while i < bytes.len() && bytes[i] != b'=' && !(bytes[i] as char).is_whitespace() {
i += 1;
}
let key = rest[ks..i].trim();
while i < bytes.len() && (bytes[i] as char).is_whitespace() {
i += 1;
}
if i >= bytes.len() || bytes[i] != b'=' {
if !key.is_empty() {
// boolean-ish attribute with no value; skip.
}
continue;
}
i += 1; // '='
while i < bytes.len() && (bytes[i] as char).is_whitespace() {
i += 1;
}
if i >= bytes.len() {
break;
}
let quote = bytes[i];
if quote != b'"' && quote != b'\'' {
break;
}
i += 1;
let vs = i;
while i < bytes.len() && bytes[i] != quote {
i += 1;
}
let val = &rest[vs..i.min(rest.len())];
i += 1; // closing quote
if !key.is_empty() {
attrs.insert(local(key), unescape(val));
}
}
(name, attrs)
}
// ── import ─────────────────────────────────────────────────────────────────────
/// Parse a **GEXF** document into a [`PropGraph`]. Reads node `id`/`label`, node
/// `<attvalue for=... value=...>` properties (the `label` reserved key sets the node
/// type), and edge `source`/`target`/`label`/`weight`.
///
/// # Errors
/// Returns `Err` if no `<graph>` / nodes could be recognised.
pub fn from_gexf(xml: &str) -> Result<PropGraph, String> {
let evs = tokenize(xml);
let mut g = PropGraph::new();
let mut cur: Option<Node> = None;
let mut in_node = false;
for ev in &evs {
match ev {
Ev::Start { name, attrs, self_closing } => match name.as_str() {
"node" => {
let id = attrs.get("id").cloned().unwrap_or_default();
if id.is_empty() {
continue;
}
let mut node = Node::new(id, "Node");
if let Some(lbl) = attrs.get("label") {
node.props.insert("name".into(), lbl.clone());
}
if *self_closing {
g.add_node(node);
} else {
cur = Some(node);
in_node = true;
}
}
"attvalue" if in_node => {
if let (Some(node), Some(key)) = (cur.as_mut(), attrs.get("for")) {
let val = attrs.get("value").cloned().unwrap_or_default();
if key == "label" {
node.label = val;
} else {
node.props.insert(key.clone(), val);
}
}
}
"edge" => {
let (Some(src), Some(dst)) = (attrs.get("source"), attrs.get("target")) else { continue };
let etype = attrs.get("label").cloned().unwrap_or_else(|| "EDGE".into());
let mut e = Edge::new(src.clone(), dst.clone(), etype);
if let Some(w) = attrs.get("weight") {
e.props.insert("weight".into(), w.clone());
}
g.add_edge(e);
}
_ => {}
},
Ev::End { name } if name == "node" => {
if let Some(node) = cur.take() {
g.add_node(node);
}
in_node = false;
}
_ => {}
}
}
if g.nodes.is_empty() {
return Err("no <node> elements found in GEXF".into());
}
Ok(g)
}
/// Parse a **GraphML** document into a [`PropGraph`]. Reads node `id`, node `<data>`
/// children (the `label`/`labelV` key sets the node type, others become properties),
/// and edge `source`/`target` with `<data key="weight">` / `<data key="etype">`.
///
/// # Errors
/// Returns `Err` if no `<node>` could be recognised.
pub fn from_graphml(xml: &str) -> Result<PropGraph, String> {
let evs = tokenize(xml);
// Map key id → attr.name so <data key=...> resolves to a human name.
let mut key_name: BTreeMap<String, String> = BTreeMap::new();
for ev in &evs {
if let Ev::Start { name, attrs, .. } = ev
&& name == "key"
&& let Some(id) = attrs.get("id")
{
let nm = attrs.get("attr.name").or_else(|| attrs.get("name")).cloned().unwrap_or_else(|| id.clone());
key_name.insert(id.clone(), nm);
}
}
let mut g = PropGraph::new();
let mut cur_node: Option<Node> = None;
let mut cur_edge: Option<Edge> = None;
let mut data_key: Option<String> = None;
for ev in &evs {
match ev {
Ev::Start { name, attrs, self_closing } => match name.as_str() {
"node" => {
let id = attrs.get("id").cloned().unwrap_or_default();
if id.is_empty() {
continue;
}
let node = Node::new(id, "Node");
if *self_closing {
g.add_node(node);
} else {
cur_node = Some(node);
}
}
"edge" => {
let (Some(src), Some(dst)) = (attrs.get("source"), attrs.get("target")) else { continue };
let e = Edge::new(src.clone(), dst.clone(), "EDGE");
if *self_closing {
g.add_edge(e);
} else {
cur_edge = Some(e);
}
}
"data" => {
data_key = attrs.get("key").map(|k| key_name.get(k).cloned().unwrap_or_else(|| k.clone()));
}
_ => {}
},
Ev::Text(t) => {
let Some(key) = data_key.clone() else { continue };
if let Some(node) = cur_node.as_mut() {
match key.as_str() {
"label" | "labelV" | "type" => node.label = t.clone(),
"name" => {
node.props.insert("name".into(), t.clone());
}
other => {
node.props.insert(other.to_string(), t.clone());
}
}
} else if let Some(edge) = cur_edge.as_mut() {
match key.as_str() {
"etype" | "label" | "labelE" => edge.etype = t.clone(),
other => {
edge.props.insert(other.to_string(), t.clone());
}
}
}
}
Ev::End { name } => match name.as_str() {
"data" => data_key = None,
"node" => {
if let Some(node) = cur_node.take() {
g.add_node(node);
}
}
"edge" => {
if let Some(edge) = cur_edge.take() {
g.add_edge(edge);
}
}
_ => {}
},
}
}
if g.nodes.is_empty() {
return Err("no <node> elements found in GraphML".into());
}
Ok(g)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn gexf_round_trips_the_demo_graph() {
let g = PropGraph::demo();
let xml = to_gexf(&g, &[("pagerank", vec!["0.1".into(); g.nodes.len()])]);
assert!(xml.contains("<gexf"));
assert!(xml.contains("source=\"p1\""));
let back = from_gexf(&xml).expect("parse back");
assert_eq!(back.nodes.len(), g.nodes.len());
assert_eq!(back.edges.len(), g.edges.len());
// Node type + caption survived.
let p1 = back.node("p1").expect("p1 present");
assert_eq!(p1.label, "Person");
assert_eq!(p1.caption(), "Alice");
}
#[test]
fn graphml_round_trips_the_demo_graph() {
let g = PropGraph::demo();
let xml = to_graphml(&g, &[]);
assert!(xml.contains("<graphml"));
let back = from_graphml(&xml).expect("parse back");
assert_eq!(back.nodes.len(), g.nodes.len());
assert_eq!(back.edges.len(), g.edges.len());
let p1 = back.node("p1").expect("p1 present");
assert_eq!(p1.label, "Person");
// Edge type preserved.
assert!(back.edges.iter().any(|e| e.etype == "WORKS_AT"));
}
#[test]
fn imports_a_minimal_external_gexf() {
// The shape Gephi exports (attvalues + weight).
let xml = r#"<?xml version="1.0"?>
<gexf version="1.2"><graph>
<nodes>
<node id="a" label="Ay"><attvalues><attvalue for="label" value="City"/></attvalues></node>
<node id="b" label="Bee"/>
</nodes>
<edges><edge id="0" source="a" target="b" weight="2.5"/></edges>
</graph></gexf>"#;
let g = from_gexf(xml).unwrap();
assert_eq!(g.nodes.len(), 2);
assert_eq!(g.edges.len(), 1);
assert_eq!(g.node("a").unwrap().label, "City");
assert_eq!(g.node("a").unwrap().caption(), "Ay");
assert_eq!(g.edges[0].props.get("weight").map(String::as_str), Some("2.5"));
}
#[test]
fn rejects_a_document_without_nodes() {
assert!(from_gexf("<gexf><graph><edges/></graph></gexf>").is_err());
assert!(from_graphml("<graphml><graph/></graphml>").is_err());
}
}