IO.GraphML.cs

Go to the documentation of this file.

#region License
/*This file is part of Satsuma Graph Library
Copyright © 2013 Balázs Szalkai

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

   3. This notice may not be removed or altered from any source
   distribution.*/
#endregion

using System;
using System.Collections.Generic;
using System.Xml;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Xml.Linq;

namespace Satsuma.IO.GraphML
{
    public enum PropertyDomain
    {
        All, Node, Arc, Graph
    }

    public abstract class GraphMLProperty
    {
        public string Name { get; set; }
        public PropertyDomain Domain { get; set; }
        public string Id { get; set; }

        protected GraphMLProperty()
        {
            Domain = PropertyDomain.All;
        }

        protected static string DomainToGraphML(PropertyDomain domain)
        {
            switch (domain)
            {
                case PropertyDomain.Node: return "node";
                case PropertyDomain.Arc: return "edge";
                case PropertyDomain.Graph: return "graph";
                default: return "all";
            }
        }

        protected static PropertyDomain ParseDomain(string s)
        {
            switch (s)
            {
                case "node": return PropertyDomain.Node; 
                case "edge": return PropertyDomain.Arc; 
                case "graph": return PropertyDomain.Graph;
                default: return PropertyDomain.All;
            }
        }

        protected virtual void LoadFromKeyElement(XElement xKey)
        {
            var attrName = xKey.Attribute("attr.name");
            Name = (attrName == null ? null : attrName.Value);
            Domain = ParseDomain(xKey.Attribute("for").Value);
            Id = xKey.Attribute("id").Value;

            var _default = Utils.ElementLocal(xKey, "default");
            ReadData(_default, null);
        }

        public virtual XElement GetKeyElement()
        {
            XElement xKey = new XElement(GraphMLFormat.xmlns + "key");
            xKey.SetAttributeValue("attr.name", Name);
            xKey.SetAttributeValue("for", DomainToGraphML(Domain));
            xKey.SetAttributeValue("id", Id);

            XElement xDefault = WriteData(null);
            if (xDefault != null)
            {
                xDefault.Name = GraphMLFormat.xmlns + "default";
                xKey.Add(xDefault);
            }
    
            return xKey;
        }

        public abstract void ReadData(XElement x, object key);
        public abstract XElement WriteData(object key);
    }

    public abstract class DictionaryProperty<T> : GraphMLProperty, IClearable
    {
        public bool HasDefaultValue { get; set; }
        public T DefaultValue { get; set; }
        public Dictionary<object, T> Values { get; private set; }

        protected DictionaryProperty() : base()
        {
            HasDefaultValue = false;
            Values = new Dictionary<object, T>();
        }

        public void Clear()
        {
            HasDefaultValue = false;
            Values.Clear();
        }

        public bool TryGetValue(object key, out T result)
        {
            if (Values.TryGetValue(key, out result)) return true;
            if (HasDefaultValue)
            {
                result = DefaultValue;
                return true;
            }
            result = default(T);
            return false;
        }

        public T this[object key]
        {
            get
            {
                T result;
                TryGetValue(key, out result);
                return result;
            }
        }

        public override void ReadData(XElement x, object key)
        {
            if (x == null)
            {
                // erase
                if (key == null) HasDefaultValue = false; else Values.Remove(key);
            }
            else
            {
                // load
                T value = ReadValue(x);
                if (key == null)
                {
                    HasDefaultValue = true;
                    DefaultValue = value;
                }
                else Values[key] = value;
            }
        }

        public override XElement WriteData(object key)
        {
            if (key == null)
            {
                return HasDefaultValue ? WriteValue(DefaultValue) : null;
            }
            else
            {
                T value;
                if (!Values.TryGetValue(key, out value)) return null;
                return WriteValue(value);
            }
        }

        protected abstract T ReadValue(XElement x);
        protected abstract XElement WriteValue(T value);
    }

