Implement loading of graph from a graph described in Dot language

[KeRNeLith]

Implement loading of graph from a graph described in Dot language.

The library had a minimal API definition for this, here are the basis:

using System;
using System.Collections.Generic;
using JetBrains.Annotations;

namespace QuikGraph
{
    using Attributes = IDictionary<string, string>;

    /// <summary>
    /// Dot parser adapter, offers features to load graph from dot.
    /// </summary>
    public class DotParserAdapter
    {
        /// <summary>
        /// Loads the given <paramref name="dotSource"/> and creates the corresponding graph.
        /// </summary>
        /// <param name="dotSource">Dot source string.</param>
        /// <param name="createGraph">Graph constructor function.</param>
        /// <param name="vertexFunction">Packing function (See <see cref="VertexFactory"/> class).</param>
        /// <param name="edgeFunction">Packing function (See <see cref="EdgeFactory{TVertex}"/> class).</param>
        /// <exception cref="NotImplementedException">This method is not implemented yet.</exception>
        [Pure]
        [NotNull]
        internal static IMutableVertexAndEdgeSet<TVertex, TEdge> LoadDot<TVertex, TEdge>(
            [NotNull] string dotSource,
            [NotNull, InstantHandle] Func<bool, IMutableVertexAndEdgeSet<TVertex, TEdge>> createGraph,
            [NotNull, InstantHandle] Func<string, Attributes, TVertex> vertexFunction,
            [NotNull, InstantHandle] Func<TVertex, TVertex, Attributes, TEdge> edgeFunction)
            where TEdge : IEdge<TVertex>
        {
            //var graphData = DotParser.parse(dotSource);
            //var graph = createGraph(!graphData.IsStrict);

            //var vertices = graphData.Nodes.ToDictionary(v => v.Key, v => vertexFunction(v.Key, v.Value));
            //graph.AddVertexRange(vertices.Values);

            //foreach (var parallelEdges in graphData.Edges)
            //{
            //    var edgeVertices = parallelEdges.Key;
            //    foreach (var attr in parallelEdges.Value)
            //    {
            //        graph.AddEdge(edgeFunction(vertices[edgeVertices.Item1], vertices[edgeVertices.Item2], attr));
            //        if (graph.IsDirected && !graphData.IsDirected)
            //        {
            //            graph.AddEdge(edgeFunction(vertices[edgeVertices.Item2], vertices[edgeVertices.Item1], attr));
            //        }
            //    }
            //}
            //return graph;
            throw new NotImplementedException();
        }

        /// <summary>
        /// Helpers to get weight from attributes.
        /// </summary>
        public class WeightHelpers
        {
            [NotNull]
            private const string Weight = "weight";

            /// <summary>
            /// Gets the <see cref="Weight"/> attribute if available.
            /// </summary>
            /// <param name="attributes">Attributes.</param>
            /// <returns>Found weight, null otherwise.</returns>
            [CanBeNull]
            public static int? GetWeight([NotNull] Attributes attributes)
            {
                return int.TryParse(attributes["weight"], out int weight) ? (int?)weight : null;
            }

            /// <summary>
            /// Gets the <see cref="Weight"/> attribute if available,
            /// and fallback on <paramref name="defaultValue"/> if not found.
            /// </summary>
            /// <param name="attributes">Attributes.</param>
            /// <param name="defaultValue">Default weight value.</param>
            /// <returns>Found weight, otherwise returns the <paramref name="defaultValue"/>.</returns>
            public static int GetWeight([NotNull] Attributes attributes, int defaultValue)
            {
                if (!attributes.TryGetValue("weight", out string weightAttribute))
                    return defaultValue;

                return int.TryParse(weightAttribute, out int weight)
                    ? weight
                    : defaultValue;
            }
        }

        /// <summary>
        /// Vertex factory.
        /// </summary>
        public class VertexFactory
        {
            /// <summary>
            /// Gets the vertex name.
            /// </summary>
            [NotNull]
            public static Func<string, Attributes, string> Name = (vertex, attributes) => vertex;

            /// <summary>
            /// Gets the vertex name and its attributes.
            /// </summary>
            [NotNull]
            public static Func<string, Attributes, KeyValuePair<string, Attributes>> NameAndAttributes =
                (vertex, attributes) => new KeyValuePair<string, Attributes>(vertex, new Dictionary<string, string>(attributes));

