1struct::graph::op(n)          Tcl Data Structures         struct::graph::op(n)
2
3
4
5______________________________________________________________________________
6

NAME

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

SYNOPSIS

11       package require Tcl  8.4
12
13       package require struct::graph::op  ?0.11.3?
14
15       struct::graph::op::toAdjacencyMatrix g
16
17       struct::graph::op::toAdjacencyList G ?options...?
18
19       struct::graph::op::kruskal g
20
21       struct::graph::op::prim g
22
23       struct::graph::op::isBipartite? g ?bipartvar?
24
25       struct::graph::op::tarjan g
26
27       struct::graph::op::connectedComponents g
28
29       struct::graph::op::connectedComponentOf g n
30
31       struct::graph::op::isConnected? g
32
33       struct::graph::op::isCutVertex? g n
34
35       struct::graph::op::isBridge? g a
36
37       struct::graph::op::isEulerian? g ?tourvar?
38
39       struct::graph::op::isSemiEulerian? g ?pathvar?
40
41       struct::graph::op::dijkstra g start ?options...?
42
43       struct::graph::op::distance g origin destination ?options...?
44
45       struct::graph::op::eccentricity g n ?options...?
46
47       struct::graph::op::radius g ?options...?
48
49       struct::graph::op::diameter g ?options...?
50
51       struct::graph::op::BellmanFord G startnode
52
53       struct::graph::op::Johnsons G ?options...?
54
55       struct::graph::op::FloydWarshall G
56
57       struct::graph::op::MetricTravellingSalesman G
58
59       struct::graph::op::Christofides G
60
61       struct::graph::op::GreedyMaxMatching G
62
63       struct::graph::op::MaxCut G U V
64
65       struct::graph::op::UnweightedKCenter G k
66
67       struct::graph::op::WeightedKCenter G nodeWeights W
68
69       struct::graph::op::GreedyMaxIndependentSet G
70
71       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
72
73       struct::graph::op::VerticesCover G
74
75       struct::graph::op::EdmondsKarp G s t
76
77       struct::graph::op::BusackerGowen G desiredFlow s t
78
79       struct::graph::op::ShortestsPathsByBFS G s outputFormat
80
81       struct::graph::op::BFS G s ?outputFormat...?
82
83       struct::graph::op::MinimumDiameterSpanningTree G
84
85       struct::graph::op::MinimumDegreeSpanningTree G
86
87       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
88
89       struct::graph::op::BlockingFlowByDinic G s t
90
91       struct::graph::op::BlockingFlowByMKM G s t
92
93       struct::graph::op::createResidualGraph G f
94
95       struct::graph::op::createAugmentingNetwork G f path
96
97       struct::graph::op::createLevelGraph Gf s
98
99       struct::graph::op::TSPLocalSearching G C
100
101       struct::graph::op::TSPLocalSearching3Approx G C
102
103       struct::graph::op::createSquaredGraph G
104
105       struct::graph::op::createCompleteGraph G originalEdges
106
107______________________________________________________________________________
108

DESCRIPTION

110       The package described by this document, struct::graph::op, is a compan‐
111       ion to the package struct::graph. It provides a series of common opera‐
112       tions and algorithms applicable to (un)directed graphs.
113
114       Despite  being  a  companion  the  package is not directly dependent on
115       struct::graph, only on the API defined by that package. I.e. the opera‐
116       tions of this package can be applied to any and all graph objects which
117       provide the same API as the objects created through struct::graph.
118

OPERATIONS