    public enum StandardType
    {
        Bool, Double, Float, Int, Long, String
    }

    public sealed class StandardProperty<T> : DictionaryProperty<T>
    {
        private static readonly StandardType Type = ParseType(typeof(T));
        private static readonly string TypeString = TypeToGraphML(Type);

        public StandardProperty()
            : base()
        { }

        internal StandardProperty(XElement xKey)
            : this()
        {
            var attrType = xKey.Attribute("attr.type");
            if (attrType == null || attrType.Value != TypeString)
                throw new ArgumentException("Key not compatible with property.");
            LoadFromKeyElement(xKey);
        }

        private static StandardType ParseType(Type t)
        {
            if (t == typeof(bool)) return StandardType.Bool;
            if (t == typeof(double)) return StandardType.Double;
            if (t == typeof(float)) return StandardType.Float;
            if (t == typeof(int)) return StandardType.Int;
            if (t == typeof(long)) return StandardType.Long;
            if (t == typeof(string)) return StandardType.String;
            throw new ArgumentException("Invalid type for a standard GraphML property.");
        }

        private static string TypeToGraphML(StandardType type)
        {
            switch (type)
            {
                case StandardType.Bool: return "boolean"; // !
                case StandardType.Double: return "double";
                case StandardType.Float: return "float";
                case StandardType.Int: return "int";
                case StandardType.Long: return "long";
                default: return "string";
            }
        }

        private static object ParseValue(string value)
        {
            switch (Type)
            {
                case StandardType.Bool: return value == "true";
                case StandardType.Double: return double.Parse(value, CultureInfo.InvariantCulture);
                case StandardType.Float: return float.Parse(value, CultureInfo.InvariantCulture);
                case StandardType.Int: return int.Parse(value, CultureInfo.InvariantCulture);
                case StandardType.Long: return long.Parse(value, CultureInfo.InvariantCulture);
                default: return value;
            }
        }

        private static string ValueToGraphML(object value)
        {
            switch (Type)
            {
                case StandardType.Bool: return (bool)value ? "true" : "false";
                case StandardType.Double: return ((double)value).ToString(CultureInfo.InvariantCulture);
                case StandardType.Float: return ((float)value).ToString(CultureInfo.InvariantCulture);
                case StandardType.Int: return ((int)value).ToString(CultureInfo.InvariantCulture);
                case StandardType.Long: return ((long)value).ToString(CultureInfo.InvariantCulture);
                default: return value.ToString();
            }
        }

        public override XElement GetKeyElement()
        {
            XElement x = base.GetKeyElement();
            x.SetAttributeValue("attr.type", TypeString);
            return x;
        }

        protected override T ReadValue(XElement x)
        {
            return (T)ParseValue(x.Value);
        }

        protected override XElement WriteValue(T value)
        {
            return new XElement("dummy", ValueToGraphML(value));
        }
    }

    public enum NodeShape
    {
        Rectangle, RoundRect, Ellipse, Parallelogram, 
        Hexagon, Triangle, Rectangle3D, Octagon,
        Diamond, Trapezoid, Trapezoid2
    }

    public sealed class NodeGraphics
    {
        public double X { get; set; }
        public double Y { get; set; }
        public double Width { get; set; }
        public double Height { get; set; }
        public NodeShape Shape { get; set; }

        public NodeGraphics()
        {
            X = Y = 0;
            Width = Height = 10;
            Shape = NodeShape.Rectangle;
        }

        private readonly string[] nodeShapeToString = { "rectangle", "roundrectangle", "ellipse", "parallelogram", 
                                                          "hexagon", "triangle", "rectangle3d", "octagon", 
                                                          "diamond", "trapezoid", "trapezoid2"};

        private NodeShape ParseShape(string s)
        {
            return (NodeShape)(Math.Max(0, Array.IndexOf(nodeShapeToString, s)));
        }

