Click here to Skip to main content
12,620,840 members (33,811 online)
Click here to Skip to main content

Stats

16.2K views
961 downloads
21 bookmarked
Posted

Signum Framework Tutorials Part 2 – Southwind Logic

, 15 Nov 2012 LGPL3
In this part, we will focus on writing business logic, LINQ queries and explain inheritance
Northwind.bak
signumframework-signumframework-c6436e1
.gitignore
Local.testsettings
README.md
Signum.Engine
ClassDiagram1.cd
Connection
DynamicQuery
Engine
Linq
ExpressionVisitor
Meta
Properties
Schema
Schema.cd
SchemaBuilder
SignumFramework.pfx
Signum.Entities
Attributes.cd
Basics
ClassDiagram1.cd
Diagram.cd
DynamicQuery
Tokens
Patterns
Properties
Reflection
Services
SignumFramework.pfx
Signum.Framework.vsmdi
Signum.Test
ClassDiagram1.cd
LinqProvider
Properties
Signum.Utilities
DataStructures
IntervalDictionaries
ExpressionTrees
Properties
Reflection
SignumFramework.pfx
Synchronization
Signum.Web
ButtonBar
ControllerAttributes
Facades
HtmlHelpers
JSRenderer
LineHelpers
Lines
Mappings
PortableAreas
Repositories
Properties
Signum
Content
Controllers
Images
asc.gif
calendar.png
desc.gif
lineButtons.gif
sign_error.gif
Models
Scripts
Views
Widgets
SignumFramework.pfx
TypeContext
Widgets
Signum.Windows
Basics
Controls
ColorUtils
Converters
DynamicQuery
EntityControls
Facades
Fluent
Images
admin.png
alert.png
calendar.png
cancel.png
close.png
entity.png
find.png
forbidden.png
newColumn.png
newFilter.png
note.png
ok.png
pin.png
reload.png
save.png
star.png
Localization
MarkupExtensions
Properties
SignumFramework.pfx
Themes
Utilities
Widgets
SignumFrameworkSetup
SignumFrameworkSetup.vdproj
logo.ico
signumFramework2.0.jpg
Snippets
DroidSansMono.ttf
RazorSingleFileGenerator.vsix
Signum.Fonts.vssettings
T4template
entity.snippet
entityWithName.snippet
expressionMethod.snippet
expressionMethodQuery.snippet
expressionProperty.snippet
field.snippet
fieldCreacion.snippet
fieldEuro.snippet
fieldInicioFin.snippet
fieldString.snippet
fiff.snippet
propiedad.snippet
tran.snippet
Template
EntityControlTemplate
MyTemplate.vstemplate
SignumEntityControl.zip
__TemplateIcon.ico
Template
MyTemplate.vstemplate
ProjectName.Entities
MyTemplate.vstemplate
Properties
__TemplateIcon.ico
ProjectName.Load
MyTemplate.vstemplate
Properties
__TemplateIcon.ico
ProjectName.Logic
MyTemplate.vstemplate
Properties
__TemplateIcon.ico
ProjectName.Web
Code
Content
smoothness
images
ui-bg_flat_0_aaaaaa_40x100.png
ui-bg_flat_75_ffffff_40x100.png
ui-bg_glass_55_fbf9ee_1x400.png
ui-bg_glass_65_ffffff_1x400.png
ui-bg_glass_75_dadada_1x400.png
ui-bg_glass_75_e6e6e6_1x400.png
ui-bg_glass_95_fef1ec_1x400.png
ui-bg_highlight-soft_75_cccccc_1x100.png
ui-icons_222222_256x240.png
ui-icons_2e83ff_256x240.png
ui-icons_454545_256x240.png
ui-icons_888888_256x240.png
ui-icons_cd0a0a_256x240.png
Controllers
Global.asax
MyTemplate.vstemplate
Properties
Scripts
ServerCapri.svc
Views
Capri
Home
Shared
__TemplateIcon.ico
favicon.ico
ProjectName.Windows
Controls
MyTemplate.vstemplate
Properties
__TemplateIcon.ico
SignumFramework2ClientServer.zip
__TemplateIcon.ico
WizardProjectName
Test
Properties
WizardProjectName
Isolated
Properties
SignumFramework.pfx
TraceAndTestImpact.testsettings
SignumFramework2Setup.msi
.gitignore
README.md
Southwind.vssscc
Southwind
Southwind.Entities
Properties
Southwind.Load
Properties
Southwind.Logic
Properties
Southwind.Web
Code
Content
smoothness
images
ui-bg_flat_0_aaaaaa_40x100.png
ui-bg_flat_75_ffffff_40x100.png
ui-bg_glass_55_fbf9ee_1x400.png
ui-bg_glass_65_ffffff_1x400.png
ui-bg_glass_75_dadada_1x400.png
ui-bg_glass_75_e6e6e6_1x400.png
ui-bg_glass_95_fef1ec_1x400.png
ui-bg_highlight-soft_75_cccccc_1x100.png
ui-icons_222222_256x240.png
ui-icons_2e83ff_256x240.png
ui-icons_454545_256x240.png
ui-icons_888888_256x240.png
ui-icons_cd0a0a_256x240.png
Controllers
Global.asax
Properties
Scripts
ServerSouthwind.svc
Views
Home
Shared
Southwind
favicon.ico
Southwind.Windows
Controls
Properties
Southwind.bak
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Signum.Utilities;
using System.Collections;
using Signum.Utilities.Properties;
using System.Xml.Linq;