120       struct::graph::op::toAdjacencyMatrix g
121              This command takes the graph g and returns a  nested  list  con‐
122              taining the adjacency matrix of g.
123
124              The  elements  of the outer list are the rows of the matrix, the
125              inner elements are the column values in each row. The matrix has
126              "n+1"  rows and columns, with the first row and column (index 0)
127              containing the name of the node the row/column is for. All other
128              elements are boolean values, True if there is an arc between the
129              2 nodes of the respective row and column, and False otherwise.
130
131              Note that the matrix is symmetric. It  does  not  represent  the
132              directionality of arcs, only their presence between nodes. It is
133              also unable to represent parallel arcs in g.
134
135       struct::graph::op::toAdjacencyList G ?options...?
136              Procedure creates for input  graph  G,  it's  representation  as
137              Adjacency  List.  It handles both directed and undirected graphs
138              (default is undirected).  It returns dictionary  that  for  each
139              node  (key) returns list of nodes adjacent to it. When consider‐
140              ing weighted version, for  each  adjacent  node  there  is  also
141              weight of the edge included.
142
143
144              Arguments:
145
146                     Graph object G (input)
147                            A graph to convert into an Adjacency List.
148
149              Options:
150
151                     -directed
152                            By  default  G  is operated as if it were an Undi‐
153                            rected graph.  Using this option tells the command
154                            to handle G as the directed graph it is.
155
156                     -weights
157                            By  default any weight information the graph G may
158                            have is ignored.  Using this option tells the com‐
159                            mand  to  put  weight information into the result.
160                            In that case it is expected that all arcs  have  a
161                            proper  weight,  and an error is thrown if that is
162                            not the case.
163
164       struct::graph::op::kruskal g
165              This command takes the graph g and returns a list containing the
166              names  of  the arcs in g which span up a minimum weight spanning
167              tree (MST), or, in the case of an un-connected graph, a  minimum
168              weight  spanning  forest  (except  for the 1-vertex components).
169              Kruskal's algorithm is used to compute the tree or forest.  This
170              algorithm  has  a  time complexity of O(E*log E) or O(E* log V),
171              where V is the number of vertices and E is the number  of  edges
172              in graph g.
173
174              The command will throw an error if one or more arcs in g have no
175              weight associated with them.
176
177              A note regarding the result, the command refrains  from  explic‐
178              itly listing the nodes of the MST as this information is implic‐
179              itly provided in the arcs already.
180
181       struct::graph::op::prim g
182              This command takes the graph g and returns a list containing the
183              names  of  the arcs in g which span up a minimum weight spanning
184              tree (MST), or, in the case of an un-connected graph, a  minimum
185              weight  spanning  forest  (except  for the 1-vertex components).
186              Prim's algorithm is used to compute the tree  or  forest.   This
187              algorithm has a time complexity between O(E+V*log V) and O(V*V),
188              depending on the implementation (Fibonacci heap + Adjacency list
189              versus  Adjacency Matrix).  As usual V is the number of vertices
190              and E the number of edges in graph g.
191
192              The command will throw an error if one or more arcs in g have no
193              weight associated with them.
194
195              A  note  regarding the result, the command refrains from explic‐
196              itly listing the nodes of the MST as this information is implic‐
197              itly provided in the arcs already.
198
199       struct::graph::op::isBipartite? g ?bipartvar?
200              This command takes the graph g and returns a boolean value indi‐
201              cating whether it is bipartite (true) or  not  (false).  If  the
202              variable  bipartvar is specified the two partitions of the graph
203              are there as a list, if, and only if the graph is  bipartit.  If
204              it is not the variable, if specified, is not touched.
205
206       struct::graph::op::tarjan g
207              This  command  computes the set of strongly connected components
208              (SCCs) of the graph g. The result of the command is  a  list  of
209              sets, each of which contains the nodes for one of the SCCs of g.
210              The union of all SCCs covers the whole graph, and  no  two  SCCs
211              intersect with each other.
212
213              The  graph g is acyclic if all SCCs in the result contain only a
214              single node. The graph g is strongly  connected  if  the  result
215              contains only a single SCC containing all nodes of g.
216
217       struct::graph::op::connectedComponents g
218              This  command  computes the set of connected components (CCs) of
219              the graph g. The result of the command is a list of  sets,  each
220              of  which  contains the nodes for one of the CCs of g. The union
221              of all CCs covers the whole graph, and no two CCs intersect with
222              each other.
223
224              The  graph  g  is connected if the result contains only a single
225              SCC containing all nodes of g.
226
227       struct::graph::op::connectedComponentOf g n
228              This command computes the connected component (CC) of the  graph
229              g  containing  the  node  n. The result of the command is a sets
230              which contains the nodes for the CC of n in g.
231
232              The command will throw an error if n is not a node of the  graph
233              g.
234
235       struct::graph::op::isConnected? g
236              This is a convenience command determining whether the graph g is
237              connected or not.  The result is a boolean value,  true  if  the
238              graph is connected, and false otherwise.
239
240       struct::graph::op::isCutVertex? g n
241              This  command  determines whether the node n in the graph g is a
242              cut vertex (aka articulation point). The  result  is  a  boolean
243              value, true if the node is a cut vertex, and false otherwise.
244
245              The  command will throw an error if n is not a node of the graph
246              g.
247
248       struct::graph::op::isBridge? g a
249              This command determines whether the arc a in the graph  g  is  a
250              bridge  (aka  cut  edge,  or  isthmus).  The result is a boolean
251              value, true if the arc is a bridge, and false otherwise.
252
253              The command will throw an error if a is not an arc of the  graph
254              g.
255
256       struct::graph::op::isEulerian? g ?tourvar?
257              This  command determines whether the graph g is eulerian or not.
258              The result is a boolean value, true if the  graph  is  eulerian,
259              and false otherwise.
260
261              If  the graph is eulerian and tourvar is specified then an euler
262              tour is computed as well and stored in the named  variable.  The
263              tour  is represented by the list of arcs traversed, in the order
264              of traversal.
265
266       struct::graph::op::isSemiEulerian? g ?pathvar?
267              This command determines whether the graph g is semi-eulerian  or
268              not.   The result is a boolean value, true if the graph is semi-
269              eulerian, and false otherwise.
270
271              If the graph is semi-eulerian and pathvar is specified  then  an
272              euler path is computed as well and stored in the named variable.
273              The path is represented by the list of arcs  traversed,  in  the
274              order of traversal.
275
276       struct::graph::op::dijkstra g start ?options...?
277              This  command  determines  distances  in the weighted g from the
278              node start to all other nodes in the graph. The options  specify
279              how to traverse graphs, and the format of the result.
280
281              Two options are recognized
282
283              -arcmode mode
284                     The  accepted  mode  values  are directed and undirected.
285                     For directed traversal all arcs are traversed from source
286                     to  target.  For  undirected  traversal all arcs are tra‐
287                     versed in the opposite direction as well. Undirected tra‐
288                     versal is the default.
289
290              -outputformat format
291                     The  accepted  format  values  are distances and tree. In
292                     both cases the result is a dictionary keyed by the  names
293                     of all nodes in the graph. For distances the value is the
294                     distance of the node to start, whereas for tree the value
295                     is  the  path  from the node to start, excluding the node
296                     itself, but including start. Tree format is the default.
297
298       struct::graph::op::distance g origin destination ?options...?
299              This command determines the (un)directed  distance  between  the
300              two  nodes origin and destination in the graph g. It accepts the
301              option -arcmode of struct::graph::op::dijkstra.
302
303       struct::graph::op::eccentricity g n ?options...?
304              This command determines the  (un)directed  eccentricity  of  the
305              node  n  in  the  graph  g.  It  accepts  the option -arcmode of
306              struct::graph::op::dijkstra.
307
308              The  (un)directed  eccentricity  of  a  node  is   the   maximal
309              (un)directed distance between the node and any other node in the
310              graph.
311
312       struct::graph::op::radius g ?options...?
313              This command determines the (un)directed radius of the graph  g.
314              It accepts the option -arcmode of struct::graph::op::dijkstra.
315
316              The  (un)directed  radius of a graph is the minimal (un)directed
317              eccentricity of all nodes in the graph.
318
319       struct::graph::op::diameter g ?options...?
320              This command determines the (un)directed diameter of  the  graph
321              g.  It  accepts  the option -arcmode of struct::graph::op::dijk‐
322              stra.
323
324              The (un)directed diameter of a graph is the maximal (un)directed
325              eccentricity of all nodes in the graph.
326
327       struct::graph::op::BellmanFord G startnode
328              Searching  for shortests paths between chosen node and all other
329              nodes in graph G. Based on relaxation method. In  comparison  to
330              struct::graph::op::dijkstra  it doesn't need assumption that all
331              weights on edges in input graph G have to be positive.
332
333              That generality sets the complexity of algorithm  to  -  O(V*E),
334              where  V  is  the number of vertices and E is number of edges in
335              graph G.
336
337
338              Arguments:
339
340                     Graph object G (input)
341                            Directed, connected and  edge  weighted  graph  G,
342                            without  any  negative cycles ( presence of cycles
343                            with the negative sum of weight means  that  there
344                            is  no  shortest  path,  since  the  total  weight
345                            becomes lower each time the cycle is traversed  ).
346                            Negative weights on edges are allowed.
347
348                     Node startnode (input)
349                            The  node  for which we find all shortest paths to
350                            each other node in graph G.
351
352              Result:
353                     Dictionary containing for each node  (key)  distances  to
354                     each other node in graph G.
355
356       Note:  If  algorithm  finds a negative cycle, it will return error mes‐
357       sage.
358
359       struct::graph::op::Johnsons G ?options...?
360              Searching for shortest paths between all pairs  of  vertices  in
361              graph.   For   sparse   graphs   asymptotically   quicker   than
362              struct::graph::op::FloydWarshall algorithm. Johnson's  algorithm
363              uses struct::graph::op::BellmanFord and struct::graph::op::dijk‐
364              stra as subprocedures.
365
366              Time complexity: O(n**2*log(n) +n*m), where n is the  number  of
367              nodes and m is the number of edges in graph G.
368
369
370              Arguments:
371
372                     Graph object G (input)
373                            Directed  graph  G, weighted on edges and not con‐
374                            taining any cycles with negative sum of weights  (
375                            the  presence  of  such  cycles  means there is no
376                            shortest path,  since  the  total  weight  becomes
377                            lower each time the cycle is traversed ). Negative
378                            weights on edges are allowed.
379
380              Options:
381
382                     -filter
383                            Returns only existing distances, cuts all Inf val‐
384                            ues  for non-existing connections between pairs of
385                            nodes.
386
387              Result:
388                     Dictionary containing distances between all pairs of ver‐
389                     tices.
390
391       struct::graph::op::FloydWarshall G
392              Searching  for  shortest  paths  between  all  pairs of edges in
393              weighted graphs.
394
395              Time complexity: O(V^3) - where V is number of vertices.
396
397              Memory complexity: O(V^2).
398
399
400              Arguments:
401
402                     Graph object G (input)
403                            Directed and weighted graph G.
404
405              Result:
406                     Dictionary containing shortest  distances  to  each  node
407                     from each node.
408
409              Note:  Algorithm  finds  solutions  dynamically. It compares all
410              possible paths through the graph between each pair of  vertices.
411              Graph  shouldn't  possess any cycle with negative sum of weights
412              (the presence of such cycles means there is  no  shortest  path,
413              since the total weight becomes lower each time the cycle is tra‐
414              versed).
415
416              On the other hand algorithm can be used to find those  cycles  -
417              if  any shortest distance found by algorithm for any nodes v and
418              u (when v is the same node as u) is negative, that  node  surely
419              belong to at least one negative cycle.
420
421       struct::graph::op::MetricTravellingSalesman G
422              Algorithm  for solving a metric variation of Travelling salesman
423              problem.  TSP problem is NP-Complete, so there is  no  efficient
424              algorithm  to  solve  it.  Greedy  methods are getting extremely
425              slow, with the increase in the set of nodes.
426
427
428              Arguments:
429
430                     Graph object G (input)
431                            Undirected, weighted graph G.
432
433              Result:
434                     Approximated solution of minimum Hamilton Cycle -  closed
435                     path visiting all nodes, each exactly one time.
436
437              Note: It's 2-approximation algorithm.
438
439       struct::graph::op::Christofides G
440              Another  algorithm for solving metric TSP problem.  Christofides
441              implementation uses Max Matching for reaching better  approxima‐
442              tion factor.
443
444
445              Arguments:
446
447                     Graph Object G (input)
448                            Undirected, weighted graph G.
449
450              Result:
451                     Approximated  solution of minimum Hamilton Cycle - closed
452                     path visiting all nodes, each exactly one time.
453
454       Note: It's is a 3/2 approximation algorithm.
455
456       struct::graph::op::GreedyMaxMatching G
457              Greedy Max Matching procedure, which finds maximal matching (not
458              maximum) for given graph G. It adds edges to solution, beginning
459              from edges with the lowest cost.
460
461
462              Arguments:
463
464                     Graph Object G (input)
465                            Undirected graph G.
466
467              Result:
468                     Set of edges - the max matching for graph G.
469
470       struct::graph::op::MaxCut G U V
471              Algorithm solving a Maximum Cut Problem.
472
473
474              Arguments:
475
476                     Graph Object G (input)
477                            The graph to cut.
478
479                     List U (output)
480                            Variable storing first set of nodes (cut) given by
481                            solution.
482
483                     List V (output)
484                            Variable  storing  second set of nodes (cut) given
485                            by solution.
486
487              Result:
488                     Algorithm returns number of edges between found two  sets
489                     of nodes.
490
491              Note: MaxCut is a 2-approximation algorithm.
492
493       struct::graph::op::UnweightedKCenter G k
494              Approximation algorithm that solves a k-center problem.
495
496
497              Arguments:
498
499                     Graph Object G (input)
500                            Undirected  complete graph G, which satisfies tri‐
501                            angle inequality.
502
503
504                     Integer k (input)
505                            Positive integer that sets  the  number  of  nodes
506                            that will be included in k-center.
507
508              Result:
509                     Set of nodes - k center for graph G.
510
511              Note: UnweightedKCenter is a 2-approximation algorithm.
512
513       struct::graph::op::WeightedKCenter G nodeWeights W
514              Approximation algorithm that solves a weighted version of k-cen‐
515              ter problem.
516
517
518              Arguments:
519
520                     Graph Object G (input)
521                            Undirected complete graph G, which satisfies  tri‐
522                            angle inequality.
523
524                     Integer W (input)
525                            Positive  integer  that  sets the maximum possible
526                            weight of k-center found by algorithm.
527
528                     List nodeWeights (input)
529                            List of nodes and its weights in graph G.
530
531              Result:
532                     Set of nodes, which is solution found by algorithm.
533
534              Note:WeightedKCenter is a 3-approximation algorithm.
535
536       struct::graph::op::GreedyMaxIndependentSet G
537              A maximal independent set is an independent set such that adding
538              any other node to the set forces the set to contain an edge.
539
540              Algorithm  for  input graph G returns set of nodes (list), which
541              are contained in Max Independent Set found by algorithm.
542
543       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
544              Weighted variation of Maximal Independent Set. It  takes  as  an
545              input  argument not only graph G but also set of weights for all
546              vertices in graph G.
547
548              Note: Read also Maximal Independent  Set  description  for  more
549              info.
550
551       struct::graph::op::VerticesCover G
552              Vertices  cover  is a set of vertices such that each edge of the
553              graph is incident to at  least  one  vertex  of  the  set.  This
554              2-approximation  algorithm  searches for minimum vertices cover,
555              which is a classical optimization problem  in  computer  science
556              and is a typical example of an NP-hard optimization problem that
557              has an approximation algorithm.  For  input  graph  G  algorithm
558              returns  the set of edges (list), which is Vertex Cover found by
559              algorithm.
560
561       struct::graph::op::EdmondsKarp G s t
562              Improved Ford-Fulkerson's algorithm, computing the maximum  flow
563              in given flow network G.
564
565
566              Arguments:
567
568                     Graph Object G (input)
569                            Weighted and directed graph. Each edge should have
570                            set  integer  attribute  considered   as   maximum
571                            throughputs  that  can  be  carried  by  that link
572                            (edge).
573
574                     Node s (input)
575                            The node that is a source for graph G.
576
577                     Node t (input)
578                            The node that is a sink for graph G.
579
580              Result:
581                     Procedure returns the dictionary  containing  throughputs
582                     for  all  edges.  For each key ( the edge between nodes u
583                     and v in the form of list u v ) there is a value that  is
584                     a  throughput for that key. Edges where throughput values
585                     are equal to 0 are not returned ( it is like there was no
586                     link  in the flow network between nodes connected by such
587                     edge).
588
589       The general idea of algorithm is finding the shortest augumenting paths
590       in  graph  G,  as  long  as  they exist, and for each path updating the
591       edge's weights along that path, with maximum possible  throughput.  The
592       final  (maximum)  flow is found when there is no other augumenting path
593       from source to sink.
594
595       Note: Algorithm complexity : O(V*E), where V is the number of nodes and
596       E is the number of edges in graph G.
597
598       struct::graph::op::BusackerGowen G desiredFlow s t
599              Algorithm  finds  solution  for a minimum cost flow problem. So,
600              the goal is to find a flow, whose max value can be  desiredFlow,
601              from source node s to sink node t in given flow network G.  That
602              network except throughputs at edges has also defined a non-nega‐
603              tive  cost on each edge - cost of using that edge when directing
604              flow with that edge ( it can illustrate e.g. fuel usage, time or
605              any other measure dependent on usages ).
606
607
608              Arguments:
609
610                     Graph Object G (input)
611                            Flow  network (directed graph), each edge in graph
612                            should  have  two  integer  attributes:  cost  and
613                            throughput.
614
615                     Integer desiredFlow (input)
616                            Max value of the flow for that network.
617
618                     Node s (input)
619                            The source node for graph G.
620
621                     Node t (input)
622                            The sink node for graph G.
623
624              Result:
625                     Dictionary containing values of used throughputs for each
626                     edge ( key ).  found by algorithm.
627
628              Note: Algorithm complexity : O(V**2*desiredFlow), where V is the
629              number of nodes in graph G.
630
631       struct::graph::op::ShortestsPathsByBFS G s outputFormat
632              Shortest  pathfinding  algorithm using BFS method. In comparison
633              to struct::graph::op::dijkstra it can work with negative weights
634              on  edges.  Of course negative cycles are not allowed. Algorithm
635              is better than dijkstra for sparse graphs, but also there  exist
636              some  pathological  cases (those cases generally don't appear in
637              practise) that make time complexity increase exponentially  with
638              the growth of the number of nodes.
639
640
641              Arguments:
642
643                     Graph Object G (input)
644                            Input graph.
645
646                     Node s (input)
647                            Source  node for which all distances to each other
648                            node in graph G are computed.
649
650              Options and result:
651
652                     distances
653                            When selected outputFormat is distances  -  proce‐
654                            dure   returns   dictionary  containing  distances
655                            between source node s and each other node in graph
656                            G.
657
658                     paths  When  selected  outputFormat  is paths - procedure
659                            returns dictionary containing for each node  v,  a
660                            list of nodes, which is a path between source node
661                            s and node v.
662
663       struct::graph::op::BFS G s ?outputFormat...?
664              Breadth-First Search - algorithm creates the BFS  Tree.   Memory
665              and  time  complexity:  O(V + E), where V is the number of nodes
666              and E is number of edges.
667
668
669              Arguments:
670
671                     Graph Object G (input)
672                            Input graph.
673
674                     Node s (input)
675                            Source node for BFS procedure.
676
677              Options and result:
678
679                     graph  When selected outputFormat is  graph  -  procedure
680                            returns  a  graph structure (struct::graph), which
681                            is equivalent to BFS tree found by algorithm.
682
683                     tree   When selected outputFormat  is  tree  -  procedure
684                            returns  a tree structure (struct::tree), which is
685                            equivalent to BFS tree found by algorithm.
686
687       struct::graph::op::MinimumDiameterSpanningTree G
688              The goal is to find for input graph G, the  spanning  tree  that
689              has the minimum diameter value.
690
691              General  idea  of  algorithm  is to run BFS over all vertices in
692              graph G. If the diameter d of the tree is odd, then we are  sure
693              that  tree given by BFS is minimum (considering diameter value).
694              When, diameter d is even, then optimal  tree  can  have  minimum
695              diameter equal to d or d-1.
696
697              In  that  case, what algorithm does is rebuilding the tree given
698              by BFS, by adding a vertice between root node and  root's  child
699              node  (nodes), such that subtree created with child node as root
700              node is the greatest one (has the greatests height). In the next
701              step  for such rebuilded tree, we run again BFS with new node as
702              root node. If the height of the tree  didn't  changed,  we  have
703              found a better solution.
704
705              For   input  graph  G  algorithm  returns  the  graph  structure
706              (struct::graph) that is a spanning tree  with  minimum  diameter
707              found by algorithm.
708
709       struct::graph::op::MinimumDegreeSpanningTree G
710              Algorithm  finds  for  input graph G, a spanning tree T with the
711              minimum possible degree. That problem is NP-hard,  so  algorithm
712              is an approximation algorithm.
713
714              Let V be the set of nodes for graph G and let W be any subset of
715              V. Lets assume also that OPT is  optimal  solution  and  ALG  is
716              solution found by algorithm for input graph G.
717
718              It  can  be  proven  that solution found with the algorithm must
719              fulfil inequality:
720
721              ((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(n) + 1.
722
723
724              Arguments:
725
726                     Graph Object G (input)
727                            Undirected simple graph.
728
729              Result:
730                     Algorithm returns graph structure, which is equivalent to
731                     spanning tree T found by algorithm.
732
733       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
734              Algorithm finds maximum flow for the flow network represented by
735              graph G. It is based on the blocking-flow finding methods, which
736              give  us different complexities what makes a better fit for dif‐
737              ferent graphs.
738
739
740              Arguments:
741
742                     Graph Object G (input)
743                            Directed graph G representing  the  flow  network.
744                            Each  edge  should  have  attribute throughput set
745                            with integer value.
746
747                     Node s (input)
748                            The source node for the flow network G.
749
750                     Node t (input)
751                            The sink node for the flow network G.
752
753              Options:
754
755                     dinic  Procedure will find maximum flow for flow  network
756                            G          using         Dinic's         algorithm
757                            (struct::graph::op::BlockingFlowByDinic)       for
758                            blocking flow computation.
759
760                     mkm    Procedure  will find maximum flow for flow network
761                            G using Malhotra, Kumar and Maheshwari's algorithm
762                            (struct::graph::op::BlockingFlowByMKM)  for block‐
763                            ing flow computation.
764
765              Result:
766                     Algorithm returns dictionary containing it's  flow  value
767                     for each edge (key) in network G.
768
769       Note:  struct::graph::op::BlockingFlowByDinic gives O(m*n^2) complexity
770       and struct::graph::op::BlockingFlowByMKM gives O(n^3) complexity, where
771       n  is  the number of nodes and m is the number of edges in flow network
772       G.
773
774       struct::graph::op::BlockingFlowByDinic G s t
775              Algorithm for given network G with source s and sink t, finds  a
776              blocking  flow,  which  can be used to obtain a maximum flow for
777              that network G.
778
779
780              Arguments:
781
782                     Graph Object G (input)
783                            Directed graph G representing  the  flow  network.
784                            Each  edge  should  have  attribute throughput set
785                            with integer value.
786
787                     Node s (input)
788                            The source node for the flow network G.
789
790                     Node t (input)
791                            The sink node for the flow network G.
792
793              Result:
794                     Algorithm returns  dictionary  containing  it's  blocking
795                     flow value for each edge (key) in network G.
796
797              Note: Algorithm's complexity is O(n*m), where n is the number of
798              nodes and m is the number of edges in flow network G.
799
800       struct::graph::op::BlockingFlowByMKM G s t
801              Algorithm for given network G with source s and sink t, finds  a
802              blocking  flow,  which  can be used to obtain a maximum flow for
803              that network G.
804
805
806              Arguments:
807
808                     Graph Object G (input)
809                            Directed graph G representing  the  flow  network.
810                            Each  edge  should  have  attribute throughput set
811                            with integer value.
812
813                     Node s (input)
814                            The source node for the flow network G.
815
816                     Node t (input)
817                            The sink node for the flow network G.
818
819              Result:
820                     Algorithm returns  dictionary  containing  it's  blocking
821                     flow value for each edge (key) in network G.
822
823              Note: Algorithm's complexity is O(n^2), where n is the number of
824              nodes in flow network G.
825
826       struct::graph::op::createResidualGraph G f
827              Procedure creates a residual graph (or residual  network  )  for
828              network G and given flow f.
829
830
831              Arguments:
832
833                     Graph Object G (input)
834                            Flow  network  (directed graph where each edge has
835                            set attribute: throughput ).
836
837                     dictionary f (input)
838                            Current flows in flow network G.
839
840              Result:
841                     Procedure returns graph  structure  that  is  a  residual
842                     graph created from input flow network G.
843
844       struct::graph::op::createAugmentingNetwork G f path
845              Procedure  creates  an  augmenting  network for a given residual
846              network G , flow f and augmenting path path.
847
848
849              Arguments:
850
851                     Graph Object G (input)
852                            Residual network (directed graph), where for every
853                            edge  there are set two attributes: throughput and
854                            cost.
855
856                     Dictionary f (input)
857                            Dictionary which contains for  every  edge  (key),
858                            current value of the flow on that edge.
859
860                     List path (input)
861                            Augmenting  path, set of edges (list) for which we
862                            create the network modification.
863
864              Result:
865                     Algorithm returns graph structure containing the modified
866                     augmenting network.
867
868       struct::graph::op::createLevelGraph Gf s
869              For given residual graph Gf procedure finds the level graph.
870
871
872              Arguments:
873
874                     Graph Object Gf (input)
875                            Residual   network,   where  each  edge  has  it's
876                            attribute throughput set with certain value.
877
878                     Node s (input)
879                            The source node for the residual network Gf.
880
881              Result:
882                     Procedure returns a level graph created from input resid‐
883                     ual network.
884
885       struct::graph::op::TSPLocalSearching G C
886              Algorithm  is  a  heuristic  of  local  searching for Travelling
887              Salesman Problem. For some solution of TSP problem, it checks if
888              it's  possible  to  find a better solution. As TSP is well known
889              NP-Complete problem, so algorithm is a  approximation  algorithm
890              (with 2 approximation factor).
891
892
893              Arguments:
894
895                     Graph Object G (input)
896                            Undirected  and  complete  graph  with  attributes
897                            "weight" set on each single edge.
898
899                     List C (input)
900                            A list of edges being Hamiltonian cycle, which  is
901                            solution of TSP Problem for graph G.
902
903              Result:
904                     Algorithm  returns  the best solution for TSP problem, it
905                     was able to find.
906
907              Note: The solution depends on  the  choosing  of  the  beginning
908              cycle  C.  It's  not  true that better cycle assures that better
909              solution will be found, but practise shows that we  should  give
910              starting cycle with as small sum of weights as possible.
911
912       struct::graph::op::TSPLocalSearching3Approx G C
913              Algorithm  is  a  heuristic  of  local  searching for Travelling
914              Salesman Problem. For some solution of TSP problem, it checks if
915              it's  possible  to  find a better solution. As TSP is well known
916              NP-Complete problem, so algorithm is a  approximation  algorithm
917              (with 3 approximation factor).
918
919
920              Arguments:
921
922                     Graph Object G (input)
923                            Undirected  and  complete  graph  with  attributes
924                            "weight" set on each single edge.
925
926                     List C (input)
927                            A list of edges being Hamiltonian cycle, which  is
928                            solution of TSP Problem for graph G.
929
930              Result:
931                     Algorithm  returns  the best solution for TSP problem, it
932                     was able to find.
933
934              Note: In practise 3-approximation algorithm turns out to be  far
935              more effective than 2-approximation, but it gives worser approx‐
936              imation factor. Further  heuristics  of  local  searching  (e.g.
937              4-approximation)   doesn't  give  enough  boost  to  square  the
938              increase of approximation factor, so 2 and 3 approximations  are
939              mainly used.
940
941       struct::graph::op::createSquaredGraph G
942              X-Squared  graph  is a graph with the same set of nodes as input
943              graph G, but a different set of edges. X-Squared graph has  edge
944              (u,v), if and only if, the distance between u and v nodes is not
945              greater than X and u != v.
946
947              Procedure for input graph G, returns its two-squared graph.
948
949              Note: Distances used in choosing new set of edges are  consider‐
950              ing the number of edges, not the sum of weights at edges.
951
952       struct::graph::op::createCompleteGraph G originalEdges
953              For  input graph G procedure adds missing arcs to make it a com‐
954              plete graph. It also holds in variable originalEdges the set  of
955              arcs that graph G possessed before that operation.
956

BACKGROUND THEORY AND TERMS

958   SHORTEST PATH PROBLEM
959       Definition (single-pair shortest path problem):
960              Formally,  given a weighted graph (let V be the set of vertices,
961              and E a set of edges), and one vertice v of V,  find  a  path  P
962              from  v  to  a v' of V so that the sum of weights on edges along
963              the path is minimal among all paths connecting v to v'.
964
965       Generalizations:
966
967              ·      The single-source shortest path problem, in which we have
968                     to  find  shortest  paths  from  a source vertex v to all
969                     other vertices in the graph.
970
971              ·      The single-destination shortest path problem, in which we
972                     have  to  find  shortest  paths  from all vertices in the
973                     graph to a single  destination  vertex  v.  This  can  be
974                     reduced  to  the  single-source  shortest path problem by
975                     reversing the edges in the graph.
976
977              ·      The all-pairs shortest path problem, in which we have  to
978                     find  shortest paths between every pair of vertices v, v'
979                     in the graph.
980
981              Note: The result of Shortest Path problem can be  Shortest  Path
982              tree,  which  is a subgraph of a given (possibly weighted) graph
983              constructed so that the distance between a  selected  root  node
984              and  all  other  nodes is minimal. It is a tree because if there
985              are two paths between the root node and some vertex  v  (i.e.  a
986              cycle),  we  can delete the last edge of the longer path without
987              increasing the distance from the root node to any  node  in  the
988              subgraph.
989
990   TRAVELLING SALESMAN PROBLEM
991       Definition:
992              For  given  edge-weighted  (weights on edges should be positive)
993              graph the goal is to find the cycle that  visits  each  node  in
994              graph exactly once (Hamiltonian cycle).
995
996       Generalizations:
997
998              ·      Metric  TSP - A very natural restriction of the TSP is to
999                     require that the distances between cities form a  metric,
1000                     i.e.,  they satisfy the triangle inequality. That is, for
1001                     any 3 cities A, B and C, the distance  between  A  and  C
1002                     must  be  at  most the distance from A to B plus the dis‐
1003                     tance from B to C. Most natural instances of TSP  satisfy
1004                     this constraint.
1005
1006              ·      Euclidean  TSP - Euclidean TSP, or planar TSP, is the TSP
1007                     with the distance being the ordinary Euclidean  distance.
1008                     Euclidean  TSP  is a particular case of TSP with triangle
1009                     inequality,  since  distances  in  plane  obey   triangle
1010                     inequality.  However,  it seems to be easier than general
1011                     TSP with triangle inequality. For  example,  the  minimum
1012                     spanning tree of the graph associated with an instance of
1013                     Euclidean TSP is a Euclidean minimum spanning  tree,  and
1014                     so  can  be  computed  in  expected O(n log n) time for n
1015                     points (considerably less than the number of edges). This
1016                     enables the simple 2-approximation algorithm for TSP with
1017                     triangle inequality above to operate more quickly.
1018
1019              ·      Asymmetric TSP - In most cases, the distance between  two
1020                     nodes  in the TSP network is the same in both directions.
1021                     The case where the distance from A to B is not  equal  to
1022                     the  distance  from  B  to A is called asymmetric TSP.  A
1023                     practical application of an asymmetric TSP is route opti‐
1024                     misation  using  street-level  routing (asymmetric due to
1025                     one-way streets, slip-roads and motorways).
1026
1027   MATCHING PROBLEM
1028       Definition:
1029              Given a graph G = (V,E), a matching or edge-independent set M in
1030              G is a set of pairwise non-adjacent edges, that is, no two edges
1031              share a common vertex. A vertex is matched if it is incident  to
1032              an edge in the matching M.  Otherwise the vertex is unmatched.
1033
1034       Generalizations:
1035
1036              ·      Maximal  matching  -  a  matching M of a graph G with the
1037                     property that if any edge not in M is added to M,  it  is
1038                     no  longer a matching, that is, M is maximal if it is not
1039                     a proper subset of any other matching  in  graph  G.   In
1040                     other  words,  a  matching  M  of a graph G is maximal if
1041                     every edge in G has  a  non-empty  intersection  with  at
1042                     least one edge in M.
1043
1044              ·      Maximum  matching  - a matching that contains the largest
1045                     possible number of  edges.  There  may  be  many  maximum
1046                     matchings.   The matching number of a graph G is the size
1047                     of a maximum matching. Note that every  maximum  matching
1048                     is  maximal,  but not every maximal matching is a maximum
1049                     matching.
1050
1051              ·      Perfect matching - a matching which matches all  vertices
1052                     of the graph. That is, every vertex of the graph is inci‐
1053                     dent to exactly one edge of the matching.  Every  perfect
1054                     matching  is  maximum  and hence maximal. In some litera‐
1055                     ture, the term  complete  matching  is  used.  A  perfect
1056                     matching is also a minimum-size edge cover. Moreover, the
1057                     size of a maximum matching is no larger than the size  of
1058                     a minimum edge cover.
1059
1060              ·      Near-perfect  matching  - a matching in which exactly one
1061                     vertex is unmatched. This can only occur when  the  graph
1062                     has  an  odd number of vertices, and such a matching must
1063                     be maximum. If, for every vertex in a graph, there  is  a
1064                     near-perfect  matching  that  omits only that vertex, the
1065                     graph is also called factor-critical.
1066
1067       Related terms:
1068
1069              ·      Alternating path - given a  matching  M,  an  alternating
1070                     path is a path in which the edges belong alternatively to
1071                     the matching and not to the matching.
1072
1073              ·      Augmenting path - given a matching M, an augmenting  path
1074                     is  an alternating path that starts from and ends on free
1075                     (unmatched) vertices.
1076
1077   CUT PROBLEMS
1078       Definition:
1079              A cut is a partition of the vertices of a graph  into  two  dis‐
1080              joint  subsets. The cut-set of the cut is the set of edges whose
1081              end points are in different subsets of the partition. Edges  are
1082              said to be crossing the cut if they are in its cut-set.
1083
1084              Formally:
1085
1086              ·      a  cut  C  = (S,T) is a partition of V of a graph G = (V,
1087                     E).
1088
1089              ·      an s-t cut C = (S,T) of a flow network N = (V,  E)  is  a
1090                     cut  of  N such that s is included in S and t is included
1091                     in T, where s and t are the source  and  the  sink  of  N
1092                     respectively.
1093
1094              ·      The  cut-set of a cut C = (S,T) is such set of edges from
1095                     graph G = (V, E) that each edge (u, v)  satisfies  condi‐
1096                     tion that u is included in S and v is included in T.
1097
1098       In  an  unweighted undirected graph, the size or weight of a cut is the
1099       number of edges crossing the cut. In a weighted graph, the same term is
1100       defined by the sum of the weights of the edges crossing the cut.
1101
1102       In a flow network, an s-t cut is a cut that requires the source and the
1103       sink to be in different subsets, and its cut-set only consists of edges
1104       going from the source's side to the sink's side. The capacity of an s-t
1105       cut is defined by the sum of capacity of each edge in the cut-set.
1106
1107       The cut of a graph can sometimes refer to its cut-set  instead  of  the
1108       partition.
1109
1110       Generalizations:
1111
1112              ·      Minimum  cut - A cut is minimum if the size of the cut is
1113                     not larger than the size of any other cut.
1114
1115              ·      Maximum cut - A cut is maximum if the size of the cut  is
1116                     not smaller than the size of any other cut.
1117
1118              ·      Sparsest cut - The Sparsest cut problem is to bipartition
1119                     the vertices so as to minimize the ratio of the number of
1120                     edges across the cut divided by the number of vertices in
1121                     the smaller half of the partition.
1122
1123   K-CENTER PROBLEM
1124       Definitions:
1125
1126              Unweighted K-Center
1127                     For any set S ( which is subset of V ) and  node  v,  let
1128                     the  connect(v,S) be the cost of cheapest edge connecting
1129                     v with any node in S. The goal is to find  such  S,  that
1130                     |S| = k and max_v{connect(v,S)} is possibly small.
1131
1132                     In other words, we can use it i.e. for finding best loca‐
1133                     tions in the city ( nodes of input graph ) for placing  k
1134                     buildings,  such that those buildings will be as close as
1135                     possible to all other locations in town.
1136
1137
1138              Weighted K-Center
1139                     The variation of unweighted k-center problem. Besides the
1140                     fact  graph  is  edge-weighted, there are also weights on
1141                     vertices of input graph G. We've got also restriction  W.
1142                     The  goal  is  to choose such set of nodes S ( which is a
1143                     subset of V ), that it's total weight is not greater than
1144                     W and also function: max_v { min_u { cost(u,v) }} has the
1145                     smallest possible worth ( v is a node in V  and  u  is  a
1146                     node in S ).
1147
1148   FLOW PROBLEMS
1149       Definitions:
1150
1151              ·      the maximum flow problem - the goal is to find a feasible
1152                     flow through a single-source,  single-sink  flow  network
1153                     that is maximum.  The maximum flow problem can be seen as
1154                     a special case of more  complex  network  flow  problems,
1155                     such as the circulation problem.  The maximum value of an
1156                     s-t flow is equal to the minimum capacity of an  s-t  cut
1157                     in  the  network, as stated in the max-flow min-cut theo‐
1158                     rem.
1159
1160                     More formally for flow network G = (V,E), where for  each
1161                     edge  (u,  v)  we  have its throuhgput c(u,v) defined. As
1162                     flow F we define set of non-negative  integer  attributes
1163                     f(u,v) assigned to edges, satisfying such conditions:
1164
1165                     [1]    for each edge (u, v) in G such condition should be
1166                            satisfied:      0 <= f(u,v) <= c(u,v)
1167
1168                     [2]    Network G has source node s such that the  flow  F
1169                            is equal to the sum of outcoming flow decreased by
1170                            the sum of incoming flow from that source node s.
1171
1172                     [3]    Network G has sink node t such  that  the  the  -F
1173                            value  is  equal  to  the sum of the incoming flow
1174                            decreased by the sum of outcoming flow  from  that
1175                            sink node t.
1176
1177                     [4]    For each node that is not a source or sink the sum
1178                            of incoming flow and sum of outcoming flow  should
1179                            be equal.
1180
1181              ·      the  minimum  cost flow problem - the goal is finding the
1182                     cheapest possible way of sending a certain amount of flow
1183                     through a flow network.
1184
1185              ·      blocking flow - a blocking flow for a residual network Gf
1186                     we name such flow b in Gf that:
1187
1188                     [1]    Each path from sink to source is the shortest path
1189                            in Gf.
1190
1191                     [2]    Each  shortest  path  in  Gf contains an edge with
1192                            fully used throughput in Gf+b.
1193
1194              ·      residual network - for a flow network G and flow f resid‐
1195                     ual  network  is  built  with those edges, which can send
1196                     larger flow. It contains only those edges, which can send
1197                     flow larger than 0.
1198
1199              ·      level  network - it has the same set of nodes as residual
1200                     graph, but has only those edges (u,v) from Gf  for  which
1201                     such   equality  is  satisfied:  distance(s,u)+1  =  dis‐
1202                     tance(s,v).
1203
1204              ·      augmenting network - it is  a  modification  of  residual
1205                     network  considering the new flow values. Structure stays
1206                     unchanged but values of throughputs and  costs  at  edges
1207                     are different.
1208
1209   APPROXIMATION ALGORITHM
1210       k-approximation algorithm:
1211              Algorithm  is a k-approximation, when for ALG (solution returned
1212              by algorithm) and OPT (optimal  solution),  such  inequality  is
1213              true:
1214
1215              ·      for minimalization problems: ALG/OPT <= k
1216
1217              ·      for maximalization problems: OPT/ALG <= k
1218

REFERENCES

1220       [1]    Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
1221
1222       [2]    Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]
1223
1224       [3]    Kruskal's                                              algorithm
1225              [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
1226
1227       [4]    Prim's  algorithm   [http://en.wikipedia.org/wiki/Prim%27s_algo
1228              rithm]
1229
1230       [5]    Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]
1231
1232       [6]    Strongly                   connected                  components
1233              [http://en.wikipedia.org/wiki/Strongly_connected_components]
1234
1235       [7]    Tarjan's     strongly     connected     components     algorithm
1236              [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_com
1237              ponents_algorithm]
1238
1239       [8]    Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]
1240
1241       [9]    Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]
1242
1243       [10]   Bellman-Ford's algorithm  [http://en.wikipedia.org/wiki/Bellman-
1244              Ford_algorithm]
1245
1246       [11]   Johnson's  algorithm [http://en.wikipedia.org/wiki/Johnson_algo
1247              rithm]
1248
1249       [12]   Floyd-Warshall's algorithm  [http://en.wikipedia.org/wiki/Floyd-
1250              Warshall_algorithm]
1251
1252       [13]   Travelling  Salesman Problem [http://en.wikipedia.org/wiki/Trav
1253              elling_salesman_problem]
1254
1255       [14]   Christofides                                           Algorithm
1256              [http://en.wikipedia.org/wiki/Christofides_algorithm]
1257
1258       [15]   Max Cut [http://en.wikipedia.org/wiki/Maxcut]
1259
1260       [16]   Matching [http://en.wikipedia.org/wiki/Matching]
1261
1262       [17]   Max  Independent Set [http://en.wikipedia.org/wiki/Maximal_inde
1263              pendent_set]
1264
1265       [18]   Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]
1266
1267       [19]   Ford-Fulkerson's  algorithm  [http://en.wikipedia.org/wiki/Ford-
1268              Fulkerson_algorithm]
1269
1270       [20]   Maximum    Flow    problem   [http://en.wikipedia.org/wiki/Maxi
1271              mum_flow_problem]
1272
1273       [21]   Busacker-Gowen's  algorithm  [http://en.wikipedia.org/wiki/Mini
1274              mum_cost_flow_problem]
1275
1276       [22]   Dinic's   algorithm  [http://en.wikipedia.org/wiki/Dinic's_algo‐
1277              rithm]
1278
1279       [23]   K-Center      problem      [http://www.csc.kth.se/~viggo/wwwcom‐
1280              pendium/node128.html]
1281
1282       [24]   BFS [http://en.wikipedia.org/wiki/Breadth-first_search]
1283
1284       [25]   Minimum             Degree             Spanning             Tree
1285              [http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree]
1286
1287       [26]   Approximation algorithm [http://en.wikipedia.org/wiki/Approxima
1288              tion_algorithm]
1289

BUGS, IDEAS, FEEDBACK

1291       This  document,  and the package it describes, will undoubtedly contain
1292       bugs and other problems.  Please report such in the category struct  ::
1293       graph  of  the  Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
1294       Please also report any ideas for enhancements you may have  for  either
1295       package and/or documentation.
1296
1297       When proposing code changes, please provide unified diffs, i.e the out‐
1298       put of diff -u.
1299
1300       Note further that  attachments  are  strongly  preferred  over  inlined
1301       patches.  Attachments  can  be  made  by  going to the Edit form of the
1302       ticket immediately after its creation, and  then  using  the  left-most
1303       button in the secondary navigation bar.
1304

KEYWORDS

1306       adjacency  list,  adjacency  matrix, adjacent, approximation algorithm,
1307       arc, articulation point,  augmenting  network,  augmenting  path,  bfs,
1308       bipartite,  blocking flow, bridge, complete graph, connected component,
1309       cut edge, cut vertex, degree, degree constrained spanning tree,  diame‐
1310       ter,  dijkstra,  distance,  eccentricity,  edge,  flow  network, graph,
1311       heuristic, independent set,  isthmus,  level  graph,  local  searching,
1312       loop,  matching,  max cut, maximum flow, minimal spanning tree, minimum
1313       cost flow, minimum degree  spanning  tree,  minimum  diameter  spanning
1314       tree,  neighbour,  node, radius, residual graph, shortest path, squared
1315       graph, strongly connected  component,  subgraph,  travelling  salesman,
1316       vertex, vertex cover
1317

CATEGORY

1319       Data structures
1320
1322       Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>
1323       Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
1324       Copyright (c) 2009 Michal Antoniewski <antoniewski.m@gmail.com>
1325
1326
1327
1328
1329tcllib                              0.11.3                struct::graph::op(n)
Impressum