1. Manuals
  2. Tumbleweed
  3. tcllib
  4. graphops(n)

Scroll to navigation

struct::graph::op(n) Tcl Data Structures struct::graph::op(n) 





NAME


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






SYNOPSIS


package require Tcl 8.6


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



  

  
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.

  

  

  
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.
    

  







  

  







  

  
A graph to convert into an Adjacency List.







  

  







  

  
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.

  

  
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.









  

  
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.

  

  

  
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.

  

  

  
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.

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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

  







  

  
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.

  

  
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.







  

  
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.

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

    

  







  

  







  

  
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.

  

  
The node for which we find all shortest paths to each other node in graph
      G.







  

  
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.



  

  
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(n) +n*m), where n is
        the number of nodes and m is the number of edges in graph
        G.

    

  







  

  







  

  
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.







  

  







  

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







  

  
Dictionary containing distances between all pairs of vertices.







  

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

    

  







  

  







  

  
Directed and weighted graph G.







  

  
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.

  





  

  
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.
    

  







  

  







  

  
Undirected, weighted graph G.







  

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







  

  
Note: It's 2-approximation algorithm.





  

  
Another algorithm for solving metric TSP problem.
      Christofides implementation uses Max Matching for reaching better
      approximation factor.
    

  







  

  







  

  
Undirected, weighted graph G.







  

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






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



  

  
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.
    

  







  

  







  

  
Undirected graph G.







  

  
Set of edges - the max matching for graph G.







  

  
Algorithm solving a Maximum Cut Problem.
    

  







  

  







  

  
The graph to cut.

  

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

  

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







  

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







  

  
Note: MaxCut is a 2-approximation algorithm.





  

  
Approximation algorithm that solves a k-center problem.
    

  







  

  







  

  
Undirected complete graph G, which satisfies triangle inequality.
    

  

  

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







  

  
Set of nodes - k center for graph G.







  

  
Note: UnweightedKCenter is a 2-approximation
      algorithm.





  

  
Approximation algorithm that solves a weighted version of k-center
      problem.
    

  







  

  







  

  
Undirected complete graph G, which satisfies triangle
    inequality.

  

  
Positive integer that sets the maximum possible weight of k-center
      found by algorithm.

  

  
List of nodes and its weights in graph G.







  

  
Set of nodes, which is solution found by algorithm.







  

  
Note:WeightedKCenter is a 3-approximation
    algorithm.





  

  
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.

  

  

  
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.

  

  

  
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.

  

  
Improved Ford-Fulkerson's algorithm, computing the maximum flow in
      given flow network G.
    

  







  

  







  

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

  

  
The node that is a source for graph G.

  

  
The node that is a sink for graph G.







  

  
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.



  

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

  







  

  







  

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

  

  
Max value of the flow for that network.

  

  
The source node for graph G.

  

  
The sink node for graph G.







  

  
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.





  

  
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.
    

  







  

  







  

  
Input graph.

  

  
Source node for which all distances to each other node in graph G
      are computed.







  

  







  

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

  

  
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.









  

  
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.
    

  







  

  







  

  
Input graph.

  

  
Source node for BFS procedure.







  

  







  

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

  

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









  

  
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.

  

  

  
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(n) +
        1.

    

  







  

  







  

  
Undirected simple graph.







  

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







  

  
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.
    

  







  

  







  

  
Directed graph G representing the flow network. Each edge should
      have attribute throughput set with integer value.

  

  
The source node for the flow network G.

  

  
The sink node for the flow network G.







  

  







  

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

  

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







  

  
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.



  

  
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.
    

  







  

  







  

  
Directed graph G representing the flow network. Each edge should
      have attribute throughput set with integer value.

  

  
The source node for the flow network G.

  

  
The sink node for the flow network G.







  

  
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.





  

  
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.
    

  







  

  







  

  
Directed graph G representing the flow network. Each edge should
      have attribute throughput set with integer value.

  

  
The source node for the flow network G.

  

  
The sink node for the flow network G.







  

  
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.





  

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

  







  

  







  

  
Flow network (directed graph where each edge has set attribute:
      throughput ).

  

  
Current flows in flow network G.







  

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







  

  
Procedure creates an augmenting network for a given residual
      network G , flow f and augmenting path path.
    

  







  

  







  

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

  

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

  

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







  

  
Algorithm returns graph structure containing the modified augmenting
      network.







  

  
For given residual graph Gf procedure finds the level graph.
    

  







  

  







  

  
Residual network, where each edge has it's attribute throughput set
      with certain value.

  

  
The source node for the residual network Gf.







  

  
Procedure returns a level graph created from input residual
      network.







  

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

  







  

  







  

  
Undirected and complete graph with attributes "weight" set on
      each single edge.

  

  
A list of edges being Hamiltonian cycle, which is solution of
      TSP Problem for graph G.







  

  
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.





  

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

  







  

  







  

  
Undirected and complete graph with attributes "weight" set on
      each single edge.

  

  
A list of edges being Hamiltonian cycle, which is solution of
      TSP Problem for graph G.







  

  
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.





  

  
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.

  

  

  
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



  

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

  

  






    
  
  • 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



  

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

  

  






    
  
  • 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



  

  
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.

  

  






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






  
  






    
  
  • 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



  

  
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.



  

  






    
  
  • 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



  

  







  

  
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.

    

  

  

  
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



  

  







  
•

  
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



  

  
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 Trackers
    [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for
    enhancements you may have for either package and/or documentation.


When proposing code changes, please provide unified diffs,
    i.e the output of diff -u.


Note further that attachments are strongly preferred over
    inlined patches. Attachments can be made by going to the Edit form of
    the ticket immediately after its creation, and then using the left-most
    button in the secondary navigation bar.






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>








  

    0.11.3
    tcllib