summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua98
1 files changed, 49 insertions, 49 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
index a4e51dfeff9..6cd46c60eb2 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/CoarseGraph.lua
@@ -12,7 +12,7 @@
--- A class for handling "coarse" versions of a graph. Such versions contain
--- less nodes and edges than the original graph while retaining the overall
+-- less nodes and edges than the original graph while retaining the overall
-- structure.
local Graph = require "pgf.gd.deprecated.Graph" -- we subclass from here
@@ -43,12 +43,12 @@ CoarseGraph.COARSEN_HYBRID = 2
--- Creates a new coarse graph derived from an existing graph.
--
--- Generates a coarse graph for the input |Graph|.
+-- Generates a coarse graph for the input |Graph|.
--
--- Coarsening describes the process of reducing the amount of nodes in a graph
--- by merging nodes into supernodes. There are different strategies, called
--- schemes, that can be applied, like merging nodes that belong to edges in a
--- maximal independent edge set or by creating supernodes based on a maximal
+-- Coarsening describes the process of reducing the amount of nodes in a graph
+-- by merging nodes into supernodes. There are different strategies, called
+-- schemes, that can be applied, like merging nodes that belong to edges in a
+-- maximal independent edge set or by creating supernodes based on a maximal
-- independent node set.
--
-- Coarsening is not performed automatically. The functions |CoarseGraph:coarsen|
@@ -57,28 +57,28 @@ CoarseGraph.COARSEN_HYBRID = 2
-- the coarser version of the graph).
--
-- Note, however, that the input \meta{graph} is always modified in-place, so
--- if the original version of \meta{graph} is needed in parallel to its
--- coarse representations, a deep copy of \meta{graph} needs to be passed over
+-- if the original version of \meta{graph} is needed in parallel to its
+-- coarse representations, a deep copy of \meta{grpah} needs to be passed over
-- to |CoarseGraph.new|.
--
-- @param graph An existing graph that needs to be coarsened.
-- @param scheme Coarsening scheme to use. Possible values are:\par
--- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|:
+-- |CoarseGraph.COARSEN_INDEPENDENT_EDGES|:
-- Coarsen the input graph by computing a maximal independent edge set
-- and collapsing edges from this set. The resulting coarse graph has
-- at least 50% of the nodes of the input graph. This coarsening scheme
--- gives slightly better results than
+-- gives slightly better results than
-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| because it is less aggressive.
-- However, this comes at higher computational cost.\par
-- |CoarseGraph.COARSEN_INDEPENDENT_NODES|:
-- Coarsen the input graph by computing a maximal independent node set,
-- making nodes from this set supernodes in the coarse graph, merging
--- adjacent nodes into the supernodes and connecting the supernodes
--- if their graph distance is no greater than three. This scheme gives
+-- adjacent nodes into the supernodes and connecting the supernodes
+-- if their grpah distance is no greater than three. This scheme gives
-- slightly worse results than |CoarseGraph.COARSEN_INDEPENDENT_EDGES|
-- but is computationally more efficient.\par
-- |CoarseGraph.COARSEN_HYBRID|: Combines the other schemes by starting
--- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to
+-- with |CoarseGraph.COARSEN_INDEPENDENT_EDGES| and switching to
-- |CoarseGraph.COARSEN_INDEPENDENT_NODES| as soon as the first scheme
-- does not reduce the amount of nodes by a factor of 25%.
--
@@ -114,14 +114,14 @@ end
local function pairs_by_sorted_keys (t, f)
- local a = {}
- for n in pairs(t) do a[#a + 1] = n end
- table.sort (a, f)
- local i = 0
- return function ()
- i = i + 1
- return a[i], t[a[i]]
- end
+ local a = {}
+ for n in pairs(t) do a[#a + 1] = n end
+ table.sort (a, f)
+ local i = 0
+ return function ()
+ i = i + 1
+ return a[i], t[a[i]]
+ end
end
@@ -153,33 +153,33 @@ function CoarseGraph:coarsen()
-- add the supernode to the graph
self.graph:addNode(supernode)
- -- collect all neighbors of the nodes to merge, create a node -> edge mapping
+ -- collact all neighbours of the nodes to merge, create a node -> edge mapping
local u_neighbours = lib.map(u.edges, function(edge) return edge, edge:getNeighbour(u) end)
local v_neighbours = lib.map(v.edges, function(edge) return edge, edge:getNeighbour(v) end)
- -- remove the two nodes themselves from the neighbor lists
+ -- remove the two nodes themselves from the neighbour lists
u_neighbours = lib.map(u_neighbours, function (edge,node) if node ~= v then return edge,node end end)
v_neighbours = lib.map(v_neighbours, function (edge,node) if node ~= u then return edge,node end end)
- -- compute a list of neighbors u and v have in common
+ -- compute a list of neighbours u and v have in common
local common_neighbours = lib.map(u_neighbours,
- function (edge,node)
- if v_neighbours[node] ~= nil then return edge,node end
- end)
+ function (edge,node)
+ if v_neighbours[node] ~= nil then return edge,node end
+ end)
- -- create a node -> edges mapping for common neighbors
+ -- create a node -> edges mapping for common neighbours
common_neighbours = lib.map(common_neighbours, function (edge, node)
return { edge, v_neighbours[node] }, node
end)
- -- drop common edges from the neighbor mappings
+ -- drop common edges from the neighbour mappings
u_neighbours = lib.map(u_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end)
v_neighbours = lib.map(v_neighbours, function (val,node) if not common_neighbours[node] then return val,node end end)
- -- merge neighbor lists
+ -- merge neighbour lists
local disjoint_neighbours = custom_merge(u_neighbours, v_neighbours)
- -- create edges between the supernode and the neighbors of the merged nodes
+ -- create edges between the supernode and the neighbours of the merged nodes
for neighbour, edge in pairs_by_sorted_keys(disjoint_neighbours, function (n,m) return n.index < m.index end) do
-- create a superedge to replace the existing one
@@ -190,11 +190,11 @@ function CoarseGraph:coarsen()
level = self.level,
}
- -- add the supernode and the neighbor to the edge
+ -- add the supernode and the neighbour to the edge
if u_neighbours[neighbour] then
superedge:addNode(neighbour)
superedge:addNode(supernode)
-
+
else
superedge:addNode(supernode)
superedge:addNode(neighbour)
@@ -206,14 +206,14 @@ function CoarseGraph:coarsen()
self.graph:deleteEdge(edge)
end
- -- do the same for all neighbors that the merged nodes have
+ -- do the same for all neighbours that the merged nodes have
-- in common, except that the weights of the new edges are the
- -- sums of the of the weights of the edges to the common neighbors
+ -- sums of the of the weights of the edges to the common neighbours
for neighbour, edges in pairs_by_sorted_keys(common_neighbours, function (n,m) return n.index < m.index end) do
local weights = 0
- for _,e in ipairs(edges) do
- weights = weights + edge.weight
- end
+ for _,e in ipairs(edges) do
+ weights = weights + edge.weight
+ end
local superedge = Edge.new{
direction = Edge.UNDIRECTED,
@@ -222,7 +222,7 @@ function CoarseGraph:coarsen()
level = self.level,
}
- -- add the supernode and the neighbor to the edge
+ -- add the supernode and the neighbour to the edge
superedge:addNode(supernode)
superedge:addNode(neighbour)
@@ -253,7 +253,7 @@ function CoarseGraph:revertSuperedge(superedge)
-- TODO we can probably skip adding edges that have one or more
-- subedges with the same level. But that needs more testing.
- -- TODO we might have to pass the corresponding supernode to
+ -- TODO we might have to pass the corresponding supernode to
-- this method so that we can move subnodes to the same
-- position, right? Interpolating seems to work fine without
-- though...
@@ -345,14 +345,14 @@ function CoarseGraph:interpolate()
self.graph:deleteNode(supernode)
end
end
-
+
-- Make sure that the nodes and edges are in the correct order:
table.sort (self.graph.nodes, function (a, b) return a.index < b.index end)
table.sort (self.graph.edges, function (a, b) return a.index < b.index end)
for _, n in pairs(self.graph.nodes) do
table.sort (n.edges, function (a, b) return a.index < b.index end)
end
-
+
-- update the level
self.level = self.level - 1
end
@@ -396,22 +396,22 @@ function CoarseGraph:findMaximalMatching()
-- mark the node as matched
matched_nodes[node] = true
- -- filter out edges adjacent to neighbors already matched
+ -- filter out edges adjacent to neighbours already matched
local edges = lib.imap(node.edges,
- function (edge)
- if not matched_nodes[edge:getNeighbour(node)] then return edge end
- end)
+ function (edge)
+ if not matched_nodes[edge:getNeighbour(node)] then return edge end
+ end)
-- FIXME TODO We use a light-vertex matching here. This is
-- different from the algorithm proposed by Hu which collapses
-- edges based on a heavy-edge matching...
if #edges > 0 then
- -- sort edges by the weights of the node's neighbors
+ -- sort edges by the weights of the node's neighbours
table.sort(edges, function (a, b)
return a:getNeighbour(node).weight < b:getNeighbour(node).weight
end)
- -- match the node against the neighbor with minimum weight
+ -- match the node against the neighbour with minimum weight
matched_nodes[edges[1]:getNeighbour(node)] = true
table.insert(matching, edges[1])
end
@@ -432,4 +432,4 @@ end
-- done
-return CoarseGraph
+return CoarseGraph \ No newline at end of file