            /// <summary>
            /// Gets the vertex weight (if available).
            /// </summary>
            [NotNull]
            public static Func<string, Attributes, KeyValuePair<string, int?>> WeightedNullable =
                (vertex, attributes) => new KeyValuePair<string, int?>(vertex, WeightHelpers.GetWeight(attributes));

            /// <summary>
            /// Gets the vertex weight (with fallback value).
            /// </summary>
            [NotNull]
            public static Func<string, Attributes, KeyValuePair<string, int>> Weighted(int defaultValue) =>
                (vertex, attributes) => new KeyValuePair<string, int>(vertex, WeightHelpers.GetWeight(attributes, defaultValue));
        }

        /// <summary>
        /// Edge factory.
        /// </summary>
        /// <typeparam name="TVertex">Vertex type.</typeparam>
        public class EdgeFactory<TVertex>
        {
            /// <summary>
            /// Gets the edge vertices.
            /// </summary>
            [NotNull]
            public static Func<TVertex, TVertex, Attributes, SEdge<TVertex>> VerticesOnly =
                (vertex1, vertex2, attributes) => new SEdge<TVertex>(vertex1, vertex2);

            /// <summary>
            /// Gets the edge vertices and its attributes.
            /// </summary>
            [NotNull]
            public static Func<TVertex, TVertex, Attributes, STaggedEdge<TVertex, Attributes>> VerticesAndEdgeAttributes =
                (vertex1, vertex2, attributes) => new STaggedEdge<TVertex, Attributes>(vertex1, vertex2, new Dictionary<string, string>(attributes));

            /// <summary>
            /// Gets the edge vertices and weight (if available).
            /// </summary>
            [NotNull]
            public static Func<TVertex, TVertex, Attributes, STaggedEdge<TVertex, int?>> WeightedNullable =
                (vertex1, vertex2, attributes) => new STaggedEdge<TVertex, int?>(vertex1, vertex2, WeightHelpers.GetWeight(attributes));

            /// <summary>
            /// Gets the edge vertices and weight (with fallback value).
            /// </summary>
            [NotNull]
            public static Func<TVertex, TVertex, Attributes, STaggedEdge<TVertex, int>> Weighted(int defaultValue) =>
                (vertex1, vertex2, attributes) => new STaggedEdge<TVertex, int>(vertex1, vertex2, WeightHelpers.GetWeight(attributes, defaultValue));
        }
    }
}

and

using System;
using System.Collections.Generic;
using JetBrains.Annotations;

namespace QuikGraph
{
    /// <summary>
    /// Helpers to load graph from dot string.
    /// </summary>
    public static class DotGraphLoader
    {
        [Pure]
        [NotNull]
        private static TGraph LoadGraphFromDot<TVertex, TEdge, TGraph>(
            [NotNull] string dotSource,
            [NotNull, InstantHandle] Func<bool, TGraph> createGraph,
            [NotNull, InstantHandle] Func<string, IDictionary<string, string>, TVertex> vertexFactory,
            [NotNull, InstantHandle] Func<TVertex, TVertex, IDictionary<string, string>, TEdge> edgeFactory)
            where TEdge : IEdge<TVertex>
            where TGraph : IMutableVertexAndEdgeSet<TVertex, TEdge>
        {
#if SUPPORTS_CONTRACTS
            Contract.Requires(dotSource != null);
            Contract.Requires(createGraph != null);
            Contract.Requires(vertexFactory != null);
            Contract.Requires(edgeFactory != null);
#endif

            return (TGraph)DotParserAdapter.LoadDot(
                dotSource,
                allowParallelEdges => createGraph(allowParallelEdges),
                vertexFactory,
                edgeFactory);
        }