namespace Signum.Utilities.DataStructures
{
    public class DirectedGraph<T> : IEnumerable<T>
    {
        Dictionary<T, HashSet<T>> adjacency;
        public IEqualityComparer<T> Comparer { get; private set; }

        public DirectedGraph()
            : this(EqualityComparer<T>.Default)
        {
        }

        public DirectedGraph(IEqualityComparer<T> comparer)
        {
            this.Comparer = comparer;
            this.adjacency = new Dictionary<T, HashSet<T>>(comparer);
        }

        public IEnumerable<T> Nodes
        {
            get { return adjacency.Keys; }
        }

        public IEnumerable<Edge<T>> Edges
        {
            get { return adjacency.SelectMany(k => k.Value.Select(n => new Edge<T>(k.Key, n))); }
        }

        public int Count
        {
            get { return adjacency.Count; }
        }

        public int EdgesCount
        {
            get { return adjacency.Sum(k => k.Value.Count); }
        }

        public bool Contains(T node)
        {
            return adjacency.ContainsKey(node);
        }

        public bool Connected(T from, T to)
        {
            return Get(from).Contains(to);
        }

        public bool TryConnected(T from, T to)
        {
            return TryGet(from).TryCS(hs => hs.Contains(to)) ?? false;
        }

        public void Add(T from)
        {
            TryGetOrAdd(from);
        }

        public void Add(T from, T to)
        {
            TryGetOrAdd(from).Add(to);
            TryGetOrAdd(to);
        }

        public void Add(T from, params T[] elements)
        {
            var f = TryGetOrAdd(from);
            foreach (var item in elements)
            {
                TryGetOrAdd(item);
                f.Add(item);
            }
        }

        public void Add(T from, IEnumerable<T> elements)
        {
            var f = TryGetOrAdd(from);
            foreach (var item in elements)
            {
                TryGetOrAdd(item);
                f.Add(item);
            }
        }

        public bool Remove(T from, T to)
        {
            var hashSet = adjacency.TryGetC(from);
            if (hashSet == null)
                return false;

            return hashSet.Remove(to);
        }

        public bool Remove(Edge<T> edge)
        {
            return Remove(edge.From, edge.To);
        }

        public void RemoveAll(IEnumerable<Edge<T>> edges)
        {
            foreach (var edge in edges)
                Remove(edge.From, edge.To);
        }

        public bool RemoveFullNode(T node)
        {
            if (!adjacency.ContainsKey(node))
                return false;

            return RemoveFullNode(node, InverseRelatedTo(node));
        }

        /// <summary>
        /// Unsafer but faster
        /// </summary>
        public bool RemoveFullNode(T node, IEnumerable<T> inverseRelated)
        {
            if (!adjacency.ContainsKey(node))
                return false;

            adjacency.Remove(node);
            foreach (var n in inverseRelated)
                Remove(n, node);

            return true;
        }

