Provided by: tcllib_1.17-dfsg-1_all 
NAME
struct::graph::op - Operation for (un)directed graph objects
SYNOPSIS
package require Tcl 8.4
package require struct::graph::op ?0.11.3?
struct::graph::op::toAdjacencyMatrix g
struct::graph::op::toAdjacencyList G ?options...?
struct::graph::op::kruskal g
struct::graph::op::prim g
struct::graph::op::isBipartite? g ?bipartvar?
struct::graph::op::tarjan g
struct::graph::op::connectedComponents g
struct::graph::op::connectedComponentOf g n
struct::graph::op::isConnected? g
struct::graph::op::isCutVertex? g n
struct::graph::op::isBridge? g a
struct::graph::op::isEulerian? g ?tourvar?
struct::graph::op::isSemiEulerian? g ?pathvar?
struct::graph::op::dijkstra g start ?options...?
struct::graph::op::distance g origin destination ?options...?
struct::graph::op::eccentricity g n ?options...?
struct::graph::op::radius g ?options...?
struct::graph::op::diameter g ?options...?
struct::graph::op::BellmanFord G startnode
struct::graph::op::Johnsons G ?options...?
struct::graph::op::FloydWarshall G
struct::graph::op::MetricTravellingSalesman G
struct::graph::op::Christofides G
struct::graph::op::GreedyMaxMatching G
struct::graph::op::MaxCut G U V
struct::graph::op::UnweightedKCenter G k
struct::graph::op::WeightedKCenter G nodeWeights W
struct::graph::op::GreedyMaxIndependentSet G
struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
struct::graph::op::VerticesCover G
struct::graph::op::EdmondsKarp G s t
struct::graph::op::BusackerGowen G desiredFlow s t
struct::graph::op::ShortestsPathsByBFS G s outputFormat
struct::graph::op::BFS G s ?outputFormat...?
struct::graph::op::MinimumDiameterSpanningTree G
struct::graph::op::MinimumDegreeSpanningTree G
struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
struct::graph::op::BlockingFlowByDinic G s t
struct::graph::op::BlockingFlowByMKM G s t
struct::graph::op::createResidualGraph G f
struct::graph::op::createAugmentingNetwork G f path
struct::graph::op::createLevelGraph Gf s
struct::graph::op::TSPLocalSearching G C
struct::graph::op::TSPLocalSearching3Approx G C
struct::graph::op::createSquaredGraph G
struct::graph::op::createCompleteGraph G originalEdges
_________________________________________________________________________________________________
DESCRIPTION
The package described by this document, struct::graph::op, is a companion to the package
struct::graph. It provides a series of common operations and algorithms applicable to
(un)directed graphs.
Despite being a companion the package is not directly dependent on struct::graph, only on
the API defined by that package. I.e. the operations of this package can be applied to any
and all graph objects which provide the same API as the objects created through
struct::graph.
OPERATIONS
struct::graph::op::toAdjacencyMatrix g
This command takes the graph g and returns a nested list containing the adjacency
matrix of g.
The elements of the outer list are the rows of the matrix, the inner elements are
the column values in each row. The matrix has "n+1" rows and columns, with the
first row and column (index 0) containing the name of the node the row/column is
for. All other elements are boolean values, True if there is an arc between the 2
nodes of the respective row and column, and False otherwise.
Note that the matrix is symmetric. It does not represent the directionality of
arcs, only their presence between nodes. It is also unable to represent parallel
arcs in g.
struct::graph::op::toAdjacencyList G ?options...?
Procedure creates for input graph G, it's representation as Adjacency List. It
handles both directed and undirected graphs (default is undirected). It returns
dictionary that for each node (key) returns list of nodes adjacent to it. When
considering weighted version, for each adjacent node there is also weight of the
edge included.
Arguments:
Graph object G (input)
A graph to convert into an Adjacency List.
Options:
-directed
By default G is operated as if it were an Undirected graph. Using
this option tells the command to handle G as the directed graph it
is.
-weights
By default any weight information the graph G may have is ignored.
Using this option tells the command to put weight information into
the result. In that case it is expected that all arcs have a proper
weight, and an error is thrown if that is not the case.
struct::graph::op::kruskal g
This command takes the graph g and returns a list containing the names of the arcs
in g which span up a minimum weight spanning tree (MST), or, in the case of an un-
connected graph, a minimum weight spanning forest (except for the 1-vertex
components). Kruskal's algorithm is used to compute the tree or forest. This
algorithm has a time complexity of O(E*log E) or O(E* log V), where V is the number
of vertices and E is the number of edges in graph g.
The command will throw an error if one or more arcs in g have no weight associated
with them.
A note regarding the result, the command refrains from explicitly listing the nodes
of the MST as this information is implicitly provided in the arcs already.
struct::graph::op::prim g
This command takes the graph g and returns a list containing the names of the arcs
in g which span up a minimum weight spanning tree (MST), or, in the case of an un-
connected graph, a minimum weight spanning forest (except for the 1-vertex
components). Prim's algorithm is used to compute the tree or forest. This
algorithm has a time complexity between O(E+V*log V) and O(V*V), depending on the
implementation (Fibonacci heap + Adjacency list versus Adjacency Matrix). As usual
V is the number of vertices and E the number of edges in graph g.
The command will throw an error if one or more arcs in g have no weight associated
with them.
A note regarding the result, the command refrains from explicitly listing the nodes
of the MST as this information is implicitly provided in the arcs already.
struct::graph::op::isBipartite? g ?bipartvar?
This command takes the graph g and returns a boolean value indicating whether it is
bipartite (true) or not (false). If the variable bipartvar is specified the two
partitions of the graph are there as a list, if, and only if the graph is bipartit.
If it is not the variable, if specified, is not touched.
struct::graph::op::tarjan g
This command computes the set of strongly connected components (SCCs) of the graph
g. The result of the command is a list of sets, each of which contains the nodes
for one of the SCCs of g. The union of all SCCs covers the whole graph, and no two
SCCs intersect with each other.
The graph g is acyclic if all SCCs in the result contain only a single node. The
graph g is strongly connected if the result contains only a single SCC containing
all nodes of g.
struct::graph::op::connectedComponents g
This command computes the set of connected components (CCs) of the graph g. The
result of the command is a list of sets, each of which contains the nodes for one
of the CCs of g. The union of all CCs covers the whole graph, and no two CCs
intersect with each other.
The graph g is connected if the result contains only a single SCC containing all
nodes of g.
struct::graph::op::connectedComponentOf g n
This command computes the connected component (CC) of the graph g containing the
node n. The result of the command is a sets which contains the nodes for the CC of
n in g.
The command will throw an error if n is not a node of the graph g.
struct::graph::op::isConnected? g
This is a convenience command determining whether the graph g is connected or not.
The result is a boolean value, true if the graph is connected, and false otherwise.
struct::graph::op::isCutVertex? g n
This command determines whether the node n in the graph g is a cut vertex (aka
articulation point). The result is a boolean value, true if the node is a cut
vertex, and false otherwise.
The command will throw an error if n is not a node of the graph g.
struct::graph::op::isBridge? g a
This command determines whether the arc a in the graph g is a bridge (aka cut edge,
or isthmus). The result is a boolean value, true if the arc is a bridge, and false
otherwise.
The command will throw an error if a is not an arc of the graph g.
struct::graph::op::isEulerian? g ?tourvar?
This command determines whether the graph g is eulerian or not. The result is a
boolean value, true if the graph is eulerian, and false otherwise.
If the graph is eulerian and tourvar is specified then an euler tour is computed as
well and stored in the named variable. The tour is represented by the list of arcs
traversed, in the order of traversal.
struct::graph::op::isSemiEulerian? g ?pathvar?
This command determines whether the graph g is semi-eulerian or not. The result is
a boolean value, true if the graph is semi-eulerian, and false otherwise.
If the graph is semi-eulerian and pathvar is specified then an euler path is
computed as well and stored in the named variable. The path is represented by the
list of arcs traversed, in the order of traversal.
struct::graph::op::dijkstra g start ?options...?
This command determines distances in the weighted g from the node start to all
other nodes in the graph. The options specify how to traverse graphs, and the
format of the result.
Two options are recognized
-arcmode mode
The accepted mode values are directed and undirected. For directed
traversal all arcs are traversed from source to target. For undirected
traversal all arcs are traversed in the opposite direction as well.
Undirected traversal is the default.
-outputformat format
The accepted format values are distances and tree. In both cases the result
is a dictionary keyed by the names of all nodes in the graph. For distances
the value is the distance of the node to start, whereas for tree the value
is the path from the node to start, excluding the node itself, but including
start. Tree format is the default.
struct::graph::op::distance g origin destination ?options...?
This command determines the (un)directed distance between the two nodes origin and
destination in the graph g. It accepts the option -arcmode of
struct::graph::op::dijkstra.
struct::graph::op::eccentricity g n ?options...?
This command determines the (un)directed eccentricity of the node n in the graph g.
It accepts the option -arcmode of struct::graph::op::dijkstra.
The (un)directed eccentricity of a node is the maximal (un)directed distance
between the node and any other node in the graph.
struct::graph::op::radius g ?options...?
This command determines the (un)directed radius of the graph g. It accepts the
option -arcmode of struct::graph::op::dijkstra.
The (un)directed radius of a graph is the minimal (un)directed eccentricity of all
nodes in the graph.
struct::graph::op::diameter g ?options...?
This command determines the (un)directed diameter of the graph g. It accepts the
option -arcmode of struct::graph::op::dijkstra.
The (un)directed diameter of a graph is the maximal (un)directed eccentricity of
all nodes in the graph.
struct::graph::op::BellmanFord G startnode
Searching for shortests paths between chosen node and all other nodes in graph G.
Based on relaxation method. In comparison to struct::graph::op::dijkstra it doesn't
need assumption that all weights on edges in input graph G have to be positive.
That generality sets the complexity of algorithm to - O(V*E), where V is the number
of vertices and E is number of edges in graph G.
Arguments:
Graph object G (input)
Directed, connected and edge weighted graph G, without any negative
cycles ( presence of cycles with the negative sum of weight means
that there is no shortest path, since the total weight becomes lower
each time the cycle is traversed ). Negative weights on edges are
allowed.
Node startnode (input)
The node for which we find all shortest paths to each other node in
graph G.
Result:
Dictionary containing for each node (key) distances to each other node in
graph G.
Note: If algorithm finds a negative cycle, it will return error message.
struct::graph::op::Johnsons G ?options...?
Searching for shortest paths between all pairs of vertices in graph. For sparse
graphs asymptotically quicker than struct::graph::op::FloydWarshall algorithm.
Johnson's algorithm uses struct::graph::op::BellmanFord and
struct::graph::op::dijkstra as subprocedures.
Time complexity: O(n**2*log(3tcl) +n*m), where n is the number of nodes and m is
the number of edges in graph G.
Arguments:
Graph object G (input)
Directed graph G, weighted on edges and not containing any cycles
with negative sum of weights ( the presence of such cycles means
there is no shortest path, since the total weight becomes lower each
time the cycle is traversed ). Negative weights on edges are allowed.
Options:
-filter
Returns only existing distances, cuts all Inf values for non-existing
connections between pairs of nodes.
Result:
Dictionary containing distances between all pairs of vertices.
struct::graph::op::FloydWarshall G
Searching for shortest paths between all pairs of edges in weighted graphs.
Time complexity: O(V^3) - where V is number of vertices.
Memory complexity: O(V^2).
Arguments:
Graph object G (input)
Directed and weighted graph G.
Result:
Dictionary containing shortest distances to each node from each node.
Note: Algorithm finds solutions dynamically. It compares all possible paths through
the graph between each pair of vertices. Graph shouldn't possess any cycle with
negative sum of weights (the presence of such cycles means there is no shortest
path, since the total weight becomes lower each time the cycle is traversed).
On the other hand algorithm can be used to find those cycles - if any shortest
distance found by algorithm for any nodes v and u (when v is the same node as u) is
negative, that node surely belong to at least one negative cycle.
struct::graph::op::MetricTravellingSalesman G
Algorithm for solving a metric variation of Travelling salesman problem. TSP
problem is NP-Complete, so there is no efficient algorithm to solve it. Greedy
methods are getting extremely slow, with the increase in the set of nodes.
Arguments:
Graph object G (input)
Undirected, weighted graph G.
Result:
Approximated solution of minimum Hamilton Cycle - closed path visiting all
nodes, each exactly one time.
Note: It's 2-approximation algorithm.
struct::graph::op::Christofides G
Another algorithm for solving metric TSP problem. Christofides implementation uses
Max Matching for reaching better approximation factor.
Arguments:
Graph Object G (input)
Undirected, weighted graph G.
Result:
Approximated solution of minimum Hamilton Cycle - closed path visiting all
nodes, each exactly one time.
Note: It's is a 3/2 approximation algorithm.
struct::graph::op::GreedyMaxMatching G
Greedy Max Matching procedure, which finds maximal matching (not maximum) for given
graph G. It adds edges to solution, beginning from edges with the lowest cost.
Arguments:
Graph Object G (input)
Undirected graph G.
Result:
Set of edges - the max matching for graph G.
struct::graph::op::MaxCut G U V
Algorithm solving a Maximum Cut Problem.
Arguments:
Graph Object G (input)
The graph to cut.
List U (output)
Variable storing first set of nodes (cut) given by solution.
List V (output)
Variable storing second set of nodes (cut) given by solution.
Result:
Algorithm returns number of edges between found two sets of nodes.
Note: MaxCut is a 2-approximation algorithm.
struct::graph::op::UnweightedKCenter G k
Approximation algorithm that solves a k-center problem.
Arguments:
Graph Object G (input)
Undirected complete graph G, which satisfies triangle inequality.
Integer k (input)
Positive integer that sets the number of nodes that will be included
in k-center.
Result:
Set of nodes - k center for graph G.
Note: UnweightedKCenter is a 2-approximation algorithm.
struct::graph::op::WeightedKCenter G nodeWeights W
Approximation algorithm that solves a weighted version of k-center problem.
Arguments:
Graph Object G (input)
Undirected complete graph G, which satisfies triangle inequality.
Integer W (input)
Positive integer that sets the maximum possible weight of k-center
found by algorithm.
List nodeWeights (input)
List of nodes and its weights in graph G.
Result:
Set of nodes, which is solution found by algorithm.
Note:WeightedKCenter is a 3-approximation algorithm.
struct::graph::op::GreedyMaxIndependentSet G
A maximal independent set is an independent set such that adding any other node to
the set forces the set to contain an edge.
Algorithm for input graph G returns set of nodes (list), which are contained in Max
Independent Set found by algorithm.
struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
Weighted variation of Maximal Independent Set. It takes as an input argument not
only graph G but also set of weights for all vertices in graph G.
Note: Read also Maximal Independent Set description for more info.
struct::graph::op::VerticesCover G
Vertices cover is a set of vertices such that each edge of the graph is incident to
at least one vertex of the set. This 2-approximation algorithm searches for minimum
vertices cover, which is a classical optimization problem in computer science and
is a typical example of an NP-hard optimization problem that has an approximation
algorithm. For input graph G algorithm returns the set of edges (list), which is
Vertex Cover found by algorithm.
struct::graph::op::EdmondsKarp G s t
Improved Ford-Fulkerson's algorithm, computing the maximum flow in given flow
network G.
Arguments:
Graph Object G (input)
Weighted and directed graph. Each edge should have set integer
attribute considered as maximum throughputs that can be carried by
that link (edge).
Node s (input)
The node that is a source for graph G.
Node t (input)
The node that is a sink for graph G.
Result:
Procedure returns the dictionary containing throughputs for all edges. For
each key ( the edge between nodes u and v in the form of list u v ) there is
a value that is a throughput for that key. Edges where throughput values are
equal to 0 are not returned ( it is like there was no link in the flow
network between nodes connected by such edge).
The general idea of algorithm is finding the shortest augumenting paths in graph G, as
long as they exist, and for each path updating the edge's weights along that path, with
maximum possible throughput. The final (maximum) flow is found when there is no other
augumenting path from source to sink.
Note: Algorithm complexity : O(V*E), where V is the number of nodes and E is the number of
edges in graph G.
struct::graph::op::BusackerGowen G desiredFlow s t
Algorithm finds solution for a minimum cost flow problem. So, the goal is to find a
flow, whose max value can be desiredFlow, from source node s to sink node t in
given flow network G. That network except throughputs at edges has also defined a
non-negative cost on each edge - cost of using that edge when directing flow with
that edge ( it can illustrate e.g. fuel usage, time or any other measure dependent
on usages ).
Arguments:
Graph Object G (input)
Flow network (directed graph), each edge in graph should have two
integer attributes: cost and throughput.
Integer desiredFlow (input)
Max value of the flow for that network.
Node s (input)
The source node for graph G.
Node t (input)
The sink node for graph G.
Result:
Dictionary containing values of used throughputs for each edge ( key ).
found by algorithm.
Note: Algorithm complexity : O(V**2*desiredFlow), where V is the number of nodes in
graph G.
struct::graph::op::ShortestsPathsByBFS G s outputFormat
Shortest pathfinding algorithm using BFS method. In comparison to
struct::graph::op::dijkstra it can work with negative weights on edges. Of course
negative cycles are not allowed. Algorithm is better than dijkstra for sparse
graphs, but also there exist some pathological cases (those cases generally don't
appear in practise) that make time complexity increase exponentially with the
growth of the number of nodes.
Arguments:
Graph Object G (input)
Input graph.
Node s (input)
Source node for which all distances to each other node in graph G are
computed.
Options and result:
distances
When selected outputFormat is distances - procedure returns
dictionary containing distances between source node s and each other
node in graph G.
paths When selected outputFormat is paths - procedure returns dictionary
containing for each node v, a list of nodes, which is a path between
source node s and node v.
struct::graph::op::BFS G s ?outputFormat...?
Breadth-First Search - algorithm creates the BFS Tree. Memory and time complexity:
O(V + E), where V is the number of nodes and E is number of edges.
Arguments:
Graph Object G (input)
Input graph.
Node s (input)
Source node for BFS procedure.
Options and result:
graph When selected outputFormat is graph - procedure returns a graph
structure (struct::graph), which is equivalent to BFS tree found by
algorithm.
tree When selected outputFormat is tree - procedure returns a tree
structure (struct::tree), which is equivalent to BFS tree found by
algorithm.
struct::graph::op::MinimumDiameterSpanningTree G
The goal is to find for input graph G, the spanning tree that has the minimum
diameter value.
General idea of algorithm is to run BFS over all vertices in graph G. If the
diameter d of the tree is odd, then we are sure that tree given by BFS is minimum
(considering diameter value). When, diameter d is even, then optimal tree can have
minimum diameter equal to d or d-1.
In that case, what algorithm does is rebuilding the tree given by BFS, by adding a
vertice between root node and root's child node (nodes), such that subtree created
with child node as root node is the greatest one (has the greatests height). In the
next step for such rebuilded tree, we run again BFS with new node as root node. If
the height of the tree didn't changed, we have found a better solution.
For input graph G algorithm returns the graph structure (struct::graph) that is a
spanning tree with minimum diameter found by algorithm.
struct::graph::op::MinimumDegreeSpanningTree G
Algorithm finds for input graph G, a spanning tree T with the minimum possible
degree. That problem is NP-hard, so algorithm is an approximation algorithm.
Let V be the set of nodes for graph G and let W be any subset of V. Lets assume
also that OPT is optimal solution and ALG is solution found by algorithm for input
graph G.
It can be proven that solution found with the algorithm must fulfil inequality:
((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(3tcl) + 1.
Arguments:
Graph Object G (input)
Undirected simple graph.
Result:
Algorithm returns graph structure, which is equivalent to spanning tree T
found by algorithm.
struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
Algorithm finds maximum flow for the flow network represented by graph G. It is
based on the blocking-flow finding methods, which give us different complexities
what makes a better fit for different graphs.
Arguments:
Graph Object G (input)
Directed graph G representing the flow network. Each edge should have
attribute throughput set with integer value.
Node s (input)
The source node for the flow network G.
Node t (input)
The sink node for the flow network G.
Options:
dinic Procedure will find maximum flow for flow network G using Dinic's
algorithm (struct::graph::op::BlockingFlowByDinic) for blocking flow
computation.
mkm Procedure will find maximum flow for flow network G using Malhotra,
Kumar and Maheshwari's algorithm
(struct::graph::op::BlockingFlowByMKM) for blocking flow computation.
Result:
Algorithm returns dictionary containing it's flow value for each edge (key)
in network G.
Note: struct::graph::op::BlockingFlowByDinic gives O(m*n^2) complexity and
struct::graph::op::BlockingFlowByMKM gives O(n^3) complexity, where n is the number of
nodes and m is the number of edges in flow network G.
struct::graph::op::BlockingFlowByDinic G s t
Algorithm for given network G with source s and sink t, finds a blocking flow,
which can be used to obtain a maximum flow for that network G.
Arguments:
Graph Object G (input)
Directed graph G representing the flow network. Each edge should have
attribute throughput set with integer value.
Node s (input)
The source node for the flow network G.
Node t (input)
The sink node for the flow network G.
Result:
Algorithm returns dictionary containing it's blocking flow value for each
edge (key) in network G.
Note: Algorithm's complexity is O(n*m), where n is the number of nodes and m is the
number of edges in flow network G.
struct::graph::op::BlockingFlowByMKM G s t
Algorithm for given network G with source s and sink t, finds a blocking flow,
which can be used to obtain a maximum flow for that network G.
Arguments:
Graph Object G (input)
Directed graph G representing the flow network. Each edge should have
attribute throughput set with integer value.
Node s (input)
The source node for the flow network G.
Node t (input)
The sink node for the flow network G.
Result:
Algorithm returns dictionary containing it's blocking flow value for each
edge (key) in network G.
Note: Algorithm's complexity is O(n^2), where n is the number of nodes in flow
network G.
struct::graph::op::createResidualGraph G f
Procedure creates a residual graph (or residual network ) for network G and given
flow f.
Arguments:
Graph Object G (input)
Flow network (directed graph where each edge has set attribute:
throughput ).
dictionary f (input)
Current flows in flow network G.
Result:
Procedure returns graph structure that is a residual graph created from
input flow network G.
struct::graph::op::createAugmentingNetwork G f path
Procedure creates an augmenting network for a given residual network G , flow f and
augmenting path path.
Arguments:
Graph Object G (input)
Residual network (directed graph), where for every edge there are set
two attributes: throughput and cost.
Dictionary f (input)
Dictionary which contains for every edge (key), current value of the
flow on that edge.
List path (input)
Augmenting path, set of edges (list) for which we create the network
modification.
Result:
Algorithm returns graph structure containing the modified augmenting
network.
struct::graph::op::createLevelGraph Gf s
For given residual graph Gf procedure finds the level graph.
Arguments:
Graph Object Gf (input)
Residual network, where each edge has it's attribute throughput set
with certain value.
Node s (input)
The source node for the residual network Gf.
Result:
Procedure returns a level graph created from input residual network.
struct::graph::op::TSPLocalSearching G C
Algorithm is a heuristic of local searching for Travelling Salesman Problem. For
some solution of TSP problem, it checks if it's possible to find a better solution.
As TSP is well known NP-Complete problem, so algorithm is a approximation algorithm
(with 2 approximation factor).
Arguments:
Graph Object G (input)
Undirected and complete graph with attributes "weight" set on each
single edge.
List C (input)
A list of edges being Hamiltonian cycle, which is solution of TSP
Problem for graph G.
Result:
Algorithm returns the best solution for TSP problem, it was able to find.
Note: The solution depends on the choosing of the beginning cycle C. It's not true
that better cycle assures that better solution will be found, but practise shows
that we should give starting cycle with as small sum of weights as possible.
struct::graph::op::TSPLocalSearching3Approx G C
Algorithm is a heuristic of local searching for Travelling Salesman Problem. For
some solution of TSP problem, it checks if it's possible to find a better solution.
As TSP is well known NP-Complete problem, so algorithm is a approximation algorithm
(with 3 approximation factor).
Arguments:
Graph Object G (input)
Undirected and complete graph with attributes "weight" set on each
single edge.
List C (input)
A list of edges being Hamiltonian cycle, which is solution of TSP
Problem for graph G.
Result:
Algorithm returns the best solution for TSP problem, it was able to find.
Note: In practise 3-approximation algorithm turns out to be far more effective than
2-approximation, but it gives worser approximation factor. Further heuristics of
local searching (e.g. 4-approximation) doesn't give enough boost to square the
increase of approximation factor, so 2 and 3 approximations are mainly used.
struct::graph::op::createSquaredGraph G
X-Squared graph is a graph with the same set of nodes as input graph G, but a
different set of edges. X-Squared graph has edge (u,v), if and only if, the
distance between u and v nodes is not greater than X and u != v.
Procedure for input graph G, returns its two-squared graph.
Note: Distances used in choosing new set of edges are considering the number of
edges, not the sum of weights at edges.
struct::graph::op::createCompleteGraph G originalEdges
For input graph G procedure adds missing arcs to make it a complete graph. It also
holds in variable originalEdges the set of arcs that graph G possessed before that
operation.
BACKGROUND THEORY AND TERMS
SHORTEST PATH PROBLEM
Definition (single-pair shortest path problem):
Formally, given a weighted graph (let V be the set of vertices, and E a set of
edges), and one vertice v of V, find a path P from v to a v' of V so that the sum
of weights on edges along the path is minimal among all paths connecting v to v'.
Generalizations:
• The single-source shortest path problem, in which we have to find shortest
paths from a source vertex v to all other vertices in the graph.
• The single-destination shortest path problem, in which we have to find
shortest paths from all vertices in the graph to a single destination vertex
v. This can be reduced to the single-source shortest path problem by
reversing the edges in the graph.
• The all-pairs shortest path problem, in which we have to find shortest paths
between every pair of vertices v, v' in the graph.
Note: The result of Shortest Path problem can be Shortest Path tree, which is a
subgraph of a given (possibly weighted) graph constructed so that the distance
between a selected root node and all other nodes is minimal. It is a tree because
if there are two paths between the root node and some vertex v (i.e. a cycle), we
can delete the last edge of the longer path without increasing the distance from
the root node to any node in the subgraph.
TRAVELLING SALESMAN PROBLEM
Definition:
For given edge-weighted (weights on edges should be positive) graph the goal is to
find the cycle that visits each node in graph exactly once (Hamiltonian cycle).
Generalizations:
• Metric TSP - A very natural restriction of the TSP is to require that the
distances between cities form a metric, i.e., they satisfy the triangle
inequality. That is, for any 3 cities A, B and C, the distance between A and
C must be at most the distance from A to B plus the distance from B to C.
Most natural instances of TSP satisfy this constraint.
• Euclidean TSP - Euclidean TSP, or planar TSP, is the TSP with the distance
being the ordinary Euclidean distance. Euclidean TSP is a particular case
of TSP with triangle inequality, since distances in plane obey triangle
inequality. However, it seems to be easier than general TSP with triangle
inequality. For example, the minimum spanning tree of the graph associated
with an instance of Euclidean TSP is a Euclidean minimum spanning tree, and
so can be computed in expected O(n log n) time for n points (considerably
less than the number of edges). This enables the simple 2-approximation
algorithm for TSP with triangle inequality above to operate more quickly.
• Asymmetric TSP - In most cases, the distance between two nodes in the TSP
network is the same in both directions. The case where the distance from A
to B is not equal to the distance from B to A is called asymmetric TSP. A
practical application of an asymmetric TSP is route optimisation using
street-level routing (asymmetric due to one-way streets, slip-roads and
motorways).
MATCHING PROBLEM
Definition:
Given a graph G = (V,E), a matching or edge-independent set M in G is a set of
pairwise non-adjacent edges, that is, no two edges share a common vertex. A vertex
is matched if it is incident to an edge in the matching M. Otherwise the vertex is
unmatched.
Generalizations:
• Maximal matching - a matching M of a graph G with the property that if any
edge not in M is added to M, it is no longer a matching, that is, M is
maximal if it is not a proper subset of any other matching in graph G. In
other words, a matching M of a graph G is maximal if every edge in G has a
non-empty intersection with at least one edge in M.
• Maximum matching - a matching that contains the largest possible number of
edges. There may be many maximum matchings. The matching number of a graph
G is the size of a maximum matching. Note that every maximum matching is
maximal, but not every maximal matching is a maximum matching.
• Perfect matching - a matching which matches all vertices of the graph. That
is, every vertex of the graph is incident to exactly one edge of the
matching. Every perfect matching is maximum and hence maximal. In some
literature, the term complete matching is used. A perfect matching is also a
minimum-size edge cover. Moreover, the size of a maximum matching is no
larger than the size of a minimum edge cover.
• Near-perfect matching - a matching in which exactly one vertex is unmatched.
This can only occur when the graph has an odd number of vertices, and such a
matching must be maximum. If, for every vertex in a graph, there is a near-
perfect matching that omits only that vertex, the graph is also called
factor-critical.
Related terms:
• Alternating path - given a matching M, an alternating path is a path in
which the edges belong alternatively to the matching and not to the
matching.
• Augmenting path - given a matching M, an augmenting path is an alternating
path that starts from and ends on free (unmatched) vertices.
CUT PROBLEMS
Definition:
A cut is a partition of the vertices of a graph into two disjoint subsets. The cut-
set of the cut is the set of edges whose end points are in different subsets of the
partition. Edges are said to be crossing the cut if they are in its cut-set.
Formally:
• a cut C = (S,T) is a partition of V of a graph G = (V, E).
• an s-t cut C = (S,T) of a flow network N = (V, E) is a cut of N such that s
is included in S and t is included in T, where s and t are the source and
the sink of N respectively.
• The cut-set of a cut C = (S,T) is such set of edges from graph G = (V, E)
that each edge (u, v) satisfies condition that u is included in S and v is
included in T.
In an unweighted undirected graph, the size or weight of a cut is the number of edges
crossing the cut. In a weighted graph, the same term is defined by the sum of the weights
of the edges crossing the cut.
In a flow network, an s-t cut is a cut that requires the source and the sink to be in
different subsets, and its cut-set only consists of edges going from the source's side to
the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge
in the cut-set.
The cut of a graph can sometimes refer to its cut-set instead of the partition.
Generalizations:
• Minimum cut - A cut is minimum if the size of the cut is not larger than the
size of any other cut.
• Maximum cut - A cut is maximum if the size of the cut is not smaller than
the size of any other cut.
• Sparsest cut - The Sparsest cut problem is to bipartition the vertices so as
to minimize the ratio of the number of edges across the cut divided by the
number of vertices in the smaller half of the partition.
K-CENTER PROBLEM
Definitions:
Unweighted K-Center
For any set S ( which is subset of V ) and node v, let the connect(v,S) be
the cost of cheapest edge connecting v with any node in S. The goal is to
find such S, that |S| = k and max_v{connect(v,S)} is possibly small.
In other words, we can use it i.e. for finding best locations in the city (
nodes of input graph ) for placing k buildings, such that those buildings
will be as close as possible to all other locations in town.
Weighted K-Center
The variation of unweighted k-center problem. Besides the fact graph is
edge-weighted, there are also weights on vertices of input graph G. We've
got also restriction W. The goal is to choose such set of nodes S ( which is
a subset of V ), that it's total weight is not greater than W and also
function: max_v { min_u { cost(u,v) }} has the smallest possible worth ( v
is a node in V and u is a node in S ).
FLOW PROBLEMS
Definitions:
• the maximum flow problem - the goal is to find a feasible flow through a
single-source, single-sink flow network that is maximum. The maximum flow
problem can be seen as a special case of more complex network flow problems,
such as the circulation problem. The maximum value of an s-t flow is equal
to the minimum capacity of an s-t cut in the network, as stated in the max-
flow min-cut theorem.
More formally for flow network G = (V,E), where for each edge (u, v) we have
its throuhgput c(u,v) defined. As flow F we define set of non-negative
integer attributes f(u,v) assigned to edges, satisfying such conditions:
[1] for each edge (u, v) in G such condition should be satisfied: 0
<= f(u,v) <= c(u,v)
[2] Network G has source node s such that the flow F is equal to the sum
of outcoming flow decreased by the sum of incoming flow from that
source node s.
[3] Network G has sink node t such that the the -F value is equal to the
sum of the incoming flow decreased by the sum of outcoming flow from
that sink node t.
[4] For each node that is not a source or sink the sum of incoming flow
and sum of outcoming flow should be equal.
• the minimum cost flow problem - the goal is finding the cheapest possible
way of sending a certain amount of flow through a flow network.
• blocking flow - a blocking flow for a residual network Gf we name such flow
b in Gf that:
[1] Each path from sink to source is the shortest path in Gf.
[2] Each shortest path in Gf contains an edge with fully used throughput
in Gf+b.
• residual network - for a flow network G and flow f residual network is built
with those edges, which can send larger flow. It contains only those edges,
which can send flow larger than 0.
• level network - it has the same set of nodes as residual graph, but has only
those edges (u,v) from Gf for which such equality is satisfied:
distance(s,u)+1 = distance(s,v).
• augmenting network - it is a modification of residual network considering
the new flow values. Structure stays unchanged but values of throughputs and
costs at edges are different.
APPROXIMATION ALGORITHM
k-approximation algorithm:
Algorithm is a k-approximation, when for ALG (solution returned by algorithm) and
OPT (optimal solution), such inequality is true:
• for minimalization problems: ALG/OPT <= k
• for maximalization problems: OPT/ALG <= k
REFERENCES
[1] Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
[2] Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]
[3] Kruskal's algorithm [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
[4] Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algorithm]
[5] Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]
[6] Strongly connected components
[http://en.wikipedia.org/wiki/Strongly_connected_components]
[7] Tarjan's strongly connected components algorithm
[http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm]
[8] Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]
[9] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]
[10] Bellman-Ford's algorithm [http://en.wikipedia.org/wiki/Bellman-Ford_algorithm]
[11] Johnson's algorithm [http://en.wikipedia.org/wiki/Johnson_algorithm]
[12] Floyd-Warshall's algorithm [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm]
[13] Travelling Salesman Problem
[http://en.wikipedia.org/wiki/Travelling_salesman_problem]
[14] Christofides Algorithm [http://en.wikipedia.org/wiki/Christofides_algorithm]
[15] Max Cut [http://en.wikipedia.org/wiki/Maxcut]
[16] Matching [http://en.wikipedia.org/wiki/Matching]
[17] Max Independent Set [http://en.wikipedia.org/wiki/Maximal_independent_set]
[18] Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]
[19] Ford-Fulkerson's algorithm [http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm]
[20] Maximum Flow problem [http://en.wikipedia.org/wiki/Maximum_flow_problem]
[21] Busacker-Gowen's algorithm [http://en.wikipedia.org/wiki/Minimum_cost_flow_problem]
[22] Dinic's algorithm [http://en.wikipedia.org/wiki/Dinic's_algorithm]
[23] K-Center problem [http://www.csc.kth.se/~viggo/wwwcompendium/node128.html]
[24] BFS [http://en.wikipedia.org/wiki/Breadth-first_search]
[25] Minimum Degree Spanning Tree [http://en.wikipedia.org/wiki/Degree-
constrained_spanning_tree]
[26] Approximation algorithm [http://en.wikipedia.org/wiki/Approximation_algorithm]
BUGS, IDEAS, FEEDBACK
This document, and the package it describes, will undoubtedly contain bugs and other
problems. Please report such in the category struct :: graph of the Tcllib Trackers
[http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for enhancements you
may have for either package and/or documentation.
KEYWORDS
adjacency list, adjacency matrix, adjacent, approximation algorithm, arc, articulation
point, augmenting network, augmenting path, bfs, bipartite, blocking flow, bridge,
complete graph, connected component, cut edge, cut vertex, degree, degree constrained
spanning tree, diameter, dijkstra, distance, eccentricity, edge, flow network, graph,
heuristic, independent set, isthmus, level graph, local searching, loop, matching, max
cut, maximum flow, minimal spanning tree, minimum cost flow, minimum degree spanning tree,
minimum diameter spanning tree, neighbour, node, radius, residual graph, shortest path,
squared graph, strongly connected component, subgraph, travelling salesman, vertex, vertex
cover
CATEGORY
Data structures
COPYRIGHT
Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>
Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
Copyright (c) 2009 Michal Antoniewski <antoniewski.m@gmail.com>