-- 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