        public static void RemoveFullNodeSymetric(DirectedGraph<T> original, DirectedGraph<T> inverse, T node)
        {
            HashSet<T> from = inverse.RelatedTo(node);
            HashSet<T> to = original.RelatedTo(node);

            original.RemoveFullNode(node, from);
            inverse.RemoveFullNode(node, to);
        }

        HashSet<T> TryGet(T node)
        {
            return adjacency.TryGetC(node);
        }

        HashSet<T> Get(T node)
        {
            var result = adjacency.TryGetC(node);
            if (result == null)
                throw new InvalidOperationException("The node {0} is not in the graph".Formato(node));
            return result;
        }

        HashSet<T> TryGetOrAdd(T node)
        {
            return adjacency.GetOrCreate(node, () => new HashSet<T>(Comparer));
        }

        public HashSet<T> TryRelatedTo(T node)
        {
            return TryGet(node) ?? new HashSet<T>();
        }

        public HashSet<T> RelatedTo(T node)
        {
            return Get(node);
        }

        /// <summary>
        /// Costly
        /// </summary>
        public IEnumerable<T> InverseRelatedTo(T node)
        {
            return this.Where(n => Connected(n, node));
        }

        /// <summary>
        /// Recursive relationships
        /// </summary>
        public HashSet<T> IndirectlyRelatedTo(T node)
        {
            HashSet<T> set = new HashSet<T>();
            IndirectlyRelatedTo(node, set);
            return set;
        }

        void IndirectlyRelatedTo(T node, HashSet<T> set)
        {
            foreach (var item in RelatedTo(node))
                if (set.Add(item))
                    IndirectlyRelatedTo(item, set);
        }

        public HashSet<T> IndirectlyRelatedTo(T node, Func<T, bool> condition)
        {
            HashSet<T> set = new HashSet<T>();
            IndirectlyRelatedTo(node, set, condition);
            return set;
        }

        void IndirectlyRelatedTo(T node, HashSet<T> set, Func<T, bool> condition)
        {
            foreach (var item in RelatedTo(node).Where(condition))
                if (set.Add(item))
                    IndirectlyRelatedTo(item, set, condition);
        }


        public void DepthExplore(T node, Func<T, bool> condition, Action<T> preAction, Action<T> postAction)
        {
            if (condition != null && !condition(node))
                return;

            if (preAction != null)
                preAction(node);

            foreach (T item in RelatedTo(node))
                DepthExplore(item, condition, preAction, postAction);

            if (postAction != null)
                postAction(node);
        }

        public void BreadthExplore(T root, Func<T, bool> condition, Action<T> action)
        {
            Queue<T> queue = new Queue<T>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                T node = queue.Dequeue();
                if (!condition(node))
                    continue;

                action(node);

                queue.EnqueueRange(RelatedTo(node));
            }
        }


        public DirectedGraph<T> Inverse()
        {
            DirectedGraph<T> result = new DirectedGraph<T>(Comparer);
            foreach (var item in Nodes)
            {
                result.Add(item);
                foreach (var related in RelatedTo(item))
                {
                    result.Add(related, item);
                }
            }
            return result;
        }

        public DirectedGraph<T> UndirectedGraph()
        {
            return this.Inverse().Do(g => g.UnionWith(this));
        }

        public void UnionWith(DirectedGraph<T> other)
        {
            foreach (var item in other.Nodes)
                Add(item, other.RelatedTo(item));
        }

        public DirectedGraph<T> Clone()
        {
            return new DirectedGraph<T>(Comparer).Do(g => g.UnionWith(this));
        }

        public static DirectedGraph<T> Generate(T root, Func<T, IEnumerable<T>> expandFunction)
        {
            return Generate(root, expandFunction, EqualityComparer<T>.Default);
        }

        public static DirectedGraph<T> Generate(T root, Func<T, IEnumerable<T>> expandFunction, IEqualityComparer<T> comparer)
        {
            DirectedGraph<T> result = new DirectedGraph<T>(comparer);
            result.Expand(root, expandFunction);
            return result;
        }

        public static DirectedGraph<T> Generate(IEnumerable<T> roots, Func<T, IEnumerable<T>> expandFunction)
        {
            return Generate(roots, expandFunction, EqualityComparer<T>.Default);
        }

