Provided by: tcllib_1.15-dfsg-2_all bug

NAME

       struct::graph::op - Operation for (un)directed graph objects

SYNOPSIS

       package require Tcl  8.4

       package require struct::graph::op  ?0.11.3?

       struct::graph::op::toAdjacencyMatrix g

       struct::graph::op::toAdjacencyList G ?options...?

       struct::graph::op::kruskal g

       struct::graph::op::prim g

       struct::graph::op::isBipartite? g ?bipartvar?

       struct::graph::op::tarjan g

       struct::graph::op::connectedComponents g

       struct::graph::op::connectedComponentOf g n

       struct::graph::op::isConnected? g

       struct::graph::op::isCutVertex? g n

       struct::graph::op::isBridge? g a

       struct::graph::op::isEulerian? g ?tourvar?

       struct::graph::op::isSemiEulerian? g ?pathvar?

       struct::graph::op::dijkstra g start ?options...?

       struct::graph::op::distance g origin destination ?options...?

       struct::graph::op::eccentricity g n ?options...?

       struct::graph::op::radius g ?options...?

       struct::graph::op::diameter g ?options...?

       struct::graph::op::BellmanFord G startnode

       struct::graph::op::Johnsons G ?options...?

       struct::graph::op::FloydWarshall G

       struct::graph::op::MetricTravellingSalesman G

       struct::graph::op::Christofides G

       struct::graph::op::GreedyMaxMatching G

       struct::graph::op::MaxCut G U V

       struct::graph::op::UnweightedKCenter G k

       struct::graph::op::WeightedKCenter G nodeWeights W

       struct::graph::op::GreedyMaxIndependentSet G

       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights

       struct::graph::op::VerticesCover G

       struct::graph::op::EdmondsKarp G s t

       struct::graph::op::BusackerGowen G desiredFlow s t

       struct::graph::op::ShortestsPathsByBFS G s outputFormat

       struct::graph::op::BFS G s ?outputFormat...?

       struct::graph::op::MinimumDiameterSpanningTree G

       struct::graph::op::MinimumDegreeSpanningTree G

       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg

       struct::graph::op::BlockingFlowByDinic G s t

       struct::graph::op::BlockingFlowByMKM G s t

       struct::graph::op::createResidualGraph G f

       struct::graph::op::createAugmentingNetwork G f path

       struct::graph::op::createLevelGraph Gf s

       struct::graph::op::TSPLocalSearching G C

       struct::graph::op::TSPLocalSearching3Approx G C

       struct::graph::op::createSquaredGraph G

       struct::graph::op::createCompleteGraph G originalEdges

_________________________________________________________________

DESCRIPTION

       The  package  described by this document, struct::graph::op, is a companion to the package
       struct::graph. It provides a series of common  operations  and  algorithms  applicable  to
       (un)directed graphs.

       Despite  being a companion the package is not directly dependent on struct::graph, only on
       the API defined by that package. I.e. the operations of this package can be applied to any
       and  all  graph  objects  which  provide  the  same  API  as  the  objects created through
       struct::graph.

