summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua197
1 files changed, 98 insertions, 99 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
index 99e79919b54..490b8b3191d 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
@@ -27,12 +27,12 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- and if there is a single snapshot in which two vertices are
-- connected by an edge they are connected in the supergraph.
--
--- Note that in \tikzname\ a \emph{node} is more than a single dot. A node
+-- Note that in TikZ a \emph{node} is more than a single dot. A node
-- has a content and different properties like background-color or a
--- shape. Formally this can be modeled by function mapping vertices
+-- shape. Formally this can be modelled by function mapping vertices
-- to their properties. For evolving graphs this could be done in the
--- same way. As this is difficult to be realized in PGF because there
--- is no basic support for time dependent properties on nodes, each
+-- same way. As this is difficult to be realised in PGF because there
+-- is no basic support for time dependend properties on nodes, each
-- vertex will be displayed over time by different single
-- (snapshot-)nodes which can have different visual properties. This
-- means for a vertex which we call |supervertex| in the following we
@@ -53,7 +53,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- @field supervertices_by_id This storage maps a node identifier to the
-- related supervertex such that PGF-nodes which belonging to
-- the same superverticex can be identified
---
+--
-- @field snapshots An array of all snapshots. Sorted in ascending order
-- over the timestamps of the snapshots.
--
@@ -64,7 +64,6 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- Assume we want to iterate over all snapshots
-- for a certain pair of supernodes in which they are connected
-- by an arc. The arc_snapshots storage helps in this case:
--- %
-- \begin{codeexample}[code only, tikz syntax=false]
-- local supergraph = Supergraph.generateSupergraph(self.digraph)
-- local u = supergraph.vertices[1]
@@ -111,24 +110,24 @@ local get_snapshot
--
-- @param snapshots An array of all existing snapshots
-- @param timestamps A table which maps known timestamps to their
--- related snapshots
+-- related snapshots
-- @param ugraph The ugraph of the underlying graph structure
-- @param snapshot_time
--
-- @return The snapshot instance found in the snapshots array for the
--- wanted timestamp snapshot_time if it doesn't exists a new snapshot
--- will be generated and added to the arrays
+-- wanted timestamp snapshot_time if it does'nt exists a new snapshot
+-- will be generated and added to the arrays
--
function get_snapshot(snapshots, timestamps, ugraph, snapshot_time)
local snapshot
local snapshot_idx = timestamps[snapshot_time]
-
+
if not snapshot_idx then
-- store snapshot if it doesn't exists
- snapshot_idx = timestamps.n + 1
+ snapshot_idx = timestamps.n + 1
timestamps[snapshot_time] = snapshot_idx
timestamps.n = timestamps.n + 1
- snapshot = Digraph.new {
+ snapshot = Digraph.new {
syntactic_digraph = ugraph.syntactic_digraph,
options = ugraph.options
}
@@ -137,7 +136,7 @@ function get_snapshot(snapshots, timestamps, ugraph, snapshot_time)
else
snapshot = snapshots[snapshot_idx]
end
- assert(snapshot~=nil, "an unexpected error occurred")
+ assert(snapshot~=nil, "an unexpected error occured")
return snapshot
end
@@ -153,7 +152,7 @@ end
--
-- @return The supergraph which is a |Digraph| that has a supervertex
-- for each set of snapshot-vertices with the same |supernode|
--- attribute.
+-- attribute.
--
function Supergraph.generateSupergraph(digraph)
local new_supergraph
@@ -162,35 +161,35 @@ function Supergraph.generateSupergraph(digraph)
options = digraph.options,
digraph = digraph,
}
-
- -- array to store the supervertices for a given vertex name
+
+ -- array to store the supervertices for a given vertex name
local local_snapshots = {} -- array to store each snapshot graphs
-
+
local timestamps = { n = 0 } -- set of snapshot times
- -- separate and assign vertices to their snapshots and supervertices
+ -- separate and assign vertices to their snapshots and supervertives
for i,vertex in ipairs(digraph.vertices) do
local snapshot_time = assert(vertex.options["snapshot"], "Missing option 'snapshot' for vertex ".. vertex.name ..". ")
local supernode_name = assert(vertex.options["supernode"], "Missing option 'supernode' for vertex"..vertex.name..". ")
-
+
local snapshot = get_snapshot(local_snapshots, timestamps, digraph, snapshot_time)
local supervertex = new_supergraph.supervertices_by_id[supernode_name]
-
+
if not supervertex then
- -- first appearance of the supernode id
- supervertex = Vertex.new {
- kind = "super",
- name = supernode_name
+ -- first appeareance of the supernode id
+ supervertex = Vertex.new {
+ kind = "super",
+ name = supernode_name
}
supervertex.snapshots = {}
supervertex.subvertex = {}
- new_supergraph.supervertices_by_id[supernode_name] = supervertex
+ new_supergraph.supervertices_by_id[supernode_name] = supervertex
new_supergraph:add{supervertex}
supervertex.options = {}
supervertex.options = vertex.options
- end
-
+ end
+
snapshot:add{vertex}
new_supergraph.supervertices[vertex] = supervertex
@@ -199,11 +198,11 @@ function Supergraph.generateSupergraph(digraph)
end
-- Create edges
- for i, e in ipairs(digraph.arcs) do
+ for i, e in ipairs(digraph.arcs) do
local u,v = e.tail, e.head
local snapshot_tail = new_supergraph.vertex_snapshots[e.tail]
local snapshot_head = new_supergraph.vertex_snapshots[e.head]
-
+
assert(snapshot_head == snapshot_tail, "Arcs must connect nodes that exist at the same time.")
-- connect in the snapshot graph
@@ -212,18 +211,18 @@ function Supergraph.generateSupergraph(digraph)
-- connect in the supergraph:
local super_tail = new_supergraph.supervertices[u]
local super_head = new_supergraph.supervertices[v]
-
+
new_supergraph:assignToSuperarc(super_tail, super_head, snapshot_tail)
end
-
+
-- snapshots in temporal order
- table.sort(local_snapshots,
+ table.sort(local_snapshots,
function(s1,s2)
return s1.timestamp < s2.timestamp
end )
-
- local previous_snapshot
-
+
+ local previous_snapshot
+
for i,s in ipairs(local_snapshots) do
local start = -math.huge
if previous_snapshot then
@@ -236,18 +235,18 @@ function Supergraph.generateSupergraph(digraph)
new_supergraph.snapshots = local_snapshots
new_supergraph.snapshots_indices = Storage.new()
-
+
for i, s in ipairs(new_supergraph.snapshots) do
new_supergraph.snapshots_indices[s] = i
end
-
+
return new_supergraph
end
function Supergraph:getSnapshotStaticDuration(snapshot)
assert(snapshot, "a snapshot as parameter expected, but got nil")
- local idur = snapshot.interval.to - snapshot.interval.from
+ local idur = snapshot.interval.to - snapshot.interval.from
assert(idur, "unexpected nil-value")
local d1 = snapshot.interval.to - snapshot.timestamp
local d2 = snapshot.timestamp - snapshot.interval.from
@@ -273,9 +272,9 @@ function Supergraph:getDuration()
end
---
---
+--
-- @return The ratio of the time of a snapshot related to the global duration of the whole
--- evolving trees. (The time between the last and first snapshot)
+-- evlolving trees. (The time between the last and first snapshot)
function Supergraph:getSnapshotRelativeDuration(snapshot)
if self:getDuration() == 0 then
return 1
@@ -295,7 +294,7 @@ end
function Supergraph:getSupervertex(vertex)
assert(vertex, "vertex required")
assert(self.supervertices, "supervertex table is not defined")
- return self.supervertices[vertex]
+ return self.supervertices[vertex]
end
function Supergraph:getSuperarc(arc)
@@ -323,7 +322,7 @@ end
---
-- For a given supervertex get the related vertex for a snapshot
--
--- @param supervertex
+-- @param supervertex
--
-- @param snapshot
--
@@ -341,7 +340,7 @@ function Supergraph:consecutiveSnapshots(snapshot1, snapshot2, n)
local idx1 = self.snapshots_indices[snapshot1] --or -1
local idx2 = self.snapshots_indices[snapshot2] --or -1
local d = n or 1
-
+
return (idx2-idx1 <= d) or (idx1-idx2 <= d)
end
@@ -359,21 +358,21 @@ end
-- their positions from the supergraph.
--
function Supergraph:sharePositions(ugraph, ignore)
-
+
for _,vertex in ipairs(ugraph.vertices) do
if not ignore then
vertex.pos.x = self.supervertices[vertex].pos.x
vertex.pos.y = self.supervertices[vertex].pos.y
else
if not ignore.x then
- vertex.pos.x = self.supervertices[vertex].pos.x
+ vertex.pos.x = self.supervertices[vertex].pos.x
end
if not ignore.y then
- vertex.pos.y = self.supervertices[vertex].pos.y
+ vertex.pos.y = self.supervertices[vertex].pos.y
end
end
-
-
+
+
end
end
@@ -381,7 +380,7 @@ function Supergraph:onAllSnapshotvertices(f, ugraph)
for _,vertex in ipairs(ugraph.vertices) do
local snapshot_vertex = self.supertvertices[vertex]
if snapshot_vertex then
- f(vertex, snapshot_vertex)
+ f(vertex, snapshot_vertex)
end
end
end
@@ -395,23 +394,23 @@ end
-- the original vertex.
-- If a supervertex has no subvertices then it will not be added to the graph.
--
--- @param supervertex The supervertex which should be split.
+-- @param supervertex The supervertex which should be splitted.
--
-- @param snapshots An array of snapshots at which the supervertex
--- should be split into a new one with the corresponding pgf-vertices.
+-- should be splitted into a new one with the corresponding pgf-vertices.
-- If there are more than one snapshots passed to the function
-- for each snapshot there will be a new pseudo-vertex
--
function Supergraph:splitSupervertex(supervertex, snapshots)
assert(supervertex, "no supervertex defined")
-- snapshots in temporal order
- table.sort(snapshots,
+ table.sort(snapshots,
function(s1,s2)
return s1.timestamp < s2.timestamp
end )
assert(#snapshots~=0)
-
+
local edit_snapshots = supervertex.snapshots
local first_removed = math.huge
local rem_arcs = {}
@@ -438,42 +437,42 @@ function Supergraph:splitSupervertex(supervertex, snapshots)
local s = self.snapshots[j]
local vertex = self:getSnapshotVertex(supervertex, s)
if vertex then
- self.supervertices[vertex] = pseudovertex
- self:addSnapshotVertex(pseudovertex, s, vertex)
- self:removeSnapshotVertex(supervertex, s)
-
- if not has_subvertices then
- has_subvertices = true
- self:add{pseudovertex}
- end
-
- -- update edges:
- local incoming = self.digraph:incoming(vertex)
- local outgoing = self.digraph:outgoing(vertex)
-
- for _, arc in ipairs(incoming) do
- local tail = self.supervertices[arc.tail]
- local head = self.supervertices[arc.head]
- self:assignToSuperarc(tail, pseudovertex, s)
-
- local super_arc = self:arc(tail, supervertex)
- if not rem_arcs[super_arc] then
- table.insert(rem_arcs, {arc = super_arc, snapshot = s})
- rem_arcs[super_arc] = true
- end
- end
-
- for _, arc in ipairs(outgoing) do
- local tail = self.supervertices[arc.tail]
- local head = self.supervertices[arc.head]
- self:assignToSuperarc(pseudovertex, head, s)
-
- local super_arc = self:arc(supervertex, head)
- if not rem_arcs[super_arc] then
- table.insert(rem_arcs, {arc = super_arc, snapshot = s})
- rem_arcs[super_arc] = true
- end
- end
+ self.supervertices[vertex] = pseudovertex
+ self:addSnapshotVertex(pseudovertex, s, vertex)
+ self:removeSnapshotVertex(supervertex, s)
+
+ if not has_subvertices then
+ has_subvertices = true
+ self:add{pseudovertex}
+ end
+
+ -- update edges:
+ local incoming = self.digraph:incoming(vertex)
+ local outgoing = self.digraph:outgoing(vertex)
+
+ for _, arc in ipairs(incoming) do
+ local tail = self.supervertices[arc.tail]
+ local head = self.supervertices[arc.head]
+ self:assignToSuperarc(tail, pseudovertex, s)
+
+ local super_arc = self:arc(tail, supervertex)
+ if not rem_arcs[super_arc] then
+ table.insert(rem_arcs, {arc = super_arc, snapshot = s})
+ rem_arcs[super_arc] = true
+ end
+ end
+
+ for _, arc in ipairs(outgoing) do
+ local tail = self.supervertices[arc.tail]
+ local head = self.supervertices[arc.head]
+ self:assignToSuperarc(pseudovertex, head, s)
+
+ local super_arc = self:arc(supervertex, head)
+ if not rem_arcs[super_arc] then
+ table.insert(rem_arcs, {arc = super_arc, snapshot = s})
+ rem_arcs[super_arc] = true
+ end
+ end
end
end
end
@@ -482,14 +481,14 @@ function Supergraph:splitSupervertex(supervertex, snapshots)
for _, removed_arc in ipairs(rem_arcs) do
local snapshots = self.arc_snapshots[removed_arc.arc]
for i=#snapshots,1,-1 do
- local s = snapshots[i]
- if s.timestamp >= removed_arc.snapshot.timestamp then
- table.remove(snapshots, i)
- end
+ local s = snapshots[i]
+ if s.timestamp >= removed_arc.snapshot.timestamp then
+ table.remove(snapshots, i)
+ end
end
if #snapshots==0 then
- self:disconnect(removed_arc.arc.tail, removed_arc.arc.head)
+ self:disconnect(removed_arc.arc.tail, removed_arc.arc.head)
end
end
end
@@ -554,16 +553,16 @@ end
--
function Supergraph:assignToSuperarc(super_tail, super_head, snapshot)
assert(self:contains(super_tail) and self:contains(super_head),
- "tried to connect supernodes not in the supergraph")
-
+ "tried to connect supernodes not in the supergraph")
+
local super_arc = self:arc(super_tail, super_head)
if not super_arc then
- super_arc = self:connect(super_tail, super_head)
+ super_arc = self:connect(super_tail, super_head)
end
-
+
table.insert(self.arc_snapshots[super_arc], snapshot)
self.arc_snapshots[super_arc][snapshot] = true
-
+
return super_arc
end