        public static DirectedGraph<T> Generate(IEnumerable<T> roots, Func<T, IEnumerable<T>> expandFunction, IEqualityComparer<T> comparer)
        {
            DirectedGraph<T> result = new DirectedGraph<T>(comparer);
            foreach (var root in roots)
                result.Expand(root, expandFunction);
            return result;
        }

        public void Expand(T node, Func<T, IEnumerable<T>> expandFunction)
        {
            if (Contains(node)) return;

            Add(node); //necesario para ciclos
            foreach (var item in expandFunction(node))
            {
                Expand(item, expandFunction);
                Add(node, item);
            }
        }

        public override string ToString()
        {
            return adjacency.ToString(kvp => "{0}=>{1};".Formato(kvp.Key, kvp.Value.ToString(",")), "\r\n");
        }

        public string Graphviz()
        {
            return Graphviz("Graph", a => a.ToString());
        }

        public string Graphviz(string name, Func<T, string> getName)
        {
            int num = 0;
            Dictionary<T, int> nodeDic = Nodes.ToDictionary(n => n, n => num++, Comparer);

            string nodes = Nodes.ToString(e => "   {0} [ label =\"{1}\"];".Formato(nodeDic[e], getName(e)), "\r\n");

            string edges = Edges.ToString(e => "   {0} -> {1};".Formato(nodeDic[e.From], nodeDic[e.To]), "\r\n");

            return "digraph \"{0}\"\r\n{{\r\n{1}\r\n{2}\r\n}}".Formato(name, nodes, edges);
        }

        public XDocument ToDGML()
        {
            return ToDGML(a => a.ToString() ?? "[null]", a => ColorGenerator.ColorFor(a.GetType().FullName.GetHashCode()));
        }

        public XDocument ToDGML(Func<T, string> getNodeLabel, Func<T, string> getColor)
        {
            return ToDGML(n => new[]
            {
                new XAttribute("Label", getNodeLabel(n)),
                new XAttribute("Background", getColor(n))
            });
        }
            
        public XDocument ToDGML(Func<T, XAttribute[]> attributes)
        {
            int num = 0;
            Dictionary<T, int> nodeDic = Nodes.ToDictionary(n => n, n => num++, Comparer);

            XNamespace ns = "http://schemas.microsoft.com/vs/2009/dgml";

            return new XDocument(
                new XElement(ns + "DirectedGraph",
                    new XElement(ns + "Nodes",
                        Nodes.Select(n => new XElement(ns + "Node",
                            new XAttribute("Id", nodeDic[n]),
                            attributes(n)))),
                    new XElement(ns + "Links",
                        Edges.Select(e => new XElement(ns + "Link",
                            new XAttribute("Source", nodeDic[e.From]),
                            new XAttribute("Target", nodeDic[e.To]))))
                 )
            );
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            return adjacency.Keys.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return adjacency.Keys.GetEnumerator();
        }

        #endregion

        public IEnumerable<HashSet<T>> CompilationOrderGroups()
        {
            DirectedGraph<T> clone = this.Clone();
            DirectedGraph<T> inv = this.Inverse();

            while (clone.Count > 0)
            {
                var leaves = clone.Sinks();
                foreach (var node in leaves)
                    clone.RemoveFullNode(node, inv.RelatedTo(node));
                yield return leaves;
            }
        }

        public IEnumerable<T> CompilationOrder()
        {
            return CompilationOrderGroups().SelectMany(e => e);
        }


        /// <summary>
        /// A simple but effective linear-time heuristic constructs a vertex ordering,
        /// just as in the topological sort heuristic above, and deletes any arc going from right to left. 
        /// 
        /// This heuristic builds up the ordering from the outside in based on the in- and out-degrees of each vertex. 
        /// - Any vertex of in-degree 0 is a source and can be placed first in the ordering. 
        /// - Any vertex of out-degree 0 is a sink and can be placed last in the ordering, again without violating any constraints. 
        /// - If not, we find the vertex with the maximum difference between in- and out-degree, 
        /// and place it on the side of the permutation that will salvage the greatest number of constraints. 
        /// Delete any vertex from the DAG after positioning it and repeat until the graph is empty.
        /// </summary>
        /// <returns></returns>