        private string ShapeToGraphML(NodeShape shape)
        {
            return nodeShapeToString[(int)shape];
        }

        public NodeGraphics(XElement xData)
        {
            XElement xGeometry = Utils.ElementLocal(xData, "Geometry");
            if (xGeometry != null)
            {
                X = double.Parse(xGeometry.Attribute("x").Value, CultureInfo.InvariantCulture);
                Y = double.Parse(xGeometry.Attribute("y").Value, CultureInfo.InvariantCulture);
                Width = double.Parse(xGeometry.Attribute("width").Value, CultureInfo.InvariantCulture);
                Height = double.Parse(xGeometry.Attribute("height").Value, CultureInfo.InvariantCulture);
            }
            XElement xShape = Utils.ElementLocal(xData, "Shape");
            if (xShape != null)
                Shape = ParseShape(xShape.Attribute("type").Value);
        }

        public XElement ToXml()
        {
            return new XElement("dummy",
                new XElement(GraphMLFormat.xmlnsY + "ShapeNode",
                    new XElement(GraphMLFormat.xmlnsY + "Geometry",
                        new XAttribute("x", X.ToString(CultureInfo.InvariantCulture)),
                        new XAttribute("y", Y.ToString(CultureInfo.InvariantCulture)),
                        new XAttribute("width", Width.ToString(CultureInfo.InvariantCulture)),
                        new XAttribute("height", Height.ToString(CultureInfo.InvariantCulture))),
                    new XElement(GraphMLFormat.xmlnsY + "Shape",
                        new XAttribute("type", ShapeToGraphML(Shape)))
                )
            );
        }

        public override string ToString()
        {
            return ToXml().ToString();
        }
    }
    
    public sealed class NodeGraphicsProperty : DictionaryProperty<NodeGraphics>
    {
        public NodeGraphicsProperty()
            : base()
        {
            Domain = PropertyDomain.Node;
        }

        internal NodeGraphicsProperty(XElement xKey)
            : this()
        {
            var attrYFilesType = xKey.Attribute("yfiles.type");
            if (attrYFilesType == null || attrYFilesType.Value != "nodegraphics")
                throw new ArgumentException("Key not compatible with property.");
            LoadFromKeyElement(xKey);
        }

        public override XElement GetKeyElement()
        {
            XElement x = base.GetKeyElement();
            x.SetAttributeValue("yfiles.type", "nodegraphics");
            return x;
        }

        protected override NodeGraphics ReadValue(XElement x)
        {
            return new NodeGraphics(x);
        }

        protected override XElement WriteValue(NodeGraphics value)
        {
            return value.ToXml();
        }
    }

    public sealed class GraphMLFormat
    {
        internal static readonly XNamespace xmlns = "http://graphml.graphdrawing.org/xmlns";
        private static readonly XNamespace xmlnsXsi = "http://www.w3.org/2001/XMLSchema-instance"; // xmlns:xsi
        internal static readonly XNamespace xmlnsY = "http://www.yworks.com/xml/graphml"; // xmlns:y
        private static readonly XNamespace xmlnsYed = "http://www.yworks.com/xml/yed/3"; // xmlns:yed
        private const string xsiSchemaLocation = "http://graphml.graphdrawing.org/xmlns\n" + // xsi:schemaLocation
                "http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd";

        public IGraph Graph { get; set; }
        public Dictionary<Node,string> NodeId { get; set; }
        public Dictionary<Arc, string> ArcId { get; set; }
        public IList<GraphMLProperty> Properties { get; private set; }

        private readonly List<Func<XElement, GraphMLProperty>> PropertyLoaders;

        public GraphMLFormat()
        {
            Properties = new List<GraphMLProperty>();
            PropertyLoaders = new List<Func<XElement, GraphMLProperty>>
            {
                x => new StandardProperty<bool>(x),
                x => new StandardProperty<double>(x), 
                x => new StandardProperty<float>(x), 
                x => new StandardProperty<int>(x), 
                x => new StandardProperty<long>(x), 
                x => new StandardProperty<string>(x), 
                x => new NodeGraphicsProperty(x)
            };
        }

