summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua163
1 files changed, 163 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua
new file mode 100644
index 0000000000..32927530a2
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/pedigrees/Koerner2015.lua
@@ -0,0 +1,163 @@
+-- Copyright 2015 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header$
+
+
+local Koerner2015 = {}
+
+
+-- Namespace
+require("pgf.gd.pedigrees").Koerner2015 = Koerner2015
+
+-- Imports
+local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms"
+local Storage = require "pgf.gd.lib.Storage"
+local Direct = require "pgf.gd.lib.Direct"
+
+-- Shorthand:
+local declare = InterfaceToAlgorithms.declare
+
+
+---
+declare {
+ key = "mate",
+ type = "boolean",
+
+ summary = [["
+ Edges of type |mate| join mates.
+ "]],
+}
+
+
+---
+declare {
+ key = "child",
+ type = "boolean",
+
+ summary = [["
+ Edges of type |child| join a parent to a child. The parent is the tail
+ of the edge, the child is the head.
+ "]],
+}
+
+---
+declare {
+ key = "sibling",
+ type = "boolean",
+
+ summary = [["
+ Edges of type |sibling| join a siblings (persons with identical parents).
+ "]],
+}
+
+
+---
+declare {
+ key = "simple pedigree layout",
+ algorithm = Koerner2015,
+
+ postconditions = {
+ upward_oriented = true
+ },
+
+ summary = [["
+ A simple algorithm for drawing a pedigree.
+ "]],
+ documentation = [["
+ ...
+ "]],
+ examples = [["
+ \tikz \graph [simple pedigree layout, default edge operator=complete bipartite]
+ {
+ Eve -- [mate] Felix;
+ { Eve, Felix } -> [child] { George, Hank };
+
+ Alice -- [mate] Bob;
+ { Alice, Bob } -> [child] { Charly, Dave, Eve };
+ };
+ "]]
+}
+
+
+function Koerner2015:run()
+
+ local g = self.digraph
+
+ -- Compute ranks:
+
+ local visited = {}
+ local ranks = {}
+
+ local queue = { { g.vertices[1], 1 } }
+
+ local queue_start = 1
+ local queue_end = 1
+
+ local function put(v, r)
+ queue_end = queue_end + 1
+ queue [queue_end] = { v, r }
+ end
+
+ local function get()
+ local v = queue[queue_start][1]
+ local r = queue[queue_start][2]
+ queue_start = queue_start + 1
+ return v,r
+ end
+
+ while queue_start <= queue_end do
+
+ -- Pop
+ local v, rank = get()
+ ranks[v] = rank
+
+ visited [v] = true
+
+ -- Follow mates:
+ for _,a in ipairs(g:outgoing(v)) do
+ if a:options("sibling") then
+ if not visited[a.head] then
+ put(a.head, rank)
+ end
+ end
+ end
+ for _,a in ipairs(g:incoming(v)) do
+ if a:options("child") then
+ if not visited[a.tail] then
+ put(a.tail, rank-1)
+ end
+ end
+ end
+ for _,a in ipairs(g:outgoing(v)) do
+ if a:options("child") then
+ if not visited[a.head] then
+ put(a.head, rank+1)
+ end
+ end
+ end
+ for _,a in ipairs(g:outgoing(v)) do
+ if a:options("mate") then
+ if not visited[a.head] then
+ put(a.head, rank)
+ end
+ end
+ end
+ end
+
+ for i,v in ipairs(g.vertices) do
+ v.pos.x = i*50
+ v.pos.y = ranks[v] * 50
+ end
+
+end
+
+return Koerner2015
+
+