多角形の完全グラフ - Gushwell's C# Programming Page

凸多角形の完全グラフ（一筆書き）

凸多角形の完全グラフを描くプログラムです。Silverlightアプリケーションとして作成しました。頂点の数が奇数のときは、一筆書きになるようにしています。偶数のときは一筆書きはできないので、とりあえず、完全グラフを描くようにしました。
頂点の数が奇数か偶数かで処理を分岐させないで、これをやれるようにしています（SearchPathメソッド）。
でもちょっとややこしい再帰処理になってしまいました。
PerfectGraphクラスのほうは、LINQ使ってそれぞれのメソッドを簡潔に書けたと思います。
完全グラフを作成する本質部分は、Silverlightに依存しないように作成していますので、WindowsFormsアプリに移植することもそれほど難しくはないと思います。

Startボタンを押せば、多角形の完全グラフを描くアニメーションが始まります。

■page.xaml

■page.xaml.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;

namespace SlPGraph
{
    public partial class Page : UserControl
    {
        public Page()
        {
            InitializeComponent();
        }
        private void DrawAnimatedLine(Point from, Point to)
        {
            var line = DrawInitialLine(from.X, from.Y);
            DoubleAnimation myAnimation1 = new DoubleAnimation();
            myAnimation1.To = to.X;
            myAnimation1.Duration = new Duration(TimeSpan.FromSeconds(0.3));
            Storyboard.SetTarget(myAnimation1, line);
            Storyboard.SetTargetProperty(myAnimation1, new PropertyPath("X2"));
            Storyboard myStoryboard = new Storyboard();
            myStoryboard.FillBehavior = FillBehavior.HoldEnd;
            myStoryboard.Children.Add(myAnimation1);

DoubleAnimation myAnimation2 = new DoubleAnimation();
            myAnimation2.To = to.Y;
            myAnimation2.Duration = new Duration(TimeSpan.FromSeconds(0.3));
            Storyboard.SetTarget(myAnimation2, line);
            Storyboard.SetTargetProperty(myAnimation2, new PropertyPath("Y2"));
            Storyboard myStoryboard2 = new Storyboard();
            myStoryboard2.FillBehavior = FillBehavior.HoldEnd;
            myStoryboard2.Children.Add(myAnimation2);

myStoryboard.Completed += new EventHandler(myStoryboard_Completed);
            myStoryboard.Begin();
            myStoryboard2.Begin();
        }

IEnumerator<Line> ite;
        void myStoryboard_Completed(object sender, EventArgs e)
        {
            bool r = ite.MoveNext();
            if (r)
            {
                Line line = ite.Current;
                DrawAnimatedLine(line.FromPoint(), line.ToPoint());
            }

}
        private void DrawPoint(Point p)
        {
            Ellipse ellipse = new Ellipse
            {
                Width = 5,
                Height = 5,
                Fill = new SolidColorBrush(Colors.Black),
            };
            canvas.Children.Add(ellipse);
            Canvas.SetLeft(ellipse, p.X - 3);
            Canvas.SetTop(ellipse, p.Y - 3);
        }

private Line DrawInitialLine(double x, double y)
        {
            Line line = new Line
            {
                Stroke = new SolidColorBrush(Color.FromArgb(0xff,0xb0,0xc4,0xde)),
                X1 = x,
                Y1 = y,
                X2 = x,
                Y2 = y,
                StrokeThickness = 2
            };
            canvas.Children.Add(line);
            return line;
        }
        //(x-a)2+(y-b)2=r2
        //X座標 ････ 中心のx座標 + 円周の半径 * Math.cos(角度のラジアン値) 
        //Y座標 ････ 中心のy座標 - 円周の半径 * Math.sin(角度のラジアン値) 
        private Point GetPoint(double angle)
        {
            angle += 90;
            Point p = new Point();
            p.X = 140 + 80 * Math.Cos(2 * Math.PI * angle / 360);
            p.Y = 120 - 80 * Math.Sin(2 * Math.PI * angle / 360);
            return p;
        }

private Point[] points;

public void SetPoints(int numOfTops)
        {
            points = new Point[numOfTops];
            double angle = 0;
            for (int i = 0; i < numOfTops; i++)
            {
                points[i] = GetPoint(angle);
                angle += 360 / (numOfTops);
            }
        }

private void button1_Click(object sender, RoutedEventArgs e)
        {
            canvas.Children.Clear();
            int num = 6;
            int.TryParse(textBox1.Text, out num);
            Solver sol = new Solver();
            PerfectGraph pg;
            pg = sol.GetPerfectGraph(num);
            SetPoints(num);
            foreach (var p in points)
                DrawPoint(p);
            List<Line> sequence = new List<Line>();
            foreach (var l in pg.GetLines())
            {
                sequence.Add(new Line
                {
                    X1 = points[l.From - 1].X,
                    Y1 = points[l.From - 1].Y,
                    X2 = points[l.To - 1].X,
                    Y2 = points[l.To - 1].Y
                });
            }
            ite = sequence.GetEnumerator();
            ite.MoveNext();
            Line line = ite.Current;
            DrawAnimatedLine(line.FromPoint(), line.ToPoint());

}
    }

static class LineExtentions
    {
        public static Point FromPoint(this Line line)
        {
            return new Point(line.X1, line.Y1);
        }
        public static Point ToPoint(this Line line)
        {
            return new Point(line.X2, line.Y2);
        }
    }

class Solver
    {
        private PerfectGraph pg;

public PerfectGraph GetPerfectGraph(int n)
        {
            pg = new PerfectGraph(n);
            SearchPath(1);
            return pg;
        }

private bool SearchPath(int now)
        {
            if (pg.IsPerfect())
            {
                return true;
            }
            bool isVanant = false;
            foreach (var line in pg.Candidates(now))
            {
                isVanant = true;
                pg.AddLine(line);
                if (SearchPath(line.To))
                    return true;
                pg.RemoveLine(line);
            }
            if (isVanant == false)
            { // その地点から線を引けない
                foreach (var p in pg.JumpPoints(now))
                {
                    VirtualLine temp = new VirtualLine(now, p);
                    if (SearchPath(p))
                        return true;
                }
            }
            return false;
        }

}

class PerfectGraph
    {
        // すでに引いた線を記憶しておく
        private List<VirtualLine> lines = new List<VirtualLine>();
        // 頂点の数
        private int _numOfApexes;

public PerfectGraph(int n)
        {
            NumOfApexes = n;
        }

// 引いた線のすべてを得る
        public IEnumerable<VirtualLine> GetLines()
        {
            return lines;
        }

// 頂点の番号1..NumOfApexesを順に得る
        public IEnumerable<int> Apexes()
        {
            return Enumerable.Range(1, NumOfApexes);
        }

// 頂点の数
        public int NumOfApexes
        {
            get { return _numOfApexes; }
            private set
            {
                _numOfApexes = value;
                VirtualLine.NumOfApexes = value;
            }
        }

// 線を引いたものとして記憶する
        public void AddLine(VirtualLine l)
        {
            lines.Add(l);
        }

// 引いた線をlinesから取り除く
        public void RemoveLine(VirtualLine l)
        {
            lines.Remove(l);
        }

// 引数で与えた線が既に引いてある線かを調べる。 true ならば引いてある
        public bool Contains(VirtualLine l)
        {
            return lines.Any(x => (x.From == l.From && x.To == l.To) || (x.From == l.To && x.To == l.From));
        }

// apexの位置から線が引けるか（空いている頂点があるか）を調べる 
        public bool CanDraw(int apex)
        {
            var q = Apexes()
                .Where(a => a != apex)
                .Select(a => new VirtualLine(a, apex));
            return !q.All(l => Contains(l));
        }

// 現在の頂点から引ける線のシーケンスを得る
        public IEnumerable<VirtualLine> Candidates(int now)
        {
            return Apexes().Where(p => p != now)
                .Select(p => new VirtualLine(now, p))
                .Where(line => Contains(line) == false)
                .OrderBy(line => line.Distance);
        }

// 別の頂点へ移動する
        public IEnumerable<int> JumpPoints(int now)
        {
            return Apexes().Where(p => p != now && CanDraw(p));
        }

// 完全グラフかを調べる
        public bool IsPerfect()
        {
            return Apexes().All(a => !CanDraw(a));
        }

// デバッグ用
        public void Print()
        {
            foreach (var l in lines)
            {
                Console.Write(l);
                Console.Write("  ");
            }
            Console.WriteLine();
        }
    }

class VirtualLine
    {
        static public int NumOfApexes { get; set; }
        public int From { get; set; }
        public int To { get; set; }
        public int Distance
        {
            get
            {
                int diff = Math.Abs(From - To);
                return (diff > (NumOfApexes / 2)) ? NumOfApexes - diff : diff;
            }
        }
        public VirtualLine(int a, int b)
        {
            From = a;
            To = b;
        }
        public override string ToString()
        {
            return string.Format("({0}, {1})", From, To);
        }
    }
}