        /// <summary>
        /// Loads an <see cref="AdjacencyGraph{TVertex,TEdge}"/> from a dot string.
        /// </summary>
        /// <typeparam name="TVertex">Vertex type.</typeparam>
        /// <typeparam name="TEdge">Edge type.</typeparam>
        /// <param name="dotSource">Dot string representing a graph.</param>
        /// <param name="vertexFactory">Vertex factory method.</param>
        /// <param name="edgeFactory">Edge factory method.</param>
        /// <returns>A corresponding <see cref="AdjacencyGraph{TVertex,TEdge}"/>.</returns>
        [Pure]
        [NotNull]
        public static AdjacencyGraph<TVertex, TEdge> LoadAdjacencyGraphFromDot<TVertex, TEdge>(
            [NotNull] string dotSource,
            [NotNull, InstantHandle] Func<string, IDictionary<string, string>, TVertex> vertexFactory,
            [NotNull, InstantHandle] Func<TVertex, TVertex, IDictionary<string, string>, TEdge> edgeFactory)
            where TEdge : IEdge<TVertex>
        {
            return LoadGraphFromDot(
                dotSource,
                allowParallelEdges => new AdjacencyGraph<TVertex, TEdge>(allowParallelEdges),
                vertexFactory,
                edgeFactory);
        }

        /// <summary>
        /// Loads an <see cref="UndirectedGraph{TVertex,TEdge}"/> from a dot string.
        /// </summary>
        /// <typeparam name="TVertex">Vertex type.</typeparam>
        /// <typeparam name="TEdge">Edge type.</typeparam>
        /// <param name="dotSource">Dot string representing a graph.</param>
        /// <param name="vertexFactory">Vertex factory method.</param>
        /// <param name="edgeFactory">Edge factory method.</param>
        /// <returns>A corresponding <see cref="UndirectedGraph{TVertex,TEdge}"/>.</returns>
        [Pure]
        [NotNull]
        public static UndirectedGraph<TVertex, TEdge> LoadUndirectedGraphFromDot<TVertex, TEdge>(
            [NotNull] string dotSource,
            [NotNull, InstantHandle] Func<string, IDictionary<string, string>, TVertex> vertexFactory,
            [NotNull, InstantHandle] Func<TVertex, TVertex, IDictionary<string, string>, TEdge> edgeFactory)
            where TEdge : IEdge<TVertex>
        {
            return LoadGraphFromDot(
                dotSource,
                allowParallelEdges => new UndirectedGraph<TVertex, TEdge>(allowParallelEdges),
                vertexFactory,
                edgeFactory);
        }

        /// <summary>
        /// Loads an <see cref="BidirectionalGraph{TVertex,TEdge}"/> from a dot string.
        /// </summary>
        /// <typeparam name="TVertex">Vertex type.</typeparam>
        /// <typeparam name="TEdge">Edge type.</typeparam>
        /// <param name="dotSource">Dot string representing a graph.</param>
        /// <param name="vertexFactory">Vertex factory method.</param>
        /// <param name="edgeFactory">Edge factory method.</param>
        /// <returns>A corresponding <see cref="BidirectionalGraph{TVertex,TEdge}"/>.</returns>
        [Pure]
        [NotNull]
        public static BidirectionalGraph<TVertex, TEdge> LoadBidirectionalGraphFromDot<TVertex, TEdge>(
            [NotNull] string dotSource,
            [NotNull, InstantHandle] Func<string, IDictionary<string, string>, TVertex> vertexFactory,
            [NotNull, InstantHandle] Func<TVertex, TVertex, IDictionary<string, string>, TEdge> edgeFactory)
            where TEdge : IEdge<TVertex>
        {
            return LoadGraphFromDot(
                dotSource,
                allowParallelEdges => new BidirectionalGraph<TVertex, TEdge>(allowParallelEdges),
                vertexFactory,
                edgeFactory);
        }
    }
}

[pavel-agarkov]

Hi! Is there any workaround right now to parse existing dot file?

[KeRNeLith]

Hello,
Since the loading of dot file was a commented code I took the decision to remove it from the library and open this issue. So QuikGraph does not provide at the moment any dot parsing logic.
It is indeed a nice improvement to do for the library to add this support. For now there are some existing stuff that should parse dot like DotParser library or GraphViz4Net. Note that using a well defined grammar you may also directly use Antlr to parse those files.

Maybe doing a small support of dot loading would be possible if we do not need to take into account all "display" stuff of dot language and only focus on the loading of a graph data.

[pavel-agarkov]

Yes, DotParser did the trick, but I decided to switch to PlantUML and now I'm parsing final MSI files instead.