        public DirectedGraph<T> FeedbackEdgeSet()
        {
            DirectedGraph<T> result = new DirectedGraph<T>(Comparer);

            DirectedGraph<T> clone = this.Clone();
            DirectedGraph<T> inv = this.Inverse();

            HashSet<T> head = new HashSet<T>();  // for sources
            HashSet<T> tail = new HashSet<T>();  // for sinks
            while (clone.Count > 0)
            {
                var sinks = clone.Sinks();
                if (sinks.Count() != 0)
                {
                    foreach (var sink in sinks)
                    {
                        DirectedGraph<T>.RemoveFullNodeSymetric(clone, inv, sink);
                        tail.Add(sink);
                    }
                    continue;
                }

                var sources = inv.Sinks();
                if (sources.Count() != 0)
                {
                    foreach (var source in sources)
                    {
                        DirectedGraph<T>.RemoveFullNodeSymetric(clone, inv, source);
                        head.Add(source);
                    }
                    continue;
                }

                Func<T, int> fanInOut = n => clone.RelatedTo(n).Count() - inv.RelatedTo(n).Count();

                MinMax<T> mm = clone.WithMinMaxPair(fanInOut);

                if (fanInOut(mm.Max) > -fanInOut(mm.Min))
                {
                    T node = mm.Max;
                    foreach (var n in inv.RelatedTo(node))
                        result.Add(node, n);
                    DirectedGraph<T>.RemoveFullNodeSymetric(clone, inv, node);
                    head.Add(node);
                }
                else
                {
                    T node = mm.Min;
                    foreach (var n in clone.RelatedTo(node))
                        result.Add(node, n);
                    DirectedGraph<T>.RemoveFullNodeSymetric(clone, inv, node);
                    head.Add(node);
                }
            }

            return result;
        }

        private HashSet<T> Sinks()
        {
            return adjacency.Where(a => a.Value.Count == 0).Select(a => a.Key).ToHashSet();
        }

        public DirectedGraph<T> WhereEdges(Func<Edge<T>, bool> condition)
        {
            DirectedGraph<T> result = new DirectedGraph<T>(Comparer);
            foreach (var item in Nodes)
                result.Add(item, RelatedTo(item).Where(to => condition(new Edge<T>(item, to))));
            return result;
        }

        public List<T> ShortestPath(T from, T to)
        {
            //http://en.wikipedia.org/wiki/Dijkstra's_algorithm

            Dictionary<T, int> distance = this.ToDictionary(e => e, e => int.MaxValue, Comparer);
            Dictionary<T, T> previous = new Dictionary<T, T>(Comparer);

            distance[from] = 0;
            PriorityQueue<T> queue = new PriorityQueue<T>((a, b) => distance[a].CompareTo(distance[b]));
            queue.PushAll(this);

            while (queue.Count > 0)
            {
                T u = queue.Peek();
                if (distance[u] == int.MaxValue)
                    return null;

                int newDist = distance[u] + 1;
                foreach (var v in RelatedTo(u))
                {
                    if (newDist < distance[v])
                    {
                        distance[v] = newDist;
                        queue.Update(v);
                        previous[v] = u;
                    }
                }
                queue.Pop();

                if (Comparer.Equals(u, to))
                    break;
            }

            return to.For(n => previous.ContainsKey(n), n => previous[n]).Reverse().ToList();
        }
    }

    public struct Edge<T>
    {
        public readonly T From;
        public readonly T To;

        public Edge(T from, T to)
        {
            this.From = from;
            this.To = to;
        }

        public override string ToString()
        {
            return "{0}->{1}".Formato(From, To);
        }
    };

    public static class ColorGenerator
    {
        public static string ColorFor(int value)
        {
            return "#" + (value & 0xffffff).ToString("X6");
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)

Share

About the Author

Olmo del Corral
Software Developer (Senior) Signum Software
Spain Spain
I'm Computer Scientist, one of the founders of Signum Software, and the lead developer behind Signum Framework.

www.signumframework.com

I love programming in C#, Linq, Compilers, Algorithms, Functional Programming, Computer Graphics, Maths...

You may also be interested in...

Pro
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161128.1 | Last Updated 15 Nov 2012
Article Copyright 2011 by Olmo del Corral
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid