summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua592
1 files changed, 592 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
new file mode 100644
index 00000000000..ff08573cbbd
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua
@@ -0,0 +1,592 @@
+-- Copyright 2012 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/model/Arc.lua,v 1.6 2013/12/20 14:44:46 tantau Exp $
+
+
+---
+-- An arc is a light-weight object representing an arc from a vertex
+-- in a graph to another vertex. You may not create an |Arc| by
+-- yourself, which is why there is no |new| method, arc creation is
+-- done by the Digraph class.
+--
+-- Every arc belongs to exactly one graph. If you want the same arc in
+-- another graph, you need to newly connect two vertices in the other graph.
+--
+-- You may read the |head| and |tail| fields, but you may not write
+-- them. In order to store data for an arc, use |Storage| objects.
+--
+-- Between any two vertices of a graph there can be only one arc, so
+-- all digraphs are always simple graphs. However, in the
+-- specification of a graph (the syntactic digraph), there might
+-- be multiple edges between two vertices. This means, in particular,
+-- that an arc has no |options| field. Rather, it has several
+-- |optionsXxxx| functions, that will search for options in all of the
+-- synactic edges that ``belong'' to an edge.
+--
+-- Similarly, even though an arc has a |path| field, setting this
+-- field does not immediately set the paths of the syntactic
+-- edges. Indeed, you will normally want to setup and modify the
+-- |path| field of an arc during your algorithm and only at the very
+-- end, ``write it back'' to the multiple syntactic edges underlying
+-- the graph. For this purpose, the method |sync| is used, which is
+-- called automatically for the |ugraph| and |digraph| of a scope as
+-- well as for spanning trees.
+--
+-- The bottom line concerning the |path| field is the following: If
+-- you just want a straight line along an arc, just leave the field as
+-- it is (namely, |nil|). If you want to have all edges along a path
+-- to follow a certain path, set the |path| field of the arc to the
+-- path you desire (typically, using the |setPolylinePath| or a
+-- similar method). This will cause all syntactic edges underlying the
+-- arc to be set to the specified path. In the event that you want to
+-- set different paths for the edges underlying a single arc
+-- differently, set the |path| fields of these edges and set the
+-- |path| field of the arc to |nil|. This will disable the syncing for
+-- the arc and will cause the edge |paths| to remain untouched.
+--
+-- @field tail The tail vertex of the arc.
+-- @field head The head vertex of the arc. May be the same as the tail
+-- in case of a loop.
+-- @field path If non-nil, the path of the arc. See the description
+-- above.
+-- @field syntactic_edges This field is an array containing syntactic
+-- edges (``real'' edges in the syntactic digraph) that underly this
+-- arc.
+--
+local Arc = {}
+Arc.__index = Arc
+
+
+-- Namespace
+
+require("pgf.gd.model").Arc = Arc
+
+
+-- Imports
+
+local Path = require 'pgf.gd.model.Path'
+local lib = require 'pgf.gd.lib'
+
+
+---
+-- Get an array of options of the syntactic edges corresponding to an arc.
+--
+-- An arc in a digraph is typically (but not always) present because
+-- there are one or more edges in the syntactic digraph between the
+-- tail and the head of the arc or between the head and the tail.
+--
+-- Since for every arc there can be several edges present in the
+-- syntactic digraph, an option like |length| may have
+-- been given multiple times for the edges corresponding to the arc.
+--
+-- If your algorithm gets confused by multiple edges, try saying
+-- |a:options(your_option)|. This will always give the ``most
+-- sensible'' choice of the option if there are multiple edges
+-- corresponding to the same arc.
+--
+-- @param option A string option like |"length"|.
+--
+-- @return A table with the following contents:
+-- \begin{enumerate}
+-- \item It is an array of all values the option has for edges
+-- corresponding to |self| in the syntactic digraph. Suppose, for
+-- instance, you write the following:
+--\begin{codeexample}[code only]
+--graph {
+-- tail -- [length=1] head, % multi edge 1
+-- tail -- [length=3] head, % mulit edge 2
+-- head -- [length=8] tail, % multi edge 3
+-- tail -- head, % multi edge 4
+-- head -- [length=7] tail, % multi edge 5
+-- tail -- [length=2] head, % multi edge 6
+--}
+--\end{codeexample}
+-- Suppose, furthermore, that |length| has been setup as an edge
+-- option. Now suppose that |a| is the arc from the vertex |tail| to
+-- the vertex |head|. Calling |a:optionsArray('length')| will
+-- yield the array part |{1,3,2,8,7}|. The reason for the ordering is
+-- as follows: First come all values |length| had for syntactic edges
+-- going from |self.tail| to |self.head| in the order they appear in the graph
+-- description. Then come all values the options has for syntactic
+-- edges going from |self.head| to |self.tail|. The reason for this
+-- slightly strange behaviour is that many algorithms do not really
+-- care whether someone writes |a --[length=1] b| or
+-- |b --[length=1] a|; in both cases they would ``just'' like to know
+-- that the length is~|1|.
+--
+-- \item There is field called |aligned|, which is an array storing
+-- the actual syntactic edge objects whose values can be found in the
+-- array part of the returned table. However, |aligned| contains only
+-- the syntactic edges pointing ``in the same direction'' as the arc,
+-- that is, the tail and head of the syntactic edge are the same as
+-- those of the arc. In the above example, this array would contain
+-- the edges with the comment numbers |1|, |2|, and |6|.
+--
+-- Using the length of this array and the fact that the ``aligned''
+-- values come first in the table, you can easily iterate over the
+-- |option|'s values of only those edges that are aligned with the arc:
+--
+--\begin{codeexample}[code only, tikz syntax=false]
+--local a = g:arc(tail.head) -- some arc
+--local opt = a:optionsArray('length')
+--local sum = 0
+--for i=1,#opt.aligned do
+-- sum = sum + opt[i]
+--end
+--\end{codeexample}
+--
+--\item There is a field called |anti_aligned|, which is an array
+-- containing exactly the edges in the array part of the table not
+-- aligned with the arc. The numbering start at |1| as usual, so the
+-- $i$th entry of this table corresponds to the entry at position $i +
+-- \verb!#opt.aligned!$ of the table.
+--
+--\end{enumerate}
+--
+function Arc:optionsArray(option)
+
+ local cache = self.option_cache
+ local t = cache[option]
+ if t then
+ return t
+ end
+
+ -- Accumulate the edges for which the option is set:
+ local tail = self.tail
+ local head = self.head
+ local s_graph = self.syntactic_digraph
+
+ local arc = s_graph:arc(tail, head)
+ local aligned = {}
+ if arc then
+ for _,m in ipairs(arc.syntactic_edges) do
+ if m.options[option] ~= nil then
+ aligned[#aligned + 1] = m
+ end
+ end
+ table.sort(aligned, function (a,b) return a.event.index < b.event.index end)
+ end
+
+ local arc = head ~= tail and s_graph:arc(head, tail)
+ local anti_aligned = {}
+ if arc then
+ for _,m in ipairs(arc.syntactic_edges) do
+ if m.options[option] ~= nil then
+ anti_aligned[#anti_aligned + 1] = m
+ end
+ end
+ table.sort(anti_aligned, function (a,b) return a.event.index < b.event.index end)
+ end
+
+ -- Now merge them together
+ local t = { aligned = aligned, anti_aligned = anti_aligned }
+ for i=1,#aligned do
+ t[i] = aligned[i].options[option]
+ end
+ for i=1,#anti_aligned do
+ t[#t+1] = anti_aligned[i].options[option]
+ end
+ cache[option] = t
+
+ return t
+end
+
+
+
+---
+-- Returns the first option, that is, the first entry of
+-- |Arc:optionsArray(option)|. However, if the |only_aligned|
+-- parameter is set to true and there is no option with any aligned
+-- synactic edge, |nil| is returned.
+--
+-- @param option An option
+-- @param only_aligned If true, only aligned syntactic edges will be
+-- considered.
+-- @return The first entry of the |optionsArray|
+function Arc:options(option, only_aligned)
+ if only_aligned then
+ local opt = self:optionsArray(option)
+ if #opt.aligned > 0 then
+ return opt[1]
+ end
+ else
+ return self:optionsArray(option)[1]
+ end
+end
+
+
+
+
+---
+-- Get an accumulated value of an option of the syntactic edges
+-- corresponding to an arc.
+--
+-- @param option The option of interest
+-- @param accumulator A function taking two values. When there are
+-- more than one syntactic edges corresponding to |self| for which the
+-- |option| is set, this function will be called repeatedly for the
+-- different values. The first time it will be called for the first
+-- two values. Next, it will be called for the result of this call and
+-- the third value, and so on.
+-- @param only_aligned A boolean. If true, only the aligned syntactic
+-- edges will be considered.
+--
+-- @return If the option is not set for any (aligned) syntactic edges
+-- corresponding to |self|, |nil| is returned. If there is exectly one
+-- edge, the value of this edge is returned. Otherwise, the result of
+-- repeatedly applying the |accumulator| function as described
+-- above.
+--
+-- The result is cached, repeated calls will not invoke the
+-- |accumulator| function again.
+--
+-- @usage Here is typical usage:
+--\begin{codeexample}[code only, tikz syntax=false]
+--local total_length = a:optionsAccumulated('length', function (a,b) return a+b end) or 0
+--\end{codeexample}
+--
+function Arc:optionsAccumulated(option, accumulator, only_aligned)
+ local opt = self:options(option)
+ if only_aligned then
+ local aligned = opt.aligned
+ local v = aligned[accumulator]
+ if v == nil then
+ v = opt[1]
+ for i=2,#aligned do
+ v = accumulator(v, opt[i])
+ end
+ align[accumulator] = v
+ end
+ return v
+ else
+ local v = opt[accumulator]
+ if v == nil then
+ v = opt[1]
+ for i=2,#opt do
+ v = accumulator(v, opt[i])
+ end
+ opt[accumulator] = v
+ end
+ return v
+ end
+end
+
+
+
+---
+-- Compute the syntactic head and tail of an arc. For this, we have a
+-- look at the syntactic digraph underlying the arc. If there is at
+-- least once syntactic edge going from the arc's tail to the arc's
+-- head, the arc's tail and head are returned. Otherweise, we test
+-- whether there is a syntactic edge in the other direction and, if
+-- so, return head and tail in reverse order. Finally, if there is no
+-- syntactic edge at all corresponding to the arc in either direction,
+-- |nil| is returned.
+--
+-- @return The syntactic tail
+-- @return The syntactic head
+
+function Arc:syntacticTailAndHead ()
+ local s_graph = self.syntactic_digraph
+ local tail = self.tail
+ local head = self.head
+ if s_graph:arc(tail, head) then
+ return tail, head
+ elseif s_graph:arc(head, tail) then
+ return head, tail
+ end
+end
+
+
+---
+-- Compute the point cloud.
+--
+-- @return This method will return the ``point cloud'' of an arc,
+-- which is an array of all points that must be rotated and shifted
+-- along with the endpoints of an edge.
+--
+function Arc:pointCloud ()
+ if self.cached_point_cloud then
+ return self.cached_point_cloud -- cached
+ end
+ local cloud = {}
+ local a = self.syntactic_digraph:arc(self.tail,self.head)
+ if a then
+ for _,e in ipairs(a.syntactic_edges) do
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ cloud[#cloud + 1] = p
+ end
+ end
+ end
+ end
+ self.cached_point_cloud = cloud
+ return cloud
+end
+
+
+
+---
+-- Compute an event index for the arc.
+--
+-- @return The lowest event index of any edge involved
+-- in the arc (or nil, if there is no syntactic edge).
+--
+function Arc:eventIndex ()
+ if self.cached_event_index then
+ return self.cached_event_index
+ end
+ local head = self.head
+ local tail = self.tail
+ local e = math.huge
+ local a = self.syntactic_digraph:arc(tail,head)
+ if a then
+ for _,m in ipairs(a.syntactic_edges) do
+ e = math.min(e, m.event.index)
+ end
+ end
+ local a = head ~= tail and self.syntactic_digraph:arc(head,tail)
+ if a then
+ for _,m in ipairs(a.syntactic_edges) do
+ e = math.min(e, m.event.index)
+ end
+ end
+ self.cached_event_index = e
+ return e
+end
+
+
+
+
+---
+-- The span collector
+--
+-- This method returns the top (that is, smallest) priority of any
+-- edge involved in the arc.
+--
+-- The priority of an edge is computed as follows:
+--
+-- \begin{enumerate}
+-- \item If the option |"span priority"| is set, this number
+-- will be used.
+--
+-- \item If the edge has the same head as the arc, we lookup the key\\
+-- |"span priority " .. edge.direction|. If set, we use
+-- this value.
+--
+-- \item If the edge has a different head from the arc (the arc is
+-- ``reversed'' with respect to the syntactic edge), we lookup the key
+-- |"span priority reversed " .. edge.direction|. If set,
+-- we use this value.
+--
+-- \item Otherwise, we use priority 5.
+-- \end{enumerate}
+--
+-- @return The priority of the arc, as described above.
+--
+function Arc:spanPriority()
+ if self.cached_span_priority then
+ return self.cached_span_priority
+ end
+
+ local head = self.head
+ local tail = self.tail
+ local min
+ local g = self.syntactic_digraph
+
+ local a = g:arc(tail,head)
+ if a then
+ for _,m in ipairs(a.syntactic_edges) do
+ local p =
+ m.options["span priority"] or
+ lib.lookup_option("span priority " .. m.direction, m, g)
+
+ min = math.min(p or 5, min or math.huge)
+ end
+ end
+
+ local a = head ~= tail and g:arc(head,tail)
+ if a then
+ for _,m in ipairs(a.syntactic_edges) do
+ local p =
+ m.options["span priority"] or
+ lib.lookup_option("span priority reversed " .. m.direction, m, g)
+
+ min = math.min(p or 5, min or math.huge)
+ end
+ end
+
+ self.cached_span_priority = min or 5
+
+ return min or 5
+end
+
+
+
+
+
+
+---
+-- Sync an |Arc| with its syntactic edges. This causes the following:
+-- If the |path| field of the arc is |nil|, nothing
+-- happens. Otherwise, a copy of the |path| is created. However, for
+-- every path element that is a function, this function is invoked
+-- with the syntactic edge as its parameter. The result of this call
+-- should now be a |Coordinate|, which will replace the function in
+-- the |Path|.
+--
+-- You use this method like this:
+--\begin{codeexample}[code only, tikz syntax=false]
+--...
+--local arc = g:connect(s,t)
+--arc:setPolylinePath { Coordinate.new(x,y), Coordinate.new(x1,y1) }
+--...
+--arc:sync()
+--\end{codeexample}
+--
+-- Note that this function will automatically be called for all arcs
+-- of the |ugraph|, the |digraph|, and the |spanning_tree| of an
+-- algorithm by the rendering pipeline.
+--
+function Arc:sync()
+ if self.path then
+ local path = self.path
+ local head = self.head
+ local tail = self.tail
+ local a = self.syntactic_digraph:arc(tail,head)
+ if a and #a.syntactic_edges>0 then
+ for _,e in ipairs(a.syntactic_edges) do
+ local clone = path:clone()
+ for i=1,#clone do
+ local p = clone[i]
+ if type(p) == "function" then
+ clone[i] = p(e)
+ if type(clone[i]) == "table" then
+ clone[i] = clone[i]:clone()
+ end
+ end
+ end
+ e.path = clone
+ end
+ end
+ local a = head ~= tail and self.syntactic_digraph:arc(head,tail)
+ if a and #a.syntactic_edges>0 then
+ for _,e in ipairs(a.syntactic_edges) do
+ local clone = path:reversed()
+ for i=1,#clone do
+ local p = clone[i]
+ if type(p) == "function" then
+ clone[i] = p(e)
+ if type(clone[i]) == "table" then
+ clone[i] = clone[i]:clone()
+ end
+ end
+ end
+ e.path = clone
+ end
+ end
+ end
+end
+
+
+---
+-- This method returns a ``coordinate factory'' that can be used as
+-- the coordinate of a |moveto| at the beginning of a path starting at
+-- the |tail| of the arc. Suppose you want to create a path starting
+-- at the tail vertex, going to the coordinate $(10,10)$ and ending at
+-- the head vertex. The trouble is that when you create the path
+-- corresponding to this route, you typically do not know where the
+-- tail vertex is going to be. Even if that \emph{has} already been
+-- settled, you will still have the problem that different edges
+-- underlying the arc may wish to start their paths at different
+-- anchors inside the tail vertex. In such cases, you use this
+-- method to get a function that will, later on, compute the correct
+-- position of the anchor as needed.
+--
+-- Here is the code you would use to create the abovementioned path:
+--
+--\begin{codeexample}[code only, tikz syntax=false]
+--local a = g:connect(tail,head)
+--...
+--arc.path = Path.new()
+--arc.path:appendMoveto(arc:tailAnchorForArcPath())
+--arc.path:appendLineto(10, 10)
+--arc.path:appendLineto(arc:headAnchorForArcPath())
+--\end{codeexample}
+--
+-- Normally, however, you will not write code as detailed as the above
+-- and you would just write instead of the last three lines:
+--
+--\begin{codeexample}[code only, tikz syntax=false]
+--arc:setPolylinePath { Coordinate.new (10, 10) }
+--\end{codeexample}
+
+function Arc:tailAnchorForArcPath()
+ return function (edge)
+ local a = edge.options['tail anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.tail:anchor(a) + self.tail.pos
+ end
+end
+
+---
+-- See |Arc:tailAnchorForArcPath|.
+
+function Arc:headAnchorForArcPath()
+ return function (edge)
+ local a = edge.options['head anchor']
+ if a == "" then
+ a = "center"
+ end
+ return self.head:anchor(a) + self.head.pos
+ end
+end
+
+
+
+---
+-- Setup the |path| field of an arc in such a way that it corresponds
+-- to a sequence of straight line segments starting at the tail's
+-- anchor and ending at the head's anchor.
+--
+-- @param coordinates An array of |Coordinates| through which the line
+-- will go through.
+
+function Arc:setPolylinePath(coordinates)
+ local p = Path.new ()
+
+ p:appendMoveto(self:tailAnchorForArcPath())
+
+ for _,c in ipairs(coordinates) do
+ p:appendLineto(c)
+ end
+
+ p:appendLineto(self:headAnchorForArcPath())
+
+ self.path = p
+end
+
+
+
+
+-- Returns a string representation of an arc. This is mainly for debugging
+--
+-- @return The Arc as string.
+--
+function Arc:__tostring()
+ return tostring(self.tail) .. "->" .. tostring(self.head)
+end
+
+
+-- Done
+
+return Arc