        public void RegisterPropertyLoader(Func<XElement, GraphMLProperty> loader)
        {
            PropertyLoaders.Add(loader);
        }

        private static void ReadProperties(Dictionary<string, GraphMLProperty> propertyById, XElement x, object obj)
        {
            foreach (var xData in Utils.ElementsLocal(x, "data"))
            {
                GraphMLProperty p;
                if (propertyById.TryGetValue(xData.Attribute("key").Value, out p))
                    p.ReadData(xData, obj);
            }
        }

        public void Load(XDocument doc)
        {
            // Namespaces are ignored so we can load broken documents.
            if (Graph == null) Graph = new CustomGraph();
            IBuildableGraph buildableGraph = (IBuildableGraph)Graph;
            buildableGraph.Clear();
            XElement xGraphML = doc.Root;
            
            // load properties
            Properties.Clear();
            Dictionary<string, GraphMLProperty> propertyById = new Dictionary<string, GraphMLProperty>();
            foreach (var xKey in Utils.ElementsLocal(xGraphML, "key"))
            {
                foreach (var handler in PropertyLoaders)
                {
                    try
                    {
                        GraphMLProperty p = handler(xKey);
                        Properties.Add(p);
                        propertyById[p.Id] = p;
                        break;
                    }
                    catch (ArgumentException) { }
                }
            }

            // load graph
            XElement xGraph = Utils.ElementLocal(xGraphML, "graph");
            Directedness defaultDirectedness = (xGraph.Attribute("edgedefault").Value == "directed" ? 
                Directedness.Directed : Directedness.Undirected);
            ReadProperties(propertyById, xGraph, Graph);
            // load nodes
            NodeId = new Dictionary<Node, string>();
            Dictionary<string, Node> nodeById = new Dictionary<string, Node>();
            foreach (var xNode in Utils.ElementsLocal(xGraph, "node"))
            {
                Node node = buildableGraph.AddNode();
                string id = xNode.Attribute("id").Value;
                NodeId[node] = id;
                nodeById[id] = node;
                ReadProperties(propertyById, xNode, node);
            }
            // load arcs
            ArcId = new Dictionary<Arc, string>();
            foreach (var xArc in Utils.ElementsLocal(xGraph, "edge"))
            {
                Node u = nodeById[xArc.Attribute("source").Value];
                Node v = nodeById[xArc.Attribute("target").Value];
                
                Directedness dir = defaultDirectedness;
                XAttribute dirAttr = xArc.Attribute("directed");
                if (dirAttr != null) dir = (dirAttr.Value == "true" ? Directedness.Directed : Directedness.Undirected);
                
                Arc arc = buildableGraph.AddArc(u, v, dir);
                XAttribute xId = xArc.Attribute("id");
                if (xId != null)
                    ArcId[arc] = xId.Value;
                ReadProperties(propertyById, xArc, arc);
            }
        }

        public void Load(XmlReader xml)
        {
            XDocument doc = XDocument.Load(xml);
            Load(doc);
        }

        public void Load(TextReader reader)
        {
            using (XmlReader xml = XmlReader.Create(reader)) 
                Load(xml);
        }

        public void Load(string filename)
        {
            using (StreamReader reader = new StreamReader(filename))
                Load(reader);
        }

        private void DefinePropertyValues(XmlWriter xml, object obj)
        {
            foreach (var p in Properties)
            {
                XElement x = p.WriteData(obj);
                if (x == null) continue;
                x.Name = GraphMLFormat.xmlns + "data";
                x.SetAttributeValue("key", p.Id);
                x.WriteTo(xml);
            }
        }

        public void AddStandardNodeProperty<T>(string name, Func<Node,T> getValueForNode)
        {
            StandardProperty<T> prop = new StandardProperty<T>();
            prop.Domain = PropertyDomain.Node;
            prop.Name = name;
            foreach (var node in Graph.Nodes())
                prop.Values[node] = getValueForNode(node);
            Properties.Add(prop);
        }

        public void AddStandardArcProperty<T>(string name, Func<Arc, T> getValueForArc)
        {
            StandardProperty<T> prop = new StandardProperty<T>();
            prop.Domain = PropertyDomain.Arc;
            prop.Name = name;
            foreach (var arc in Graph.Arcs())
                prop.Values[arc] = getValueForArc(arc);
            Properties.Add(prop);
        }

        private void Save(XmlWriter xml)
        {
            xml.WriteStartDocument();
            xml.WriteStartElement("graphml", xmlns.NamespaceName);
            xml.WriteAttributeString("xmlns", "xsi", null, xmlnsXsi.NamespaceName);
            xml.WriteAttributeString("xmlns", "y", null, xmlnsY.NamespaceName);
            xml.WriteAttributeString("xmlns", "yed", null, xmlnsYed.NamespaceName);
            xml.WriteAttributeString("xsi", "schemaLocation", null, xsiSchemaLocation);

            for (int i = 0; i < Properties.Count; i++)
            {
                var p = Properties[i];
                p.Id = "d" + i;
                p.GetKeyElement().WriteTo(xml);
            }

            xml.WriteStartElement("graph", xmlns.NamespaceName);
            xml.WriteAttributeString("id", "G");
            xml.WriteAttributeString("edgedefault", "directed");
            xml.WriteAttributeString("parse.nodes", Graph.NodeCount().ToString(CultureInfo.InvariantCulture));
            xml.WriteAttributeString("parse.edges", Graph.ArcCount().ToString(CultureInfo.InvariantCulture));
            xml.WriteAttributeString("parse.order", "nodesfirst");
            DefinePropertyValues(xml, Graph);

            Dictionary<string, Node> nodeById = new Dictionary<string, Node>();
            if (NodeId == null)
                NodeId = new Dictionary<Node,string>();
            foreach (var kv in NodeId)
            {
                if (nodeById.ContainsKey(kv.Value))
                    throw new Exception("Duplicate node id " + kv.Value);
                nodeById[kv.Value] = kv.Key;
            }
            foreach (var node in Graph.Nodes())
            {
                string id;
                NodeId.TryGetValue(node, out id);
                if (id == null)
                {
                    id = node.Id.ToString(CultureInfo.InvariantCulture);
                    while (nodeById.ContainsKey(id))
                        id += '_';
                    NodeId[node] = id;
                    nodeById[id] = node;
                }

                xml.WriteStartElement("node", xmlns.NamespaceName);
                xml.WriteAttributeString("id", id);
                DefinePropertyValues(xml, node);
                xml.WriteEndElement(); // node
            }

            foreach (var arc in Graph.Arcs())
            {
                string id;
                if (ArcId != null)
                    ArcId.TryGetValue(arc, out id);
                else
                    id = null;
                
                xml.WriteStartElement("edge", xmlns.NamespaceName);
                if (id != null) xml.WriteAttributeString("id", id);
                if (Graph.IsEdge(arc)) xml.WriteAttributeString("directed", "false");
                xml.WriteAttributeString("source", NodeId[Graph.U(arc)]);
                xml.WriteAttributeString("target", NodeId[Graph.V(arc)]);
                DefinePropertyValues(xml, arc);
                xml.WriteEndElement(); // edge
            }

            xml.WriteEndElement(); // graph
            xml.WriteEndElement(); // graphml
        }

        public void Save(TextWriter writer)
        {
            using (XmlWriter xml = XmlWriter.Create(writer)) 
                Save(xml);
        }

        public void Save(string filename)
        {
            using (StreamWriter writer = new StreamWriter(filename))
                Save(writer);
        }
    }
}