diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua | 849 |
1 files changed, 849 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua new file mode 100644 index 0000000000..30b600e308 --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/model/Digraph.lua @@ -0,0 +1,849 @@ +-- 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$ + + + + +--- +-- 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, +-- 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 +-- ``end'' (the head). The class modeling ``nodes'' is actually called +-- |Vertex|, just to stress that this is not a direct model of a +-- \tikzname\ |node|, but can represent a arbitrary vertex of a graph, +-- independently of whether it is an actual |node| in \tikzname. +-- +-- \medskip +-- \noindent\emph{Time Bounds.} +-- 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. +-- \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 +-- number of arcs between the to-be-deleted nodes and the remaining +-- nodes. Note that this time bound in independent of~$k$. In +-- particular, it will be much faster to delete many vertices by once +-- calling the |remove| function instead of calling it repeatedly. +-- \item Deleting an arc takes time $O(t_o+h_i)$ where $t_o$ is the +-- 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 +-- 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 +-- \emph{stable} in the following sense: The ordering of the elements +-- 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. +-- +-- @field vertices This array contains the vertices that are part of +-- the digraph. Internally, this array +-- is an object of type |LookupTable|, but you can mostly treat it as +-- if it were an array. In particular, you can iterate over its +-- elements using |ipairs|, but you may not modify the array; use the +-- |add| and |remove| methods, instead. +-- +-- \begin{codeexample}[code only, tikz syntax=false] +-- local g = Digraph.new {} +-- +-- g:add { v1, v2 } -- Add vertices v1 and v2 +-- g:remove { v2 } -- Get rid of v2. +-- +-- assert (g:contains(v1)) +-- assert (not g:contains(v2)) +-- \end{codeexample} +-- +-- It is important to note that although each digraph stores a +-- |vertices| array, the elements in this array are not exclusive to +-- the digraph: A vertex can be an element of any number of +-- digraphs. Whether or not a vertex is an element of digraph is not +-- stored in the vertex, only in the |vertices| array of the +-- digraph. To test whether a digraph contains a specific node, use the +-- |contains| method, which takes time $O(1)$ to perform the test (this +-- is because, as mentioned earlier, the |vertices| array is actually a +-- |LookupTable| and for each vertex |v| the field |vertices[v]| will +-- be true if, and only if, |v| is an element of the |vertices| array). +-- +-- Do not use |pairs(g.vertices)| because this may cause your graph +-- drawing algorithm to produce different outputs on different runs. +-- +-- A slightly annoying effect of vertices being able to belong to +-- several graphs at the same time is that the set of arcs incident to +-- a vertex is not a property of the vertex, but rather of the +-- graph. In other words, to get a list of all arcs whose tail is a +-- 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. +-- 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: +-- % +--\begin{codeexample}[code only, tikz syntax=false] +--for _,v in ipairs(g.vertices) do +-- for _,a in ipairs(g:outgoing(v)) do +-- ... +-- end +--end +--\end{codeexample} +-- +-- 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 +-- ... +--end +--\end{codeexample} +-- +-- @field arcs For any two vertices |t| and |h| of a graph, there may +-- 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 +-- pair of vertices. However, you can store any information you like for +-- 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. +-- +-- 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 +-- time. For this reason, while for vertices it makes sense to create +-- |Vertex| objects independently of any |Digraph| objects, it is not +-- possible to instantiate an |Arc| directly: only the |Digraph| method +-- |connect| is allowed to create new |Arc| objects and it will return +-- any existing arcs instead of creating new ones, if there is already +-- an arc present between two nodes. +-- +-- The |arcs| field of a digraph contains a |LookupTable| of all arc +-- objects present in the |Digraph|. Although you can access this field +-- normally and use it in |ipairs| to iterate over all arcs of a graph, +-- note that this array is actually ``reconstructed lazily'' whenever +-- an arc is deleted from the graph. What happens is the following: As +-- long as you just add arcs to a graph, the |arcs| array gets updated +-- normally. However, when you remove an arc from a graph, the arc does +-- not get removed from the |arcs| array (which would be an expensive +-- operation). Instead, the |arcs| array is invalidated (internally set +-- to |nil|), allowing us to perform a |disconnect| in time +-- $O(1)$. The |arcs| array is then ignored until the next time it is +-- accessed, for instance when a user says |ipairs(g.arcs)|. At this +-- 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 +-- 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| +-- field between calls. +-- +-- @field syntactic_digraph is a reference to the syntactic digraph +-- from which this graph stems ultimately. This may be a cyclic +-- reference to the graph itself. +-- @field options If present, it will be a table storing +-- the options set for the syntactic digraph. +-- +local Digraph = {} + +local function recalc_arcs (digraph) + local arcs = {} + local vertices = digraph.vertices + for i=1,#vertices do + local out = vertices[i].outgoings[digraph] + for j=1,#out do + arcs[#arcs + 1] = out[j] + end + end + digraph.arcs = arcs + return arcs +end + +Digraph.__index = + function (t, k) + if k == "arcs" then + return recalc_arcs(t) + else + return rawget(Digraph,k) + end + end + + + +-- Namespace +require("pgf.gd.model").Digraph = Digraph + +-- Imports +local Arc = require "pgf.gd.model.Arc" +local LookupTable = require "pgf.gd.lib.LookupTable" +local Vertex = require "pgf.gd.model.Vertex" + + + + + +--- +-- Graphs are created using the |new| method, which takes a table of +-- |initial| values as input (like most |new| methods in the graph +-- drawing system). It is permissible that this table of initial values +-- has a |vertices| field, in which case this array will be copied. In +-- contrast, an |arcs| field in the table will be ignored -- newly +-- 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 } +--g:connect (v1, v2) +-- +--local h = Digraph.new (g) +--assert (h:contains(v1)) +--assert (not h:arc(v1, v2)) +--\end{codeexample} +-- +-- To completely copy a graph, including all arcs, you have to write: +--\begin{codeexample}[code only, tikz syntax=false] +--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)$. +-- +-- @param initial A table of initial values. It is permissible that +-- this array contains a |vertices| field. In this +-- case, this field must be an array and its entries +-- must be nodes, which will be inserted. If initial +-- has an |arcs| field, this field will be ignored. +-- The table must contain a field |syntactic_digraph|, +-- which should normally be the syntactic digraph of +-- the graph, but may also be the string |"self"|, in +-- which case it will be set to the newly created +-- (syntactic) digraph. +-- @return A newly-allocated digraph. +-- +function Digraph.new(initial) + local digraph = {} + setmetatable(digraph, Digraph) + + if initial then + for k,v in pairs(initial or {}) do + digraph [k] = v + end + end + + local vertices = digraph.vertices + digraph.vertices = {} + digraph.arcs = {} + + if vertices then + digraph:add(vertices) + end + return digraph +end + + +--- Add vertices to a digraph. +-- +-- This operation takes time $O(|\verb!array!|)$. +-- +-- @param array An array of to-be-added vertices. +-- +function Digraph:add(array) + local vertices = self.vertices + for i=1,#array do + local v = array[i] + if not vertices[v] then + vertices[v] = true + vertices[#vertices + 1] = v + v.incomings[self] = {} + v.outgoings[self] = {} + end + end +end + + +--- Remove vertices from a digraph. +-- +-- This operation removes an array of vertices from a graph. The +-- operation takes time linear in the number of vertices, regardless of +-- how many vertices are to be removed. Thus, it will be (much) faster +-- to delete many vertices by first compiling them in an array and to +-- then delete them using one call to this method. +-- +-- This operation takes time $O(\max\{|\verb!array!|, |\verb!self.vertices!|\})$. +-- +-- @param array The to-be-removed vertices. +-- +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. +-- +-- This operation takes time $O(1)$. +-- +-- @param v The vertex to be tested. +-- +function Digraph:contains(v) + return v and self.vertices[v] == true +end + + + + +--- +-- Returns the arc between two nodes, provided it exists. Otherwise, +-- |nil| is returned. +-- +-- This operation takes time $O(1)$. +-- +-- @param tail The tail vertex +-- @param head The head vertex +-- +-- @return The arc object connecting them +-- +function Digraph:arc(tail, head) + local out = tail.outgoings[self] + if out then + return out[head] + end +end + + + +--- +-- Returns an array containing the outgoing arcs of a vertex. You may +-- only iterate over his array using ipairs, not using pairs. +-- +-- This operation takes time $O(1)$. +-- +-- @param v The vertex +-- +-- @return An array of all outgoing arcs of this vertex (all arcs +-- whose tail is the vertex) +-- +function Digraph:outgoing(v) + return assert(v.outgoings[self], "vertex not in graph") +end + + + +--- +-- Sorts the array of outgoing arcs of a vertex. This allows you to +-- later iterate over the outgoing arcs in a specific order. +-- +-- This operation takes time $O(|\verb!outgoing!| \log |\verb!outgoings!|)$. +-- +-- @param v The vertex +-- @param f A comparison function that is passed to |table.sort| +-- +function Digraph:sortOutgoing(v, f) + table.sort(assert(v.outgoings[self], "vertex not in graph"), f) +end + + +--- +-- Reorders the array of outgoing arcs of a vertex. The parameter array +-- \emph{must} contain the same set of vertices as the outgoing array, +-- but possibly in a different order. +-- +-- This operation takes time $O(|\verb!outgoing!|)$, where |outgoing| +-- is the array of |v|'s outgoing arcs in |self|. +-- +-- @param v The vertex +-- @param vertices An array containing the outgoing vertices in some order. +-- +function Digraph:orderOutgoing(v, vertices) + local outgoing = assert (v.outgoings[self], "vertex not in graph") + assert (#outgoing == #vertices) + + -- Create back hash + local lookup = {} + for i=1,#vertices do + lookup[vertices[i]] = i + end + + -- Compute ordering of the arcs + local reordered = {} + for _,arc in ipairs(outgoing) do + reordered [lookup[arc.head]] = arc + end + + -- Copy back + for i=1,#outgoing do + outgoing[i] = assert(reordered[i], "illegal vertex order") + end +end + + + +--- See |outgoing|. +-- +function Digraph:incoming(v) + return assert(v.incomings[self], "vertex not in graph") +end + + +--- +-- See |sortOutgoing|. +-- +function Digraph:sortIncoming(v, f) + table.sort(assert(v.incomings[self], "vertex not in graph"), f) +end + + +--- +-- See |orderOutgoing|. +-- +function Digraph:orderIncoming(v, vertices) + local incoming = assert (v.incomings[self], "vertex not in graph") + assert (#incoming == #vertices) + + -- Create back hash + local lookup = {} + for i=1,#vertices do + lookup[vertices[i]] = i + end + + -- Compute ordering of the arcs + local reordered = {} + for _,arc in ipairs(incoming) do + reordered [lookup[arc.head]] = arc + end + + -- Copy back + for i=1,#incoming do + incoming[i] = assert(reordered[i], "illegal vertex order") + end +end + + + + + +--- +-- Connects two nodes by an arc and returns the newly created arc +-- object. If they are already connected, the existing arc is returned. +-- +-- This operation takes time $O(1)$. +-- +-- @param s The tail vertex +-- @param t The head vertex (may be identical to |tail| in case of a +-- loop) +-- +-- @return The arc object connecting them (either newly created or +-- already existing) +-- +function Digraph:connect(s, t) + assert (s and t and self.vertices[s] and self.vertices[t], "trying connect nodes not in graph") + + local s_outgoings = s.outgoings[self] + local arc = s_outgoings[t] + + if not arc then + -- Ok, create and insert new arc object + arc = { + tail = s, + head = t, + option_cache = {}, + syntactic_digraph = self.syntactic_digraph, + syntactic_edges = {} + } + setmetatable(arc, Arc) + + -- Insert into outgoings: + s_outgoings [#s_outgoings + 1] = arc + s_outgoings [t] = arc + + local t_incomings = t.incomings[self] + -- Insert into incomings: + t_incomings [#t_incomings + 1] = arc + t_incomings [s] = arc + + -- Insert into arcs field, if it exists: + local arcs = rawget(self, "arcs") + if arcs then + arcs[#arcs + 1] = arc + end + end + + return arc +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. +-- +-- 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 +-- $v$. For a single vertex $v$, it takes time $O(\sum_{y: \text{there is some +-- arc between $v$ and $y$ or $y$ and $v$}} |I_y|)$. +-- +-- @param v The single vertex or the tail vertex +-- @param t The head vertex +-- +function Digraph:disconnect(v, t) + if t then + -- Case 2: Remove a single arc. + local s_outgoings = assert(v.outgoings[self], "tail node not in graph") + local t_incomings = assert(t.incomings[self], "head node not in graph") + + if s_outgoings[t] then + -- 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 + 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 + 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 + + 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 + end + end + + -- Step 2: Delete all outgoings arcs: + local outgoings = v.outgoings[self] + 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 + end + end + + if #incomings > 0 or #outgoings > 0 then + self.arcs = nil -- invalidate arcs field + end + + -- Step 3: Reset incomings and outgoings fields + v.incomings[self] = {} + v.outgoings[self] = {} + end +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 +-- effect. +-- +-- If there is already an arc at the new position, fields of the +-- to-be-reconnected arc overwrite fields of the original arc. This is +-- especially dangerous with a syntactic digraph, so do not reconnect +-- arcs of the syntactic digraph (which you should not do anyway). +-- +-- The |arc| object may no longer be valid after a reconnect, but the +-- operation returns the new arc object. +-- +-- This operation needs the time of a disconnect (if necessary). +-- +-- @param arc The original arc object +-- @param tail The new tail vertex +-- @param head The new head vertex +-- +-- @return The new arc object connecting them (either newly created or +-- already existing) +-- +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 + end + end + + -- Remove old arc: + self:disconnect(arc.tail, arc.head) + + return new_arc + end +end + + + +--- +-- Collapse a set of vertices into a single vertex +-- +-- Often, algorithms will wish to treat a whole set of vertices ``as a +-- single vertex''. The idea is that a new vertex is then inserted +-- into the graph, and this vertex is connected to all vertices to +-- which any of the original vertices used to be connected. +-- +-- The |collapse| method takes an array of to-be-collapsed vertices as +-- well as a vertex. First, it will store references to the +-- to-be-collapsed vertices inside the vertex. Second, we iterate over +-- all arcs of the to-be-collapsed vertices. If this arc connects a +-- to-be-collapsed vertex with a not-to-be-collapsed vertex, the +-- not-to-be-collapsed vertex is connected to the collapse +-- vertex. Additionally, the arc is stored at the vertex. +-- +-- Note that the collapse vertex will be added to the graph if it is +-- not already an element. The collapsed vertices will not be removed +-- from the graph, so you must remove them yourself, if necessary. +-- +-- 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. +-- +-- @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. +-- @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|. +-- @param arc_fun This function is called whenever a new arc is added +-- 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. + +function Digraph:collapse(collapse_vertices, collapse_vertex, vertex_fun, arc_fun) + + + -- Create and add node, if necessary. + if not collapse_vertex then + collapse_vertex = Vertex.new {} + end + self:add {collapse_vertex} + + -- Copy the collapse_vertices and create lookup + local cvs = {} + for i=1,#collapse_vertices do + local v = collapse_vertices[i] + cvs[i] = v + cvs[v] = true + end + assert (cvs[collapse_vertex] ~= true, "collapse_vertex is in collapse_vertices") + + -- 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 + 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) + end + collapsed_arcs[#collapsed_arcs + 1] = a + end + end + + -- Remember the old vertices. + collapse_vertex.collapsed_vertices = cvs + collapse_vertex.collapsed_arcs = collapsed_arcs + + return collapse_vertex +end + + + +--- +-- Expand a previously collapsed vertex. +-- +-- If you have collapsed a set of vertices in a graph using +-- |collapse|, you can expand this set once more using this method. It +-- will add all vertices that were previously removed from the graph +-- and will also reinstall the deleted arcs. The collapse vertex is +-- not removed. +-- +-- @param vertex A to-be-expanded vertex that was previously returned +-- by |collapse|. +-- @param vertex_fun A function that is called once for each +-- reinserted vertex. The parameters are the collapse vertex and the +-- reinstalled vertex. May be |nil|. +-- @param arc_fun A function that is called once for each +-- reinserted arc. The parameter is the arc and the |vertex|. May be |nil|. +-- +function Digraph:expand(vertex, vertex_fun, arc_fun) + local cvs = assert(vertex.collapsed_vertices, "no expand information stored") + + -- Add all vertices: + self:add(cvs) + if vertex_fun then + for _,v in ipairs(cvs) do + vertex_fun(vertex, v) + end + end + + -- 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 + end + end + + if arc_fun then + arc_fun(new_arc, vertex) + end + end +end + + + + + +--- +-- Invokes the |sync| method for all arcs of the graph. +-- +-- @see Arc:sync() +-- +function Digraph:sync() + for _,a in ipairs(self.arcs) do + a:sync() + end +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. +-- +-- @return |self| as string. +-- +function Digraph:__tostring() + local vstrings = {} + local astrings = {} + for i,v in ipairs(self.vertices) do + vstrings[i] = " " .. tostring(v) .. "[x=" .. math.floor(v.pos.x) .. "pt,y=" .. math.floor(v.pos.y) .. "pt]" + local out_arcs = v.outgoings[self] + if #out_arcs > 0 then + local t = {} + for j,a in ipairs(out_arcs) do + 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(astrings, ";\n") .. "\n}"; +end + + + + +-- Done + +return Digraph |