summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua178
1 files changed, 86 insertions, 92 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
index 30b600e308d..5c48059a605 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/model/Digraph.lua
@@ -12,12 +12,12 @@
----
+---
-- Each |Digraph| instance models a \emph{directed, simple}
-- graph. ``Directed'' means that all edges ``point'' from a head node
-- to a tail node. ``Simple'' means that between any nodes there can be
-- (at most) one edge. Since these properties are a bit at odds with
--- the normal behavior of ``nodes'' and ``edges'' in \tikzname,
+-- the normal behaviour of ``nodes'' and ``edges'' in \tikzname,
-- different names are used for them inside the |model| namespace:
-- The class modeling ``edges'' is actually called |Arc| to stress
-- that an arc has a specific ``start'' (the tail) and a specific
@@ -31,17 +31,14 @@
-- Since digraphs are constantly created and modified inside the graph
-- drawing engine, some care was taken to ensure that all operations
-- work as quickly as possible. In particular:
--- %
-- \begin{itemize}
--- \item Adding an array of $k$ vertices using the |add| method needs
--- time $O(k)$.
--- \item Adding an arc between two vertices needs time $O(1)$.
--- \item Accessing both the |vertices| and the |arcs| fields takes time
--- $O(1)$, provided only the above operations are used.
+-- \item Adding an array of $k$ vertices using the |add| method needs
+-- time $O(k)$.
+-- \item Adding an arc between two vertices needs time $O(1)$.
+-- \item Accessing both the |vertices| and the |arcs| fields takes time
+-- $O(1)$, provided only the above operations are used.
-- \end{itemize}
--- %
-- Deleting vertices and arcs takes more time:
--- %
-- \begin{itemize}
-- \item Deleting the vertices given in an array of $k$ vertices from a
-- graph with $n$ vertices takes time $O(\max\{n,c\})$ where $c$ is the
@@ -53,12 +50,12 @@
-- number of outgoing arcs at the arc's tail and $h_i$ is the number
-- of incoming arcs at the arc's head. After a call to |disconnect|,
-- the next use of the |arcs| field will take time $O(|V| + |E|)$,
--- while subsequent accesses take time $O(1)$ -- till the
+-- while subsequent accesses take time $O(1)$ -- till the
-- next use of |disconnect|. This means that once you start deleting
-- arcs using |disconnect|, you should perform as many additional
-- |disconnect|s as possible before accessing |arcs| one more.
-- \end{itemize}
---
+--
-- \medskip
-- \noindent\emph{Stability.} The |vertices| field and the array
-- returned by |Digraph:incoming| and |Digraph:outgoing| are
@@ -66,7 +63,7 @@
-- when you use |ipairs| on the will be the ordering in which the
-- vertices or arcs were added to the graph. Even when you remove a
-- vertex or an arc, the ordering of the remaining elements stays the
--- same.
+-- same.
--
-- @field vertices This array contains the vertices that are part of
-- the digraph. Internally, this array
@@ -106,18 +103,15 @@
-- given vertex |v|, you cannot say something like |v.outgoings| or
-- perhaps |v:getOutgoings()|. Rather, you have to say |g:outgoing(v)|
-- to get this list:
--- %
--\begin{codeexample}[code only, tikz syntax=false]
---for _,a in ipairs(g:outgoing(v)) do -- g is a Digraph object.
+--for _,a in ipairs(g:outgoing(v)) do -- g is a Digraph object.
-- pgf.debug ("There is an arc leaving " .. tostring(v) ..
-- " heading to " .. tostring(a.head))
--end
--\end{codeexample}
--- %
--- Naturally, there is also a method |g:incoming()|.
---
--- To iterate over all arcs of a graph you can say:
--- %
+-- Naturally, there is also a method |g:incoming()|.
+--
+-- To iterate over all arcs of a graph you can say:
--\begin{codeexample}[code only, tikz syntax=false]
--for _,v in ipairs(g.vertices) do
-- for _,a in ipairs(g:outgoing(v)) do
@@ -128,7 +122,7 @@
--
-- However, it will often be more convenient and, in case the there
-- are far less arcs than vertices, also faster to write
---
+--
--\begin{codeexample}[code only, tikz syntax=false]
--for _,a in ipairs(g.arcs) do
-- ...
@@ -136,7 +130,7 @@
--\end{codeexample}
--
-- @field arcs For any two vertices |t| and |h| of a graph, there may
--- or may not be
+-- or may not be
-- an arc from |t| to |h|. If this is the case, there is an |Arc|
-- object that represents this arc. Note that, since |Digraph|s are
-- always simple graphs, there can be at most one such object for every
@@ -144,7 +138,7 @@
-- an |Arc| through a |Storage|, see the |Storage| class for
-- details. Each |Arc| for an edge of the syntactic digraph stores
-- an array called |syntactic_edges| of all the multiple edges that
--- are present in the user's input.
+-- are present in the user's input.
--
-- Unlike vertices, the arc objects of a graph are always local to a
-- graph; an |Arc| object can never be part of two digraphs at the same
@@ -170,7 +164,7 @@
-- point, the |arcs| array is reconstructed by adding all arcs of all
-- nodes to it.
--
--- The bottom line of the behavior of the |arcs| field is that (a) the
+-- The bottom line of the behaviour of the |arcs| field is that (a) the
-- ordering of the elements may change abruptly whenever you remove an
-- arc from a graph and (b) performing $k$ |disconnect| operations in
-- sequence takes time $O(k)$, provided you do not access the |arcs|
@@ -194,12 +188,12 @@ local function recalc_arcs (digraph)
end
end
digraph.arcs = arcs
- return arcs
+ return arcs
end
-Digraph.__index =
+Digraph.__index =
function (t, k)
- if k == "arcs" then
+ if k == "arcs" then
return recalc_arcs(t)
else
return rawget(Digraph,k)
@@ -229,7 +223,7 @@ local Vertex = require "pgf.gd.model.Vertex"
-- created graphs always have an empty arcs set. This means that
-- writing |Digraph.new(g)| where |g| is a graph creates a new graph
-- whose vertex set is the same as |g|'s, but where there are no edges:
--- %
+--
--\begin{codeexample}[code only, tikz syntax=false]
--local g = Digraph.new {}
--g:add { v1, v2, v3 }
@@ -245,8 +239,8 @@ local Vertex = require "pgf.gd.model.Vertex"
--local h = Digraph.new (g)
--for _,a in ipairs(g.arcs) do h:connect(a.tail, a.head) end
--\end{codeexample}
---
--- This operation takes time $O(1)$.
+--
+-- This operation takes time $O(1)$.
--
-- @param initial A table of initial values. It is permissible that
-- this array contains a |vertices| field. In this
@@ -274,7 +268,7 @@ function Digraph.new(initial)
digraph.vertices = {}
digraph.arcs = {}
- if vertices then
+ if vertices then
digraph:add(vertices)
end
return digraph
@@ -315,25 +309,25 @@ end
--
function Digraph:remove(array)
local vertices = self.vertices
-
+
-- Mark all to-be-deleted nodes
for i=1,#array do
local v = array[i]
assert(vertices[v], "to-be-deleted node is not in graph")
vertices[v] = false
end
-
+
-- Disconnect them
for i=1,#array do
self:disconnect(array[i])
end
-
+
LookupTable.remove(self.vertices, array)
end
---- Test, whether a graph contains a given vertex.
+--- Test, whether a graph contains a given vertex.
--
-- This operation takes time $O(1)$.
--
@@ -348,7 +342,7 @@ end
---
-- Returns the arc between two nodes, provided it exists. Otherwise,
--- |nil| is returned.
+-- |nil| is retured.
--
-- This operation takes time $O(1)$.
--
@@ -366,7 +360,7 @@ end
----
+---
-- Returns an array containing the outgoing arcs of a vertex. You may
-- only iterate over his array using ipairs, not using pairs.
--
@@ -421,7 +415,7 @@ function Digraph:orderOutgoing(v, vertices)
-- Compute ordering of the arcs
local reordered = {}
for _,arc in ipairs(outgoing) do
- reordered [lookup[arc.head]] = arc
+ reordered [lookup[arc.head]] = arc
end
-- Copy back
@@ -463,7 +457,7 @@ function Digraph:orderIncoming(v, vertices)
-- Compute ordering of the arcs
local reordered = {}
for _,arc in ipairs(incoming) do
- reordered [lookup[arc.head]] = arc
+ reordered [lookup[arc.head]] = arc
end
-- Copy back
@@ -476,9 +470,9 @@ end
----
+---
-- Connects two nodes by an arc and returns the newly created arc
--- object. If they are already connected, the existing arc is returned.
+-- object. If they are already connected, the existing arc is returned.
--
-- This operation takes time $O(1)$.
--
@@ -528,10 +522,10 @@ end
----
+---
-- Disconnect either a single vertex |v| from all its neighbors (remove all
-- incoming and outgoing arcs of this vertex) or, in case two nodes
--- are given as parameter, remove the arc between them, if it exists.
+-- are given as parameter, remove the arc between them, if it exsits.
--
-- This operation takes time $O(|I_v| + |I_t|)$, where $I_x$ is the set
-- of vertices incident to $x$, to remove the single arc between $v$ and
@@ -551,23 +545,23 @@ function Digraph:disconnect(v, t)
-- Remove:
s_outgoings[t] = nil
for i=1,#s_outgoings do
- if s_outgoings[i].head == t then
- table.remove (s_outgoings, i)
- break
- end
+ if s_outgoings[i].head == t then
+ table.remove (s_outgoings, i)
+ break
+ end
end
t_incomings[v] = nil
for i=1,#t_incomings do
- if t_incomings[i].tail == v then
- table.remove (t_incomings, i)
- break
- end
+ if t_incomings[i].tail == v then
+ table.remove (t_incomings, i)
+ break
+ end
end
self.arcs = nil -- invalidate arcs field
end
else
-- Case 1: Remove all arcs incident to v:
-
+
-- Step 1: Delete all incomings arcs:
local incomings = assert(v.incomings[self], "node not in graph")
local vertices = self.vertices
@@ -575,15 +569,15 @@ function Digraph:disconnect(v, t)
for i=1,#incomings do
local s = incomings[i].tail
if s ~= v and vertices[s] then -- skip self-loop and to-be-deleted nodes
- -- Remove this arc from s:
- local s_outgoings = s.outgoings[self]
- s_outgoings[v] = nil
- for i=1,#s_outgoings do
- if s_outgoings[i].head == v then
- table.remove (s_outgoings, i)
- break
- end
- end
+ -- Remove this arc from s:
+ local s_outgoings = s.outgoings[self]
+ s_outgoings[v] = nil
+ for i=1,#s_outgoings do
+ if s_outgoings[i].head == v then
+ table.remove (s_outgoings, i)
+ break
+ end
+ end
end
end
@@ -592,14 +586,14 @@ function Digraph:disconnect(v, t)
for i=1,#outgoings do
local t = outgoings[i].head
if t ~= v and vertices[t] then
- local t_incomings = t.incomings[self]
- t_incomings[v] = nil
- for i=1,#t_incomings do
- if t_incomings[i].tail == v then
- table.remove (t_incomings, i)
- break
- end
- end
+ local t_incomings = t.incomings[self]
+ t_incomings[v] = nil
+ for i=1,#t_incomings do
+ if t_incomings[i].tail == v then
+ table.remove (t_incomings, i)
+ break
+ end
+ end
end
end
@@ -616,12 +610,12 @@ end
----
+---
-- An arc is changed so that instead of connecting |self.tail|
-- and |self.head|, it now connects a new |head| and |tail|. The
-- difference to first disconnecting and then reconnecting is that all
-- fields of the arc (other than |head| and |tail|, of course), will
--- be ``moved along''. Reconnecting an arc in the same way as before has no
+-- be ``moved along.'' Reconnecting an arc in the same way as before has no
-- effect.
--
-- If there is already an arc at the new position, fields of the
@@ -643,16 +637,16 @@ end
--
function Digraph:reconnect(arc, tail, head)
assert (arc and tail and head, "connect with nil parameters")
-
+
if arc.head == head and arc.tail == tail then
-- Nothing to be done
return arc
else
local new_arc = self:connect(tail, head)
-
+
for k,v in pairs(arc) do
if k ~= "head" and k ~= "tail" then
- new_arc[k] = v
+ new_arc[k] = v
end
end
@@ -688,11 +682,11 @@ end
-- A collapse vertex will store the collapsed vertices so that you can
-- call |expand| later on to ``restore'' the vertices and arcs that
-- were saved during a collapse. This storage is \emph{not} local to
--- the graph in which the collapse occurred.
+-- the graph in which the collapse occured.
--
-- @param collapse_vertices An array of to-be-collapsed vertices
-- @param collapse_vertex The vertex that represents the collapse. If
--- missing, a vertex will be created automatically and added to the graph.
+-- missing, a vertex will be created automatically and added to the graph.
-- @param vertex_fun This function is called for each to-be-collapsed
-- vertex. The parameters are the collapse vertex and the
-- to-be-collapsed vertex. May be |nil|.
@@ -700,7 +694,7 @@ end
-- between |rep| and some other vertex. The arguments are the new arc
-- and the original arc. May be |nil|.
--
--- @return The new vertex that represents the collapsed vertices.
+-- @return The new vertex that represents the collapsed vertices.
function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fun)
@@ -710,7 +704,7 @@ function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fu
collapse_vertex = Vertex.new {}
end
self:add {collapse_vertex}
-
+
-- Copy the collapse_vertices and create lookup
local cvs = {}
for i=1,#collapse_vertices do
@@ -722,29 +716,29 @@ function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fu
-- Connected collapse_vertex appropriately
local collapsed_arcs = {}
-
+
if not arc_fun then
arc_fun = function () end
end
-
+
for _,v in ipairs(cvs) do
if vertex_fun then
vertex_fun (collapse_vertex, v)
end
for _,a in ipairs(v.outgoings[self]) do
if cvs[a.head] ~= true then
- arc_fun (self:connect(collapse_vertex, a.head), a)
- collapsed_arcs[#collapsed_arcs + 1] = a
+ arc_fun (self:connect(collapse_vertex, a.head), a)
+ collapsed_arcs[#collapsed_arcs + 1] = a
end
end
for _,a in ipairs(v.incomings[self]) do
if cvs[a.tail] ~= true then
- arc_fun (self:connect(a.tail, collapse_vertex), a)
+ arc_fun (self:connect(a.tail, collapse_vertex), a)
end
collapsed_arcs[#collapsed_arcs + 1] = a
end
end
-
+
-- Remember the old vertices.
collapse_vertex.collapsed_vertices = cvs
collapse_vertex.collapsed_arcs = collapsed_arcs
@@ -776,7 +770,7 @@ function Digraph:expand(vertex, vertex_fun, arc_fun)
-- Add all vertices:
self:add(cvs)
- if vertex_fun then
+ if vertex_fun then
for _,v in ipairs(cvs) do
vertex_fun(vertex, v)
end
@@ -785,13 +779,13 @@ function Digraph:expand(vertex, vertex_fun, arc_fun)
-- Add all arcs:
for _,arc in ipairs(vertex.collapsed_arcs) do
local new_arc = self:connect(arc.tail, arc.head)
-
+
for k,v in pairs(arc) do
if k ~= "head" and k ~= "tail" then
- new_arc[k] = v
+ new_arc[k] = v
end
end
-
+
if arc_fun then
arc_fun(new_arc, vertex)
end
@@ -815,7 +809,7 @@ end
----
+---
-- Computes a string representation of this graph including all nodes
-- and edges. The syntax of this representation is such that it can be
-- used directly in \tikzname's |graph| syntax.
@@ -831,13 +825,13 @@ function Digraph:__tostring()
if #out_arcs > 0 then
local t = {}
for j,a in ipairs(out_arcs) do
- t[j] = tostring(a.head)
+ t[j] = tostring(a.head)
end
astrings[#astrings + 1] = " " .. tostring(v) .. " -> { " .. table.concat(t,", ") .. " }"
end
end
return "graph [id=" .. tostring(self.vertices) .. "] {\n {\n" ..
- table.concat(vstrings, ",\n") .. "\n }; \n" ..
+ table.concat(vstrings, ",\n") .. "\n }; \n" ..
table.concat(astrings, ";\n") .. "\n}";
end
@@ -846,4 +840,4 @@ end
-- Done
-return Digraph
+return Digraph \ No newline at end of file