summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/Direct.lua
blob: 81728a1a444f6abec1ab9c0789241a34302bec47 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
-- 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$



--- Direct is a class that collects algorithms for computing new
-- versions of a graph where arcs point in certain directions.

local Direct = {}

-- Namespace
require("pgf.gd.lib").Direct = Direct

-- Imports
local Digraph = require "pgf.gd.model.Digraph"


--- Compute a digraph from a syntactic digraph.
--
-- This function takes a syntactic digraph and compute a new digraph
-- where all arrow point in the "semantic direction" of the syntactic
-- arrows. For instance, while "a <- b" will cause an arc from a to be
-- to be added to the syntactic digraph, calling this function will
-- return a digraph in which there is an arc from b to a rather than
-- the other way round. In detail, "a <- b" is translated as just
-- described, "a -> b" yields an arc from a to b as expected, "a <-> b"
-- and "a -- b" yield arcs in both directions and, finally, "a -!- b"
-- yields no arc at all.
--
-- @param syntactic_digraph A syntactic digraph, usually the "input"
-- graph as specified syntactically be the user.
--
-- @return A new "semantic" digraph object.

function Direct.digraphFromSyntacticDigraph(syntactic_digraph)
  local digraph = Digraph.new(syntactic_digraph) -- copy

  -- Now go over all arcs of the syntactic_digraph and turn them into
  -- arcs with the correct direction in the digraph:
  for _,a in ipairs(syntactic_digraph.arcs) do
    for _,m in ipairs(a.syntactic_edges) do
      local direction = m.direction
      if direction == "->" then
        digraph:connect(a.tail, a.head)
      elseif direction == "<-" then
        digraph:connect(a.head, a.tail)
      elseif direction == "--" or direction == "<->" then
        digraph:connect(a.tail, a.head)
        digraph:connect(a.head, a.tail)
      end
      -- Case -!-: No edges...
    end
  end

  return digraph
end


--- Turn an arbitrary graph into a directed graph
--
-- Takes a digraph as input and returns its underlying undirected
-- graph, coded as a digraph. This means that between any two vertices
-- if there is an arc in one direction, there is also one in the other.
--
-- @param digraph A directed graph
--
-- @return The underlying undirected graph of digraph.

function Direct.ugraphFromDigraph(digraph)
  local ugraph = Digraph.new(digraph)

  -- Now go over all arcs of the syntactic_digraph and turn them into
  -- arcs with the correct direction in the digraph:
  for _,a in ipairs(digraph.arcs) do
    ugraph:connect(a.head,a.tail)
    ugraph:connect(a.tail,a.head)
  end

  return ugraph
end




-- Done

return Direct