OPERATIONS

       struct::graph::op::toAdjacencyMatrix g
              This command takes the graph g and returns a nested list containing  the  adjacency
              matrix of g.

              The  elements  of the outer list are the rows of the matrix, the inner elements are
              the column values in each row. The matrix has "n+1"  rows  and  columns,  with  the
              first  row  and  column (index 0) containing the name of the node the row/column is
              for. All other elements are boolean values, True if there is an arc between  the  2
              nodes of the respective row and column, and False otherwise.

              Note  that  the  matrix  is  symmetric. It does not represent the directionality of
              arcs, only their presence between nodes. It is also unable  to  represent  parallel
              arcs in g.

       struct::graph::op::toAdjacencyList G ?options...?
              Procedure  creates  for  input  graph G, it's representation as Adjacency List.  It
              handles both directed and undirected graphs (default is  undirected).   It  returns
              dictionary  that  for  each  node  (key) returns list of nodes adjacent to it. When
              considering weighted version, for each adjacent node there is also  weight  of  the
              edge included.

              Arguments:

                     Graph object G (input)
                            A graph to convert into an Adjacency List.

              Options:

                     -directed
                            By  default  G  is operated as if it were an Undirected graph.  Using
                            this option tells the command to handle G as the  directed  graph  it
                            is.

                     -weights
                            By  default  any  weight information the graph G may have is ignored.
                            Using this option tells the command to put  weight  information  into
                            the  result.  In that case it is expected that all arcs have a proper
                            weight, and an error is thrown if that is not the case.

       struct::graph::op::kruskal g
              This command takes the graph g and returns a list containing the names of the  arcs
              in  g which span up a minimum weight spanning tree (MST), or, in the case of an un-
              connected graph,  a  minimum  weight  spanning  forest  (except  for  the  1-vertex
              components).  Kruskal's  algorithm  is  used  to  compute the tree or forest.  This
              algorithm has a time complexity of O(E*log E) or O(E* log V), where V is the number
              of vertices and E is the number of edges in graph g.

              The  command will throw an error if one or more arcs in g have no weight associated
              with them.

              A note regarding the result, the command refrains from explicitly listing the nodes
              of the MST as this information is implicitly provided in the arcs already.

       struct::graph::op::prim g
              This  command takes the graph g and returns a list containing the names of the arcs
              in g which span up a minimum weight spanning tree (MST), or, in the case of an  un-
              connected  graph,  a  minimum  weight  spanning  forest  (except  for  the 1-vertex
              components). Prim's algorithm  is  used  to  compute  the  tree  or  forest.   This
              algorithm  has  a time complexity between O(E+V*log V) and O(V*V), depending on the
              implementation (Fibonacci heap + Adjacency list versus Adjacency Matrix).  As usual
              V is the number of vertices and E the number of edges in graph g.

              The  command will throw an error if one or more arcs in g have no weight associated
              with them.

              A note regarding the result, the command refrains from explicitly listing the nodes
              of the MST as this information is implicitly provided in the arcs already.

       struct::graph::op::isBipartite? g ?bipartvar?
              This command takes the graph g and returns a boolean value indicating whether it is
              bipartite (true) or not (false). If the variable bipartvar  is  specified  the  two
              partitions of the graph are there as a list, if, and only if the graph is bipartit.
              If it is not the variable, if specified, is not touched.

       struct::graph::op::tarjan g
              This command computes the set of strongly connected components (SCCs) of the  graph
              g.  The  result  of the command is a list of sets, each of which contains the nodes
              for one of the SCCs of g. The union of all SCCs covers the whole graph, and no  two
              SCCs intersect with each other.

              The  graph  g  is acyclic if all SCCs in the result contain only a single node. The
              graph g is strongly connected if the result contains only a single  SCC  containing
              all nodes of g.

       struct::graph::op::connectedComponents g
              This  command  computes  the  set of connected components (CCs) of the graph g. The
              result of the command is a list of sets, each of which contains the nodes  for  one
              of  the  CCs  of  g.  The  union  of all CCs covers the whole graph, and no two CCs
              intersect with each other.

              The graph g is connected if the result contains only a single  SCC  containing  all
              nodes of g.

       struct::graph::op::connectedComponentOf g n
              This  command  computes  the connected component (CC) of the graph g containing the
              node n. The result of the command is a sets which contains the nodes for the CC  of
              n in g.

              The command will throw an error if n is not a node of the graph g.

       struct::graph::op::isConnected? g
              This  is a convenience command determining whether the graph g is connected or not.
              The result is a boolean value, true if the graph is connected, and false otherwise.

       struct::graph::op::isCutVertex? g n
              This command determines whether the node n in the graph g  is  a  cut  vertex  (aka
              articulation  point).  The  result  is  a  boolean value, true if the node is a cut
              vertex, and false otherwise.

              The command will throw an error if n is not a node of the graph g.

       struct::graph::op::isBridge? g a
              This command determines whether the arc a in the graph g is a bridge (aka cut edge,
              or  isthmus). The result is a boolean value, true if the arc is a bridge, and false
              otherwise.

              The command will throw an error if a is not an arc of the graph g.

       struct::graph::op::isEulerian? g ?tourvar?
              This command determines whether the graph g is eulerian or not.  The  result  is  a
              boolean value, true if the graph is eulerian, and false otherwise.

              If the graph is eulerian and tourvar is specified then an euler tour is computed as
              well and stored in the named variable. The tour is represented by the list of  arcs
              traversed, in the order of traversal.

       struct::graph::op::isSemiEulerian? g ?pathvar?
              This command determines whether the graph g is semi-eulerian or not.  The result is
              a boolean value, true if the graph is semi-eulerian, and false otherwise.

              If the graph is semi-eulerian and pathvar  is  specified  then  an  euler  path  is
              computed  as  well and stored in the named variable. The path is represented by the
              list of arcs traversed, in the order of traversal.

       struct::graph::op::dijkstra g start ?options...?
              This command determines distances in the weighted g from  the  node  start  to  all
              other  nodes  in  the  graph.  The  options specify how to traverse graphs, and the
              format of the result.

              Two options are recognized

              -arcmode mode
                     The  accepted  mode  values  are  directed  and  undirected.   For  directed
                     traversal  all  arcs  are  traversed  from  source to target. For undirected
                     traversal all  arcs  are  traversed  in  the  opposite  direction  as  well.
                     Undirected traversal is the default.

              -outputformat format
                     The  accepted format values are distances and tree. In both cases the result
                     is a dictionary keyed by the names of all nodes in the graph. For  distances
                     the  value  is the distance of the node to start, whereas for tree the value
                     is the path from the node to start, excluding the node itself, but including
                     start. Tree format is the default.

       struct::graph::op::distance g origin destination ?options...?
              This  command determines the (un)directed distance between the two nodes origin and
              destination   in   the   graph   g.   It   accepts   the   option    -arcmode    of
              struct::graph::op::dijkstra.

       struct::graph::op::eccentricity g n ?options...?
              This command determines the (un)directed eccentricity of the node n in the graph g.
              It accepts the option -arcmode of struct::graph::op::dijkstra.

              The (un)directed eccentricity of  a  node  is  the  maximal  (un)directed  distance
              between the node and any other node in the graph.

       struct::graph::op::radius g ?options...?
              This  command  determines  the  (un)directed  radius of the graph g. It accepts the
              option -arcmode of struct::graph::op::dijkstra.

              The (un)directed radius of a graph is the minimal (un)directed eccentricity of  all
              nodes in the graph.

       struct::graph::op::diameter g ?options...?
              This  command  determines  the (un)directed diameter of the graph g. It accepts the
              option -arcmode of struct::graph::op::dijkstra.

              The (un)directed diameter of a graph is the maximal  (un)directed  eccentricity  of
              all nodes in the graph.

       struct::graph::op::BellmanFord G startnode
              Searching  for  shortests paths between chosen node and all other nodes in graph G.
              Based on relaxation method. In comparison to struct::graph::op::dijkstra it doesn't
              need assumption that all weights on edges in input graph G have to be positive.

              That generality sets the complexity of algorithm to - O(V*E), where V is the number
              of vertices and E is number of edges in graph G.

              Arguments:

                     Graph object G (input)
                            Directed, connected and edge weighted graph G, without  any  negative
                            cycles  (  presence  of  cycles with the negative sum of weight means
                            that there is no shortest path, since the total weight becomes  lower
                            each  time  the  cycle  is traversed ). Negative weights on edges are
                            allowed.

                     Node startnode (input)
                            The node for which we find all shortest paths to each other  node  in
                            graph G.

              Result:
                     Dictionary  containing  for  each node (key) distances to each other node in
                     graph G.

       Note: If algorithm finds a negative cycle, it will return error message.

       struct::graph::op::Johnsons G ?options...?
              Searching for shortest paths between all pairs of vertices  in  graph.  For  sparse
              graphs  asymptotically  quicker  than  struct::graph::op::FloydWarshall  algorithm.
              Johnson's       algorithm       uses       struct::graph::op::BellmanFord       and
              struct::graph::op::dijkstra as subprocedures.

              Time  complexity:  O(n**2*log(3tcl)  +n*m), where n is the number of nodes and m is
              the number of edges in graph G.

              Arguments:

                     Graph object G (input)
                            Directed graph G, weighted on edges and  not  containing  any  cycles
                            with  negative  sum  of  weights  ( the presence of such cycles means
                            there is no shortest path, since the total weight becomes lower  each
                            time the cycle is traversed ). Negative weights on edges are allowed.

              Options:

                     -filter
                            Returns only existing distances, cuts all Inf values for non-existing
                            connections between pairs of nodes.

              Result:
                     Dictionary containing distances between all pairs of vertices.

       struct::graph::op::FloydWarshall G
              Searching for shortest paths between all pairs of edges in weighted graphs.

              Time complexity: O(V^3) - where V is number of vertices.

              Memory complexity: O(V^2).

              Arguments:

                     Graph object G (input)
                            Directed and weighted graph G.

              Result:
                     Dictionary containing shortest distances to each node from each node.

              Note: Algorithm finds solutions dynamically. It compares all possible paths through
              the  graph  between  each  pair of vertices. Graph shouldn't possess any cycle with
              negative sum of weights (the presence of such cycles means  there  is  no  shortest
              path, since the total weight becomes lower each time the cycle is traversed).

              On  the  other  hand  algorithm  can be used to find those cycles - if any shortest
              distance found by algorithm for any nodes v and u (when v is the same node as u) is
              negative, that node surely belong to at least one negative cycle.

       struct::graph::op::MetricTravellingSalesman G
              Algorithm  for  solving  a  metric  variation  of Travelling salesman problem.  TSP
              problem is NP-Complete, so there is no efficient  algorithm  to  solve  it.  Greedy
              methods are getting extremely slow, with the increase in the set of nodes.

              Arguments:

                     Graph object G (input)
                            Undirected, weighted graph G.

              Result:
                     Approximated  solution  of minimum Hamilton Cycle - closed path visiting all
                     nodes, each exactly one time.

              Note: It's 2-approximation algorithm.

       struct::graph::op::Christofides G
              Another algorithm for solving metric TSP problem.  Christofides implementation uses
              Max Matching for reaching better approximation factor.

              Arguments:

                     Graph Object G (input)
                            Undirected, weighted graph G.

              Result:
                     Approximated  solution  of minimum Hamilton Cycle - closed path visiting all
                     nodes, each exactly one time.

       Note: It's is a 3/2 approximation algorithm.

       struct::graph::op::GreedyMaxMatching G
              Greedy Max Matching procedure, which finds maximal matching (not maximum) for given
              graph G. It adds edges to solution, beginning from edges with the lowest cost.

              Arguments:

                     Graph Object G (input)
                            Undirected graph G.

              Result:
                     Set of edges - the max matching for graph G.

       struct::graph::op::MaxCut G U V
              Algorithm solving a Maximum Cut Problem.

              Arguments:

                     Graph Object G (input)
                            The graph to cut.

                     List U (output)
                            Variable storing first set of nodes (cut) given by solution.

                     List V (output)
                            Variable storing second set of nodes (cut) given by solution.

              Result:
                     Algorithm returns number of edges between found two sets of nodes.

              Note: MaxCut is a 2-approximation algorithm.

       struct::graph::op::UnweightedKCenter G k
              Approximation algorithm that solves a k-center problem.

              Arguments:

                     Graph Object G (input)
                            Undirected complete graph G, which satisfies triangle inequality.

                     Integer k (input)
                            Positive  integer that sets the number of nodes that will be included
                            in k-center.

              Result:
                     Set of nodes - k center for graph G.

              Note: UnweightedKCenter is a 2-approximation algorithm.

       struct::graph::op::WeightedKCenter G nodeWeights W
              Approximation algorithm that solves a weighted version of k-center problem.

              Arguments:

                     Graph Object G (input)
                            Undirected complete graph G, which satisfies triangle inequality.

                     Integer W (input)
                            Positive integer that sets the maximum possible  weight  of  k-center
                            found by algorithm.

                     List nodeWeights (input)
                            List of nodes and its weights in graph G.

              Result:
                     Set of nodes, which is solution found by algorithm.

              Note:WeightedKCenter is a 3-approximation algorithm.

       struct::graph::op::GreedyMaxIndependentSet G
              A  maximal independent set is an independent set such that adding any other node to
              the set forces the set to contain an edge.

              Algorithm for input graph G returns set of nodes (list), which are contained in Max
              Independent Set found by algorithm.

       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
              Weighted  variation  of  Maximal Independent Set. It takes as an input argument not
              only graph G but also set of weights for all vertices in graph G.

              Note: Read also Maximal Independent Set description for more info.

       struct::graph::op::VerticesCover G
              Vertices cover is a set of vertices such that each edge of the graph is incident to
              at least one vertex of the set. This 2-approximation algorithm searches for minimum
              vertices cover, which is a classical optimization problem in computer  science  and
              is  a  typical example of an NP-hard optimization problem that has an approximation
              algorithm.  For input graph G algorithm returns the set of edges (list),  which  is
              Vertex Cover found by algorithm.

       struct::graph::op::EdmondsKarp G s t
              Improved  Ford-Fulkerson's  algorithm,  computing  the  maximum  flow in given flow
              network G.

              Arguments:

                     Graph Object G (input)
                            Weighted and directed  graph.  Each  edge  should  have  set  integer
                            attribute  considered  as  maximum throughputs that can be carried by
                            that link (edge).

                     Node s (input)
                            The node that is a source for graph G.

                     Node t (input)
                            The node that is a sink for graph G.

              Result:
                     Procedure returns the dictionary containing throughputs for all  edges.  For
                     each key ( the edge between nodes u and v in the form of list u v ) there is
                     a value that is a throughput for that key. Edges where throughput values are
                     equal  to  0  are  not  returned  ( it is like there was no link in the flow
                     network between nodes connected by such edge).

       The general idea of algorithm is finding the shortest augumenting paths  in  graph  G,  as
       long  as  they  exist, and for each path updating the edge's weights along that path, with
       maximum possible throughput. The final (maximum) flow is found  when  there  is  no  other
       augumenting path from source to sink.

       Note: Algorithm complexity : O(V*E), where V is the number of nodes and E is the number of
       edges in graph G.

       struct::graph::op::BusackerGowen G desiredFlow s t
              Algorithm finds solution for a minimum cost flow problem. So, the goal is to find a
              flow,  whose  max  value  can  be desiredFlow, from source node s to sink node t in
              given flow network G.  That network except throughputs at edges has also defined  a
              non-negative  cost  on each edge - cost of using that edge when directing flow with
              that edge ( it can illustrate e.g. fuel usage, time or any other measure  dependent
              on usages ).

              Arguments:

                     Graph Object G (input)
                            Flow  network  (directed  graph),  each edge in graph should have two
                            integer attributes: cost and throughput.

                     Integer desiredFlow (input)
                            Max value of the flow for that network.

                     Node s (input)
                            The source node for graph G.

                     Node t (input)
                            The sink node for graph G.

              Result:
                     Dictionary containing values of used throughputs for  each  edge  (  key  ).
                     found by algorithm.

              Note: Algorithm complexity : O(V**2*desiredFlow), where V is the number of nodes in
              graph G.

       struct::graph::op::ShortestsPathsByBFS G s outputFormat
              Shortest   pathfinding   algorithm   using   BFS   method.   In    comparison    to
              struct::graph::op::dijkstra  it  can work with negative weights on edges. Of course
              negative cycles are not allowed. Algorithm  is  better  than  dijkstra  for  sparse
              graphs,  but  also there exist some pathological cases (those cases generally don't
              appear in practise) that make  time  complexity  increase  exponentially  with  the
              growth of the number of nodes.

              Arguments:

                     Graph Object G (input)
                            Input graph.

                     Node s (input)
                            Source node for which all distances to each other node in graph G are
                            computed.

              Options and result:

                     distances
                            When  selected  outputFormat  is  distances   -   procedure   returns
                            dictionary  containing distances between source node s and each other
                            node in graph G.

                     paths  When selected outputFormat is paths -  procedure  returns  dictionary
                            containing  for each node v, a list of nodes, which is a path between
                            source node s and node v.

       struct::graph::op::BFS G s ?outputFormat...?
              Breadth-First Search - algorithm creates the BFS Tree.  Memory and time complexity:
              O(V + E), where V is the number of nodes and E is number of edges.

              Arguments:

                     Graph Object G (input)
                            Input graph.

                     Node s (input)
                            Source node for BFS procedure.

              Options and result:

                     graph  When  selected  outputFormat  is  graph  -  procedure returns a graph
                            structure (struct::graph), which is equivalent to BFS tree  found  by
                            algorithm.

                     tree   When  selected  outputFormat  is  tree  -  procedure  returns  a tree
                            structure (struct::tree), which is equivalent to BFS  tree  found  by
                            algorithm.

       struct::graph::op::MinimumDiameterSpanningTree G
              The  goal  is  to  find  for  input graph G, the spanning tree that has the minimum
              diameter value.

              General idea of algorithm is to run BFS over  all  vertices  in  graph  G.  If  the
              diameter  d  of the tree is odd, then we are sure that tree given by BFS is minimum
              (considering diameter value). When, diameter d is even, then optimal tree can  have
              minimum diameter equal to d or d-1.

              In  that case, what algorithm does is rebuilding the tree given by BFS, by adding a
              vertice between root node and root's child node (nodes), such that subtree  created
              with child node as root node is the greatest one (has the greatests height). In the
              next step for such rebuilded tree, we run again BFS with new node as root node.  If
              the height of the tree didn't changed, we have found a better solution.

              For  input  graph G algorithm returns the graph structure (struct::graph) that is a
              spanning tree with minimum diameter found by algorithm.

       struct::graph::op::MinimumDegreeSpanningTree G
              Algorithm finds for input graph G, a spanning tree  T  with  the  minimum  possible
              degree. That problem is NP-hard, so algorithm is an approximation algorithm.

              Let  V  be  the  set of nodes for graph G and let W be any subset of V. Lets assume
              also that OPT is optimal solution and ALG is solution found by algorithm for  input
              graph G.

              It can be proven that solution found with the algorithm must fulfil inequality:

              ((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(3tcl) + 1.

              Arguments:

                     Graph Object G (input)
                            Undirected simple graph.

              Result:
                     Algorithm  returns  graph  structure, which is equivalent to spanning tree T
                     found by algorithm.

       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
              Algorithm finds maximum flow for the flow network represented by  graph  G.  It  is
              based  on  the  blocking-flow finding methods, which give us different complexities
              what makes a better fit for different graphs.

              Arguments:

                     Graph Object G (input)
                            Directed graph G representing the flow network. Each edge should have
                            attribute throughput set with integer value.

                     Node s (input)
                            The source node for the flow network G.

                     Node t (input)
                            The sink node for the flow network G.

              Options:

                     dinic  Procedure  will  find  maximum  flow for flow network G using Dinic's
                            algorithm (struct::graph::op::BlockingFlowByDinic) for blocking  flow
                            computation.

                     mkm    Procedure  will  find maximum flow for flow network G using Malhotra,
                            Kumar             and             Maheshwari's              algorithm
                            (struct::graph::op::BlockingFlowByMKM) for blocking flow computation.

              Result:
                     Algorithm  returns dictionary containing it's flow value for each edge (key)
                     in network G.

       Note:    struct::graph::op::BlockingFlowByDinic    gives    O(m*n^2)    complexity     and
       struct::graph::op::BlockingFlowByMKM  gives  O(n^3)  complexity,  where n is the number of
       nodes and m is the number of edges in flow network G.

       struct::graph::op::BlockingFlowByDinic G s t
              Algorithm for given network G with source s and sink  t,  finds  a  blocking  flow,
              which can be used to obtain a maximum flow for that network G.

              Arguments:

                     Graph Object G (input)
                            Directed graph G representing the flow network. Each edge should have
                            attribute throughput set with integer value.

                     Node s (input)
                            The source node for the flow network G.

                     Node t (input)
                            The sink node for the flow network G.

              Result:
                     Algorithm returns dictionary containing it's blocking flow  value  for  each
                     edge (key) in network G.

              Note: Algorithm's complexity is O(n*m), where n is the number of nodes and m is the
              number of edges in flow network G.

       struct::graph::op::BlockingFlowByMKM G s t
              Algorithm for given network G with source s and sink  t,  finds  a  blocking  flow,
              which can be used to obtain a maximum flow for that network G.

              Arguments:

                     Graph Object G (input)
                            Directed graph G representing the flow network. Each edge should have
                            attribute throughput set with integer value.

                     Node s (input)
                            The source node for the flow network G.

                     Node t (input)
                            The sink node for the flow network G.

              Result:
                     Algorithm returns dictionary containing it's blocking flow  value  for  each
                     edge (key) in network G.

              Note:  Algorithm's  complexity  is  O(n^2),  where n is the number of nodes in flow
              network G.

       struct::graph::op::createResidualGraph G f
              Procedure creates a residual graph (or residual network ) for network G  and  given
              flow f.

              Arguments:

                     Graph Object G (input)
                            Flow  network  (directed  graph  where  each  edge has set attribute:
                            throughput ).

                     dictionary f (input)
                            Current flows in flow network G.

              Result:
                     Procedure returns graph structure that is  a  residual  graph  created  from
                     input flow network G.

       struct::graph::op::createAugmentingNetwork G f path
              Procedure creates an augmenting network for a given residual network G , flow f and
              augmenting path path.

              Arguments:

                     Graph Object G (input)
                            Residual network (directed graph), where for every edge there are set
                            two attributes: throughput and cost.

                     Dictionary f (input)
                            Dictionary  which contains for every edge (key), current value of the
                            flow on that edge.

                     List path (input)
                            Augmenting path, set of edges (list) for which we create the  network
                            modification.

              Result:
                     Algorithm   returns  graph  structure  containing  the  modified  augmenting
                     network.

       struct::graph::op::createLevelGraph Gf s
              For given residual graph Gf procedure finds the level graph.

              Arguments:

                     Graph Object Gf (input)
                            Residual network, where each edge has it's attribute  throughput  set
                            with certain value.

                     Node s (input)
                            The source node for the residual network Gf.

              Result:
                     Procedure returns a level graph created from input residual network.

       struct::graph::op::TSPLocalSearching G C
              Algorithm  is  a  heuristic of local searching for Travelling Salesman Problem. For
              some solution of TSP problem, it checks if it's possible to find a better solution.
              As TSP is well known NP-Complete problem, so algorithm is a approximation algorithm
              (with 2 approximation factor).

              Arguments:

                     Graph Object G (input)
                            Undirected and complete graph with attributes "weight"  set  on  each
                            single edge.

                     List C (input)
                            A  list  of  edges  being Hamiltonian cycle, which is solution of TSP
                            Problem for graph G.

              Result:
                     Algorithm returns the best solution for TSP problem, it was able to find.

              Note: The solution depends on the choosing of the beginning cycle C. It's not  true
              that  better  cycle  assures that better solution will be found, but practise shows
              that we should give starting cycle with as small sum of weights as possible.

       struct::graph::op::TSPLocalSearching3Approx G C
              Algorithm is a heuristic of local searching for Travelling  Salesman  Problem.  For
              some solution of TSP problem, it checks if it's possible to find a better solution.
              As TSP is well known NP-Complete problem, so algorithm is a approximation algorithm
              (with 3 approximation factor).

              Arguments:

                     Graph Object G (input)
                            Undirected  and  complete  graph with attributes "weight" set on each
                            single edge.

                     List C (input)
                            A list of edges being Hamiltonian cycle, which  is  solution  of  TSP
                            Problem for graph G.

              Result:
                     Algorithm returns the best solution for TSP problem, it was able to find.

              Note: In practise 3-approximation algorithm turns out to be far more effective than
              2-approximation, but it gives worser approximation factor.  Further  heuristics  of
              local  searching  (e.g.  4-approximation)  doesn't  give enough boost to square the
              increase of approximation factor, so 2 and 3 approximations are mainly used.

       struct::graph::op::createSquaredGraph G
              X-Squared graph is a graph with the same set of nodes  as  input  graph  G,  but  a
              different  set  of  edges.  X-Squared  graph  has  edge  (u,v), if and only if, the
              distance between u and v nodes is not greater than X and u != v.

              Procedure for input graph G, returns its two-squared graph.

              Note: Distances used in choosing new set of edges are  considering  the  number  of
              edges, not the sum of weights at edges.

       struct::graph::op::createCompleteGraph G originalEdges
              For  input graph G procedure adds missing arcs to make it a complete graph. It also
              holds in variable originalEdges the set of arcs that graph G possessed before  that
              operation.

BACKGROUND THEORY AND TERMS

   SHORTEST PATH PROBLEM
       Definition (single-pair shortest path problem):
              Formally,  given  a  weighted  graph  (let V be the set of vertices, and E a set of
              edges), and one vertice v of V, find a path P from v to a v' of V so that  the  sum
              of weights on edges along the path is minimal among all paths connecting v to v'.

       Generalizations:

              •      The  single-source  shortest path problem, in which we have to find shortest
                     paths from a source vertex v to all other vertices in the graph.

              •      The single-destination shortest path problem,  in  which  we  have  to  find
                     shortest paths from all vertices in the graph to a single destination vertex
                     v. This can be  reduced  to  the  single-source  shortest  path  problem  by
                     reversing the edges in the graph.

              •      The all-pairs shortest path problem, in which we have to find shortest paths
                     between every pair of vertices v, v' in the graph.

              Note: The result of Shortest Path problem can be Shortest Path  tree,  which  is  a
              subgraph  of  a  given  (possibly  weighted) graph constructed so that the distance
              between a selected root node and all other nodes is minimal. It is a  tree  because
              if  there  are two paths between the root node and some vertex v (i.e. a cycle), we
              can delete the last edge of the longer path without increasing  the  distance  from
              the root node to any node in the subgraph.

   TRAVELLING SALESMAN PROBLEM
       Definition:
              For  given edge-weighted (weights on edges should be positive) graph the goal is to
              find the cycle that visits each node in graph exactly once (Hamiltonian cycle).

       Generalizations:

              •      Metric TSP - A very natural restriction of the TSP is to  require  that  the
                     distances  between  cities  form  a  metric, i.e., they satisfy the triangle
                     inequality. That is, for any 3 cities A, B and C, the distance between A and
                     C  must  be  at most the distance from A to B plus the distance from B to C.
                     Most natural instances of TSP satisfy this constraint.

              •      Euclidean TSP - Euclidean TSP, or planar TSP, is the TSP with  the  distance
                     being  the  ordinary Euclidean distance.  Euclidean TSP is a particular case
                     of TSP with triangle inequality, since  distances  in  plane  obey  triangle
                     inequality.  However,  it  seems to be easier than general TSP with triangle
                     inequality. For example, the minimum spanning tree of the  graph  associated
                     with  an instance of Euclidean TSP is a Euclidean minimum spanning tree, and
                     so can be computed in expected O(n log n) time for  n  points  (considerably
                     less  than  the  number  of  edges). This enables the simple 2-approximation
                     algorithm for TSP with triangle inequality above to operate more quickly.

              •      Asymmetric TSP - In most cases, the distance between two nodes  in  the  TSP
                     network  is the same in both directions.  The case where the distance from A
                     to B is not equal to the distance from B to A is called asymmetric  TSP.   A
                     practical  application  of  an  asymmetric  TSP  is route optimisation using
                     street-level routing (asymmetric due  to  one-way  streets,  slip-roads  and
                     motorways).

   MATCHING PROBLEM
       Definition:
              Given  a  graph  G  =  (V,E), a matching or edge-independent set M in G is a set of
              pairwise non-adjacent edges, that is, no two edges share a common vertex. A  vertex
              is matched if it is incident to an edge in the matching M.  Otherwise the vertex is
              unmatched.

       Generalizations:

              •      Maximal matching - a matching M of a graph G with the property that  if  any
                     edge  not  in  M  is  added  to M, it is no longer a matching, that is, M is
                     maximal if it is not a proper subset of any other matching in graph  G.   In
                     other  words,  a matching M of a graph G is maximal if every edge in G has a
                     non-empty intersection with at least one edge in M.

              •      Maximum matching - a matching that contains the largest possible  number  of
                     edges.  There may be many maximum matchings.  The matching number of a graph
                     G is the size of a maximum matching. Note that  every  maximum  matching  is
                     maximal, but not every maximal matching is a maximum matching.

              •      Perfect  matching - a matching which matches all vertices of the graph. That
                     is, every vertex of the graph  is  incident  to  exactly  one  edge  of  the
                     matching.  Every  perfect  matching  is  maximum  and hence maximal. In some
                     literature, the term complete matching is used. A perfect matching is also a
                     minimum-size  edge  cover.  Moreover,  the  size of a maximum matching is no
                     larger than the size of a minimum edge cover.

              •      Near-perfect matching - a matching in which exactly one vertex is unmatched.
                     This can only occur when the graph has an odd number of vertices, and such a
                     matching must be maximum. If, for every vertex in a graph, there is a  near-
                     perfect  matching  that  omits  only  that  vertex, the graph is also called
                     factor-critical.

       Related terms:

              •      Alternating path - given a matching M, an alternating  path  is  a  path  in
                     which  the  edges  belong  alternatively  to  the  matching  and  not to the
                     matching.

              •      Augmenting path - given a matching M, an augmenting path is  an  alternating
                     path that starts from and ends on free (unmatched) vertices.

   CUT PROBLEMS
       Definition:
              A cut is a partition of the vertices of a graph into two disjoint subsets. The cut-
              set of the cut is the set of edges whose end points are in different subsets of the
              partition. Edges are said to be crossing the cut if they are in its cut-set.

              Formally:

              •      a cut C = (S,T) is a partition of V of a graph G = (V, E).

              •      an  s-t cut C = (S,T) of a flow network N = (V, E) is a cut of N such that s
                     is included in S and t is included in T, where s and t are  the  source  and
                     the sink of N respectively.

              •      The  cut-set  of  a cut C = (S,T) is such set of edges from graph G = (V, E)
                     that each edge (u, v) satisfies condition that u is included in S and  v  is
                     included in T.

       In  an  unweighted  undirected  graph,  the size or weight of a cut is the number of edges
       crossing the cut. In a weighted graph, the same term is defined by the sum of the  weights
       of the edges crossing the cut.

       In  a  flow  network,  an  s-t cut is a cut that requires the source and the sink to be in
       different subsets, and its cut-set only consists of edges going from the source's side  to
       the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge
       in the cut-set.

       The cut of a graph can sometimes refer to its cut-set instead of the partition.

       Generalizations:

              •      Minimum cut - A cut is minimum if the size of the cut is not larger than the
                     size of any other cut.

              •      Maximum  cut  -  A cut is maximum if the size of the cut is not smaller than
                     the size of any other cut.

              •      Sparsest cut - The Sparsest cut problem is to bipartition the vertices so as
                     to  minimize  the ratio of the number of edges across the cut divided by the
                     number of vertices in the smaller half of the partition.

   K-CENTER PROBLEM
       Definitions:

              Unweighted K-Center
                     For any set S ( which is subset of V ) and node v, let the  connect(v,S)  be
                     the  cost  of  cheapest edge connecting v with any node in S. The goal is to
                     find such S, that |S| = k and max_v{connect(v,S)} is possibly small.

                     In other words, we can use it i.e. for finding best locations in the city  (
                     nodes  of  input  graph ) for placing k buildings, such that those buildings
                     will be as close as possible to all other locations in town.

              Weighted K-Center
                     The variation of unweighted k-center problem.  Besides  the  fact  graph  is
                     edge-weighted,  there  are  also weights on vertices of input graph G. We've
                     got also restriction W. The goal is to choose such set of nodes S ( which is
                     a  subset  of  V  ),  that  it's total weight is not greater than W and also
                     function: max_v { min_u { cost(u,v) }} has the smallest possible worth  (  v
                     is a node in V and u is a node in S ).

   FLOW PROBLEMS
       Definitions:

              •      the  maximum  flow  problem  - the goal is to find a feasible flow through a
                     single-source, single-sink flow network that is maximum.  The  maximum  flow
                     problem can be seen as a special case of more complex network flow problems,
                     such as the circulation problem.  The maximum value of an s-t flow is  equal
                     to  the minimum capacity of an s-t cut in the network, as stated in the max-
                     flow min-cut theorem.

                     More formally for flow network G = (V,E), where for each edge (u, v) we have
                     its  throuhgput  c(u,v)  defined.  As  flow  F we define set of non-negative
                     integer attributes f(u,v) assigned to edges, satisfying such conditions:

                     [1]    for each edge (u, v) in G such condition should be satisfied:       0
                            <= f(u,v) <= c(u,v)

                     [2]    Network  G has source node s such that the flow F is equal to the sum
                            of outcoming flow decreased by the sum of  incoming  flow  from  that
                            source node s.

                     [3]    Network  G has sink node t such that the the -F value is equal to the
                            sum of the incoming flow decreased by the sum of outcoming flow  from
                            that sink node t.

                     [4]    For  each  node that is not a source or sink the sum of incoming flow
                            and sum of outcoming flow should be equal.

              •      the minimum cost flow problem - the goal is finding  the  cheapest  possible
                     way of sending a certain amount of flow through a flow network.

              •      blocking  flow - a blocking flow for a residual network Gf we name such flow
                     b in Gf that:

                     [1]    Each path from sink to source is the shortest path in Gf.

                     [2]    Each shortest path in Gf contains an edge with fully used  throughput
                            in Gf+b.

              •      residual network - for a flow network G and flow f residual network is built
                     with those edges, which can send larger flow. It contains only those  edges,
                     which can send flow larger than 0.

              •      level network - it has the same set of nodes as residual graph, but has only
                     those  edges  (u,v)  from  Gf  for  which  such   equality   is   satisfied:
                     distance(s,u)+1 = distance(s,v).

              •      augmenting  network  -  it is a modification of residual network considering
                     the new flow values. Structure stays unchanged but values of throughputs and
                     costs at edges are different.

   APPROXIMATION ALGORITHM
       k-approximation algorithm:
              Algorithm  is  a k-approximation, when for ALG (solution returned by algorithm) and
              OPT (optimal solution), such inequality is true:

              •      for minimalization problems: ALG/OPT <= k

              •      for maximalization problems: OPT/ALG <= k

REFERENCES

       [1]    Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]

       [2]    Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]

       [3]    Kruskal's algorithm [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]

       [4]    Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algorithm]

       [5]    Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]

       [6]    Strongly                            connected                            components
              [http://en.wikipedia.org/wiki/Strongly_connected_components]

       [7]    Tarjan's          strongly          connected          components         algorithm
              [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm]

       [8]    Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]

       [9]    Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]

       [10]   Bellman-Ford's algorithm [http://en.wikipedia.org/wiki/Bellman-Ford_algorithm]

       [11]   Johnson's algorithm [http://en.wikipedia.org/wiki/Johnson_algorithm]

       [12]   Floyd-Warshall's algorithm [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm]

       [13]   Travelling                             Salesman                             Problem
              [http://en.wikipedia.org/wiki/Travelling_salesman_problem]

       [14]   Christofides Algorithm [http://en.wikipedia.org/wiki/Christofides_algorithm]

       [15]   Max Cut [http://en.wikipedia.org/wiki/Maxcut]

       [16]   Matching [http://en.wikipedia.org/wiki/Matching]

       [17]   Max Independent Set [http://en.wikipedia.org/wiki/Maximal_independent_set]

       [18]   Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]

       [19]   Ford-Fulkerson's algorithm [http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm]

       [20]   Maximum Flow problem [http://en.wikipedia.org/wiki/Maximum_flow_problem]

       [21]   Busacker-Gowen's algorithm [http://en.wikipedia.org/wiki/Minimum_cost_flow_problem]

       [22]   Dinic's algorithm [http://en.wikipedia.org/wiki/Dinic's_algorithm]

       [23]   K-Center problem [http://www.csc.kth.se/~viggo/wwwcompendium/node128.html]

       [24]   BFS [http://en.wikipedia.org/wiki/Breadth-first_search]

       [25]   Minimum      Degree     Spanning     Tree     [http://en.wikipedia.org/wiki/Degree-
              constrained_spanning_tree]

       [26]   Approximation algorithm [http://en.wikipedia.org/wiki/Approximation_algorithm]

BUGS, IDEAS, FEEDBACK

       This document, and the package it describes,  will  undoubtedly  contain  bugs  and  other
       problems.   Please  report  such in the category struct :: graph of the Tcllib SF Trackers
       [http://sourceforge.net/tracker/?group_id=12883].   Please  also  report  any  ideas   for
       enhancements you may have for either package and/or documentation.

KEYWORDS

       adjacency  list,  adjacency  matrix,  adjacent, approximation algorithm, arc, articulation
       point, augmenting  network,  augmenting  path,  bfs,  bipartite,  blocking  flow,  bridge,
       complete  graph,  connected  component,  cut  edge, cut vertex, degree, degree constrained
       spanning tree, diameter, dijkstra, distance,  eccentricity,  edge,  flow  network,  graph,
       heuristic,  independent  set,  isthmus,  level graph, local searching, loop, matching, max
       cut, maximum flow, minimal spanning tree, minimum cost flow, minimum degree spanning tree,
       minimum  diameter  spanning  tree, neighbour, node, radius, residual graph, shortest path,
       squared graph, strongly connected component, subgraph, travelling salesman, vertex, vertex
       cover

CATEGORY

       Data structures

COPYRIGHT

       Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>
       Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
       Copyright (c) 2009 Michal Antoniewski <antoniewski.m@gmail.com>