Install Now
struct::graph::op - Operation for (un)directed graph objects
Contents
Background Theory And Terms
SHORTESTPATHPROBLEM
Definition (single-pairshortestpathproblem):
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:
• Thesingle-sourceshortestpathproblem, in which we have to find shortest paths from a
source vertex v to all other vertices in the graph.
• Thesingle-destinationshortestpathproblem, 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.
• Theall-pairsshortestpathproblem, in which we have to find shortest paths between every
pair of vertices v, v' in the graph.
Note: The result of ShortestPathproblem can be ShortestPathtree, 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.
TRAVELLINGSALESMANPROBLEM
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 (Hamiltoniancycle).
Generalizations:
• MetricTSP - A very natural restriction of the TSP is to require that the distances between
cities form a metric, i.e., they satisfy thetriangleinequality. 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.
• EuclideanTSP - Euclidean TSP, or planarTSP, is the TSP with the distance being the
ordinary Euclideandistance. EuclideanTSP is a particular case of TSP with triangleinequality, since distances in plane obey triangle inequality. However, it seems to be
easier than general TSP with triangleinequality. For example, theminimumspanningtree of
the graph associated with an instance of EuclideanTSP is a Euclideanminimumspanningtree, and so can be computed in expected O(nlogn) time for n points (considerably less
than the number of edges). This enables the simple 2-approximationalgorithm for TSP with
triangle inequality above to operate more quickly.
• AsymmetricTSP - 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 asymmetricTSP. A practical application of an asymmetricTSP is route optimisation using street-level routing (asymmetric due to one-way streets,
slip-roads and motorways).
MATCHINGPROBLEM
Definition:
Given a graph G=(V,E), a matching or edge-independentsetM 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 matchingM. Otherwise the vertex is unmatched.
Generalizations:
• Maximalmatching - 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 matchingM of a graph G is maximal if
every edge in G has a non-empty intersection with at least one edge in M.
• Maximummatching - a matching that contains the largest possible number of edges. There may
be many maximummatchings. The matchingnumber of a graph G is the size of a maximummatching. Note that every maximummatching is maximal, but not every maximalmatching is a
maximummatching.
• Perfectmatching - 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 perfectmatching
is maximum and hence maximal. In some literature, the term completematching is used. A
perfectmatching is also a minimum-sizeedgecover. Moreover, the size of a maximummatching is no larger than the size of a minimumedgecover.
• Near-perfectmatching - 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:
• Alternatingpath - given a matching M, an alternatingpath is a path in which the edges
belong alternatively to the matching and not to the matching.
• Augmentingpath - given a matching M, an augmentingpath is an alternatingpath that starts
from and ends on free (unmatched) vertices.
CUTPROBLEMS
Definition:
A cut is a partition of the vertices of a graph into two disjointsubsets. 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 cutC=(S,T) is a partition of V of a graph G=(V,E).
• an s-tcutC=(S,T) of a flownetworkN=(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 cutC=(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 unweightedundirected graph, the size or weight of a cut is the number of edges crossing the cut.
In a weightedgraph, the same term is defined by the sum of the weights of the edges crossing the cut.
In a flownetwork, an s-tcut 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-tcut 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:
• Minimumcut - A cut is minimum if the size of the cut is not larger than the size of any
other cut.
• Maximumcut - A cut is maximum if the size of the cut is not smaller than the size of any
other cut.
• Sparsestcut - The Sparsestcutproblem 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-CENTERPROBLEM
Definitions:
UnweightedK-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.
WeightedK-Center
The variation of unweightedk-centerproblem. 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 ).
FLOWPROBLEMS
Definitions:
• themaximumflowproblem - the goal is to find a feasible flow through a single-source,
single-sink flow network that is maximum. The maximumflowproblem can be seen as a
special case of more complex network flow problems, such as the circulationproblem. The
maximum value of an s-tflow is equal to the minimum capacity of an s-tcut in the network,
as stated in the max-flowmin-cuttheorem.
More formally for flow network G=(V,E), where for each edge (u,v) we have its throuhgput
c(u,v) defined. As flowF 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.
• theminimumcostflowproblem - the goal is finding the cheapest possible way of sending a
certain amount of flow through a flownetwork.
• blockingflow - a blockingflow for a residualnetworkGf 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.
• residualnetwork - for a flow network G and flow fresidualnetwork is built with those
edges, which can send larger flow. It contains only those edges, which can send flow larger
than 0.
• levelnetwork - it has the same set of nodes as residualgraph, but has only those edges
(u,v) from Gf for which such equality is satisfied: distance(s,u)+1=distance(s,v).
• augmentingnetwork - it is a modification of residualnetwork considering the new flow
values. Structure stays unchanged but values of throughputs and costs at edges are
different.
APPROXIMATIONALGORITHM
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<=kBugs, 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 TcllibTrackers
[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 unifieddiffs, 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.
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>
tcllib 0.11.4 struct::graph::op(3tcl)
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.
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
Name
struct::graph::op - Operation for (un)directed graph objects
Operations
struct::graph::op::toAdjacencyMatrixg
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::toAdjacencyListG ?options...?
Procedure creates for input graph G, it's representation as AdjacencyList. 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 AdjacencyList.
Options:
-directed
By default G is operated as if it were an Undirectedgraph. 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::kruskalg
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*logE) or O(E*logV),
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::primg
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*logV) 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::tarjang
This command computes the set of stronglyconnected 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
stronglyconnected if the result contains only a single SCC containing all nodes of g.
struct::graph::op::connectedComponentsg
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::connectedComponentOfgn
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?gn
This command determines whether the node n in the graph g is a cutvertex (aka articulationpoint). 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?ga
This command determines whether the arc a in the graph g is a bridge (aka cutedge, 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::dijkstragstart ?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::distancegorigindestination ?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::eccentricitygn ?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::radiusg ?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::diameterg ?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::BellmanFordGstartnode
Searching for shortestspaths 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::JohnsonsG ?options...?
Searching for shortestpaths 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::FloydWarshallG
Searching for shortestpaths 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::MetricTravellingSalesmanG
Algorithm for solving a metric variation of Travellingsalesmanproblem. TSPproblem 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 HamiltonCycle - closed path visiting all nodes, each
exactly one time.
Note:It's2-approximationalgorithm.struct::graph::op::ChristofidesG
Another algorithm for solving metricTSPproblem. Christofides implementation uses MaxMatching
for reaching better approximation factor.
Arguments:
Graph Object G (input)
Undirected, weighted graph G.
Result:
Approximated solution of minimum HamiltonCycle - closed path visiting all nodes, each
exactly one time.
Note:It'sisa3/2approximationalgorithm.struct::graph::op::GreedyMaxMatchingGGreedyMaxMatching procedure, which finds maximalmatching (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::MaxCutGUV
Algorithm solving a MaximumCutProblem.
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-approximationalgorithm.struct::graph::op::UnweightedKCenterGk
Approximation algorithm that solves a k-centerproblem.
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-approximationalgorithm.struct::graph::op::WeightedKCenterGnodeWeightsW
Approximation algorithm that solves a weighted version of k-centerproblem.
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-approximationalgorithm.struct::graph::op::GreedyMaxIndependentSetG
A maximalindependentset is an independentset 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::GreedyWeightedMaxIndependentSetGnodeWeights
Weighted variation of MaximalIndependentSet. It takes as an input argument not only graph G but
also set of weights for all vertices in graph G.
Note: Read also MaximalIndependentSet description for more info.
struct::graph::op::VerticesCoverGVerticescover 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 verticescover, 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::EdmondsKarpGst
Improved Ford-Fulkerson's algorithm, computing the maximumflow 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 listuv ) 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::BusackerGowenGdesiredFlowst
Algorithm finds solution for a minimumcostflowproblem. 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::ShortestsPathsByBFSGsoutputFormat
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::BFSGs ?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::MinimumDiameterSpanningTreeG
The goal is to find for input graph G, the spanningtree 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::MinimumDegreeSpanningTreeG
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::MaximumFlowByDinicGstblockingFlowAlg
Algorithm finds maximumflow 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::BlockingFlowByDinicGst
Algorithm for given network G with source s and sink t, finds a blockingflow, which can be used
to obtain a maximumflow 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::BlockingFlowByMKMGst
Algorithm for given network G with source s and sink t, finds a blockingflow, which can be used
to obtain a maximumflow for that networkG.
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::createResidualGraphGf
Procedure creates a residualgraph (or residualnetwork ) 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 residualgraph created from input flow network
G.
struct::graph::op::createAugmentingNetworkGfpath
Procedure creates an augmentingnetwork 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::createLevelGraphGfs
For given residual graph Gf procedure finds the levelgraph.
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 levelgraph created from input residualnetwork.
struct::graph::op::TSPLocalSearchingGC
Algorithm is a heuristicoflocalsearching for TravellingSalesmanProblem. For some solution of
TSPproblem, 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 Hamiltoniancycle, which is solution of TSPProblem for graph
G.
Result:
Algorithm returns the best solution for TSPproblem, 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::TSPLocalSearching3ApproxGC
Algorithm is a heuristicoflocalsearching for TravellingSalesmanProblem. For some solution of
TSPproblem, 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 Hamiltoniancycle, which is solution of TSPProblem for graph
G.
Result:
Algorithm returns the best solution for TSPproblem, 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::createSquaredGraphG
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::createCompleteGraphGoriginalEdges
For input graph G procedure adds missing arcs to make it a completegraph. It also holds in
variable originalEdges the set of arcs that graph G possessed before that operation.
References
[1] Adjacencymatrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
[2] Adjacencylist [http://en.wikipedia.org/wiki/Adjacency_list]
[3] Kruskal'salgorithm [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
[4] Prim'salgorithm [http://en.wikipedia.org/wiki/Prim%27s_algorithm]
[5] Bipartitegraph [http://en.wikipedia.org/wiki/Bipartite_graph]
[6] Stronglyconnectedcomponents [http://en.wikipedia.org/wiki/Strongly_connected_components]
[7] Tarjan'sstronglyconnectedcomponentsalgorithm
[http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm]
[8] Cutvertex [http://en.wikipedia.org/wiki/Cut_vertex]
[9] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]
[10] Bellman-Ford'salgorithm [http://en.wikipedia.org/wiki/Bellman-Ford_algorithm]
[11] Johnson'salgorithm [http://en.wikipedia.org/wiki/Johnson_algorithm]
[12] Floyd-Warshall'salgorithm [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm]
[13] TravellingSalesmanProblem [http://en.wikipedia.org/wiki/Travelling_salesman_problem]
[14] ChristofidesAlgorithm [http://en.wikipedia.org/wiki/Christofides_algorithm]
[15] MaxCut [http://en.wikipedia.org/wiki/Maxcut]
[16] Matching [http://en.wikipedia.org/wiki/Matching]
[17] MaxIndependentSet [http://en.wikipedia.org/wiki/Maximal_independent_set]
[18] VertexCover [http://en.wikipedia.org/wiki/Vertex_cover_problem]
[19] Ford-Fulkerson'salgorithm [http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm]
[20] MaximumFlowproblem [http://en.wikipedia.org/wiki/Maximum_flow_problem]
[21] Busacker-Gowen'salgorithm [http://en.wikipedia.org/wiki/Minimum_cost_flow_problem]
[22] Dinic'salgorithm [http://en.wikipedia.org/wiki/Dinic's_algorithm]
[23] K-Centerproblem [http://www.csc.kth.se/~viggo/wwwcompendium/node128.html]
[24] BFS [http://en.wikipedia.org/wiki/Breadth-first_search]
[25] MinimumDegreeSpanningTree [http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree]
[26] Approximationalgorithm [http://en.wikipedia.org/wiki/Approximation_algorithm]
Synopsis
package require Tcl8.69
package require struct::graph::op?0.11.4?struct::graph::op::toAdjacencyMatrixgstruct::graph::op::toAdjacencyListG ?options...?
struct::graph::op::kruskalgstruct::graph::op::primgstruct::graph::op::isBipartite?g ?bipartvar?
struct::graph::op::tarjangstruct::graph::op::connectedComponentsgstruct::graph::op::connectedComponentOfgnstruct::graph::op::isConnected?gstruct::graph::op::isCutVertex?gnstruct::graph::op::isBridge?gastruct::graph::op::isEulerian?g ?tourvar?
struct::graph::op::isSemiEulerian?g ?pathvar?
struct::graph::op::dijkstragstart ?options...?
struct::graph::op::distancegorigindestination ?options...?
struct::graph::op::eccentricitygn ?options...?
struct::graph::op::radiusg ?options...?
struct::graph::op::diameterg ?options...?
struct::graph::op::BellmanFordGstartnodestruct::graph::op::JohnsonsG ?options...?
struct::graph::op::FloydWarshallGstruct::graph::op::MetricTravellingSalesmanGstruct::graph::op::ChristofidesGstruct::graph::op::GreedyMaxMatchingGstruct::graph::op::MaxCutGUVstruct::graph::op::UnweightedKCenterGkstruct::graph::op::WeightedKCenterGnodeWeightsWstruct::graph::op::GreedyMaxIndependentSetGstruct::graph::op::GreedyWeightedMaxIndependentSetGnodeWeightsstruct::graph::op::VerticesCoverGstruct::graph::op::EdmondsKarpGststruct::graph::op::BusackerGowenGdesiredFlowststruct::graph::op::ShortestsPathsByBFSGsoutputFormatstruct::graph::op::BFSGs ?outputFormat...?
struct::graph::op::MinimumDiameterSpanningTreeGstruct::graph::op::MinimumDegreeSpanningTreeGstruct::graph::op::MaximumFlowByDinicGstblockingFlowAlgstruct::graph::op::BlockingFlowByDinicGststruct::graph::op::BlockingFlowByMKMGststruct::graph::op::createResidualGraphGfstruct::graph::op::createAugmentingNetworkGfpathstruct::graph::op::createLevelGraphGfsstruct::graph::op::TSPLocalSearchingGCstruct::graph::op::TSPLocalSearching3ApproxGCstruct::graph::op::createSquaredGraphGstruct::graph::op::createCompleteGraphGoriginalEdges
________________________________________________________________________________________________________________