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