using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using MathGraph;
namespace CategoryTheory
{
/// <summary>
/// DiagramLimit
/// </summary>
public class CategoryDiagram
{
/// <summary>
/// Out of diagram test
/// </summary>
static public readonly string ObjectOutOfDiagram = "Diagram does not contains object";
/// <summary>
/// Extra object in diagram text
/// </summary>
static public readonly string ExtraArrow = "Extra object";
/// <summary>
/// Shortage of in diagram text
/// </summary>
static public readonly string ArrowsShortage = "Shortage of arrows in diagram";
/// <summary>
/// Graph
/// </summary>
private Digraph graph;
/// <summary>
/// Arrows hashtable
/// </summary>
private Dictionary<CategoryObjectPair, ICategoryArrow> arrows = new Dictionary<CategoryObjectPair, ICategoryArrow>();
/// <summary>
/// Objects
/// </summary>
private IList<ICategoryObject> objects = new List<ICategoryObject>();
/// <summary>
/// Sources
/// </summary>
private Dictionary<ICategoryObject, IList<ICategoryArrow>> sources = new Dictionary<ICategoryObject, IList<ICategoryArrow>>();
/// <summary>
/// Targets
/// </summary>
private Dictionary<ICategoryObject, IList<ICategoryArrow>> targets = new Dictionary<ICategoryObject, IList<ICategoryArrow>>();
/// <summary>
/// Category
/// </summary>
private ICategory category;
/// <summary>
/// Limit
/// </summary>
private ICategoryObject lim;
/// <summary>
/// Limit arrow
/// </summary>
private ICategoryArrow limArrow;
/// <summary>
/// Limit id arrows
/// </summary>
private IList<ICategoryArrow> limIdArrows;
/// <summary>
/// Limit function arrowa
/// </summary>
private List<ICategoryArrow> limFuncArrows;
/// <summary>
/// Lim id arrow
/// </summary>
private ICategoryArrow limIdArrow;
/// <summary>
/// Limit fuctional arrow
/// </summary>
private ICategoryArrow limFuncArrow;
/// <summary>
/// Limit arrows
/// </summary>
private Dictionary<ICategoryObject, ICategoryArrow> limArrows;
/// <summary>
/// Colimit
/// </summary>
private ICategoryObject colim;
/// <summary>
/// Colimit arrow
/// </summary>
private ICategoryArrow colimArrow;
/// <summary>
/// Colimit id arrows
/// </summary>
private Dictionary<ICategoryObject, ICategoryArrow> colimArrows;
/// <summary>
/// Colimit function arrowa
/// </summary>
private IList<ICategoryArrow> colimFuncArrows;
/// <summary>
/// Colim id arrow
/// </summary>
private ICategoryArrow colimIdArrow;
/// <summary>
/// Colimit fuctional arrow
/// </summary>
private ICategoryArrow colimFuncArrow;
/// <summary>
/// Coimit arrows
/// </summary>
private IList<ICategoryArrow> colimIdArrows;
/// <summary>
/// Constructor
/// </summary>
/// <param name="graph">Graph</param>
/// <param name="category">Category</param>
public CategoryDiagram(Digraph graph, ICategory category)
{
this.graph = graph;
this.category = category;
for (int i = 0; i < graph.Count; i++)
{
ICategoryObject o = graph[i].Object as ICategoryObject;
CategoryObjectPair idPair = new CategoryObjectPair(o, o);
ICategoryArrow id = o.Id;
arrows[idPair] = id;
objects.Add(o);
IList<ICategoryArrow> s = new List<ICategoryArrow>();
s.Add(id);
sources[o] = s;
IList<ICategoryArrow> t = new List<ICategoryArrow>();
t.Add(id);
targets[o] = t;
}
for (int i = 0; i < graph.Count; i++)
{
DigraphVertex o = graph[i];
getPaths(o, o);
}
}
/// <summary>
/// Count of objects
/// </summary>
public int Count
{
get
{
return objects.Count;
}
}
/// <summary>
/// Digraph
/// </summary>
public Digraph Graph
{
get
{
return graph;
}
}
/// <summary>
/// Access to i th object
/// </summary>
public ICategoryObject this[int i]
{
get
{
return objects[i] as ICategoryObject;
}
}
/// <summary>
/// Access to arrow by pair
/// </summary>
public ICategoryArrow this[CategoryObjectPair p]
{
get
{
return arrows[p] as ICategoryArrow;
}
}
/// <summary>
/// Gets outcoming arrows
/// </summary>
/// <param name="o">The soutrce</param>
/// <returns>List of outcoming arrows</returns>
public IList<ICategoryArrow> GetOutcomingArrows(ICategoryObject o)
{
return sources[o];
}
/// <summary>
/// Gets incoming arrows
/// </summary>
/// <param name="o">The target</param>
/// <returns>List of outcoming arrows</returns>
public IList<ICategoryArrow> GetIncomingArrows(ICategoryObject o)
{
return targets[o];
}
/// <summary>
/// Keys of arrows table
/// </summary>
public ICollection Keys
{
get
{
return arrows.Keys;
}
}
/// <summary>
/// Gets arrow from limit to diagram object
/// </summary>
/// <param name="o">The diagram object</param>
/// <returns>The arrow</returns>
public ICategoryArrow GetLimArrow(ICategoryObject o)
{
return limArrows[o] as ICategoryArrow;
}
/// <summary>
/// Limit
/// </summary>
public ICategoryObject Lim
{
get
{
if (lim == null)
{
createLim();
}
return lim;
}
}
/// <summary>
/// Gets arrow to lim
/// </summary>
/// <param name="arrows">Arrows to objects</param>
/// <returns>The arrow to lim</returns>
public ICategoryArrow GetArrowToLim(ArrayList arrows)
{
Hashtable arrowsHash = new Hashtable();
ICategoryObject source = null;
foreach (ICategoryArrow arrow in arrows)
{
if (source == null)
{
source = arrow.Source;
}
if (source != arrow.Source)
{
throw new CategoryException(CategoryException.DifferentSources,
new ICategoryObject[] { source, arrow.Source });
}
if (!objects.Contains(arrow.Target))
{
throw new CategoryException(ObjectOutOfDiagram, arrow.Target);
}
if (arrowsHash.ContainsKey(arrow.Target))
{
throw new CategoryException(ExtraArrow, arrow);
}
arrowsHash[arrow.Target] = arrow;
}
foreach (object o in objects)
{
if (!arrowsHash.ContainsKey(o))
{
throw new CategoryException(ArrowsShortage, o);
}
}
foreach (CategoryObjectPair pair in Keys)
{
ICategoryArrow ar = this[pair];
ICategoryArrow first = arrowsHash[pair.Source] as ICategoryArrow;
ICategoryArrow second = arrowsHash[pair.Target] as ICategoryArrow;
ICategoryArrow composition = ar.Compose(category, first);
if (!composition.Equals(second))
{
throw new CategoryException(CategoryException.NonCommutativePath, ar);
}
}
Dictionary<int, ICategoryArrow> sortedTable = new Dictionary<int, ICategoryArrow>();
foreach (ICategoryArrow ar in arrows)
{
int i = objects.IndexOf(ar.Target);
sortedTable[i] = ar;
}
IList<ICategoryArrow> sortedArrows = new List<ICategoryArrow>();
for (int i = 0; i < sortedTable.Count; i++)
{
sortedArrows.Add(sortedTable[i]);
}
IDirectProductCategory productCategory = category as IDirectProductCategory;
ICategoryArrow arrowToProduct =
productCategory.GetArrowToDirectProduct(source, limIdArrow.Source, sortedArrows);
IEqualizerCategory equalizerCategory = category as IEqualizerCategory;
ICategoryArrow res = equalizerCategory.GetArrowToEqualizer(limArrow,
arrowToProduct, limIdArrow, limFuncArrow);
return res;
}
/// <summary>
/// Gets arrow from limit to diagram object
/// </summary>
/// <param name="o">The diagram object</param>
/// <returns>The arrow</returns>
public ICategoryArrow GetColimArrow(ICategoryObject o)
{
return colimArrows[o] as ICategoryArrow;
}
/// <summary>
/// Limit
/// </summary>
public ICategoryObject Colim
{
get
{
if (colim == null)
{
createColim();
}
return colim;
}
}
/// <summary>
/// Gets arrow from colim
/// </summary>
/// <param name="arrows">Arrows from objects</param>
/// <returns>Arrow from colim</returns>
public ICategoryArrow GetArrowFromColim(IList<ICategoryArrow> arrows)
{
Hashtable arrowsHash = new Hashtable();
ICategoryObject target = null;
foreach (ICategoryArrow arrow in arrows)
{
if (target == null)
{
target = arrow.Target;
}
if (target != arrow.Target)
{
throw new CategoryException(CategoryException.DifferentTargets,
new ICategoryObject[] { target, arrow.Target });
}
if (!objects.Contains(arrow.Source))
{
throw new CategoryException(ObjectOutOfDiagram, arrow.Source);
}
if (arrowsHash.ContainsKey(arrow.Source))
{
throw new CategoryException(ExtraArrow, arrow);
}
arrowsHash[arrow.Source] = arrow;
}
foreach (object o in objects)
{
if (!arrowsHash.ContainsKey(o))
{
throw new CategoryException(ArrowsShortage, o);
}
}
foreach (CategoryObjectPair pair in Keys)
{
ICategoryArrow ar = this[pair];
ICategoryArrow first = arrowsHash[pair.Target] as ICategoryArrow;
ICategoryArrow second = arrowsHash[pair.Source] as ICategoryArrow;
ICategoryArrow composition = first.Compose(category, ar);
if (!composition.Equals(second))
{
throw new CategoryException(CategoryException.NonCommutativePath, ar);
}
}
Dictionary<int, ICategoryArrow> sortedTable = new Dictionary<int, ICategoryArrow>();
foreach (ICategoryArrow ar in arrows)
{
int i = objects.IndexOf(ar.Source);
sortedTable[i] = ar;
}
IList<ICategoryArrow> sortedArrows = new List<ICategoryArrow>();
for (int i = 0; i < sortedTable.Count; i++)
{
sortedArrows.Add(sortedTable[i]);
}
IDirectSumCategory sumCategory = category as IDirectSumCategory;
ICategoryArrow arrowFromSum =
sumCategory.GetArrowFromDirectSum(target, colimIdArrow.Target, sortedArrows);
ICoequalizerCategory coequalizerCategory = category as ICoequalizerCategory;
ICategoryArrow res = coequalizerCategory.GetArrowFromCoequalizer(colimArrow,
arrowFromSum, colimIdArrow, colimFuncArrow);
return res;
}
/// <summary>
/// Creates limit
/// </summary>
private void createLim()
{
if (!(category is IDirectProductCategory))
{
throw new CategoryException(CategoryException.DirectProductNotSupported);
}
if (!(category is IEqualizerCategory))
{
throw new CategoryException(CategoryException.EqualizerNotSupported);
}
IDirectProductCategory productCategory = category as IDirectProductCategory;
IList<ICategoryArrow> firstArrows = new List<ICategoryArrow>();
ICategoryObject firstProduct = productCategory.GetDirectProduct(objects, firstArrows);
IList<ICategoryObject> endObjects = new List<ICategoryObject>();
foreach (CategoryObjectPair o in arrows.Keys)
{
ICategoryArrow a = arrows[o] as ICategoryArrow;
endObjects.Add(a.Target);
}
IList<ICategoryArrow> secondArrows = new List<ICategoryArrow>();
ICategoryObject secondProduct = productCategory.GetDirectProduct(endObjects, secondArrows);
limIdArrows = new List<ICategoryArrow>();
foreach (ICategoryArrow tar in secondArrows)
{
ICategoryObject t = tar.Target;
foreach (ICategoryArrow proj in firstArrows)
{
if (proj.Target == t)
{
limIdArrows.Add(proj);
break;
}
}
}
limIdArrow = productCategory.GetArrowToDirectProduct(firstProduct, secondProduct, limIdArrows);
limFuncArrows = new List<ICategoryArrow>();
foreach (CategoryObjectPair o in arrows.Keys)
{
ICategoryArrow tar = this[o];
foreach (ICategoryArrow proj in firstArrows)
{
if (proj.Target == tar.Source)
{
ICategoryArrow ar = tar.Compose(category, proj);
limFuncArrows.Add(ar);
break;
}
}
}
limFuncArrow = productCategory.GetArrowToDirectProduct(firstProduct, secondProduct, limFuncArrows);
IEqualizerCategory equalizerCategory = category as IEqualizerCategory;
limArrow = equalizerCategory.GetEqualizer(limIdArrow, limFuncArrow);
lim = limArrow.Source;
limArrows = new Dictionary<ICategoryObject, ICategoryArrow>();
foreach (ICategoryArrow proj in firstArrows)
{
ICategoryObject t = proj.Target;
ICategoryArrow ar = proj.Compose(category, limArrow);
limArrows[t] = ar;
}
}
/// <summary>
/// Creates limit
/// </summary>
private void createColim()
{
if (!(category is IDirectSumCategory))
{
throw new CategoryException(CategoryException.DirectSumNotSupported);
}
if (!(category is IEqualizerCategory))
{
throw new CategoryException(CategoryException.CoequalizerNotSupported);
}
IDirectSumCategory sumCategory = category as IDirectSumCategory;
IList<ICategoryArrow> firstArrows = new List<ICategoryArrow>();
ICategoryObject firstSum = sumCategory.GetDirectSum(objects, firstArrows);
IList<ICategoryObject> beginObjects = new List<ICategoryObject>();
foreach (CategoryObjectPair o in arrows.Keys)
{
ICategoryArrow a = arrows[o];
beginObjects.Add(a.Source);
}
IList<ICategoryArrow> secondArrows = new List<ICategoryArrow>();
ICategoryObject secondSum = sumCategory.GetDirectSum(beginObjects, secondArrows);
colimIdArrows = new List<ICategoryArrow>();
foreach (ICategoryArrow sar in secondArrows)
{
ICategoryObject s = sar.Source;
foreach (ICategoryArrow proj in firstArrows)
{
if (proj.Source == s)
{
colimIdArrows.Add(proj);
break;
}
}
}
colimIdArrow = sumCategory.GetArrowFromDirectSum(firstSum, secondSum, colimIdArrows);
colimFuncArrows = new List<ICategoryArrow>();
foreach (CategoryObjectPair o in arrows.Keys)
{
ICategoryArrow sar = this[o];
foreach (ICategoryArrow proj in firstArrows)
{
if (proj.Source == sar.Target)
{
ICategoryArrow ar = proj.Compose(category, sar);
colimFuncArrows.Add(ar);
break;
}
}
}
colimFuncArrow = sumCategory.GetArrowFromDirectSum(firstSum, secondSum, colimFuncArrows);
ICoequalizerCategory coequalizerCategory = category as ICoequalizerCategory;
colimArrow = coequalizerCategory.GetCoequalizer(colimIdArrow, colimFuncArrow);
colim = colimArrow.Target;
colimArrows = new Dictionary<ICategoryObject, ICategoryArrow>();
foreach (ICategoryArrow proj in firstArrows)
{
ICategoryObject s = proj.Source;
ICategoryArrow ar = colimArrow.Compose(category, proj);
colimArrows[s] = ar;
}
}
/// <summary>
/// Gets paths
/// </summary>
/// <param name="v">Root object</param>
/// <param name="ob">Current object</param>
private void getPaths(DigraphVertex v, DigraphVertex ob)
{
CategoryObjectPair pair = new CategoryObjectPair(v.Object as ICategoryObject,
ob.Object as ICategoryObject);
ICategoryArrow theArrow = this[pair];
foreach (DigraphEdge edge in ob.OutcomingEdges)
{
DigraphVertex vo = edge.Target;
ICategoryArrow ar = edge.Object as ICategoryArrow;
CategoryObjectPair p = new CategoryObjectPair(v.Object as ICategoryObject, ar.Target);
ICategoryArrow newArrow = ar.Compose(category, theArrow);
if (arrows.ContainsKey(p))
{
ICategoryArrow prev = this[p];
ICategoryArrow comp = ar.Compose(category, theArrow);
if (!prev.Equals(newArrow))
{
throw new CategoryException(CategoryException.NonCommutativePath);
}
continue;
}
arrows[p] = newArrow;
IList<ICategoryArrow> s = sources[p.Source] as IList<ICategoryArrow>;
s.Add(newArrow);
IList<ICategoryArrow> t = targets[p.Target] as IList<ICategoryArrow>;
t.Add(newArrow);
getPaths(v, vo);
}
}
}
}
Submit an article or tip