Provided by: tcllib_1.14-dfsg-1_all

**NAME**

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

**SYNOPSIS**

package requireTcl8.4package requirestruct::graph::op?0.11.3?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_________________________________________________________________

**DESCRIPTION**

The package described by this document,struct::graph::op, is a companion to the packagestruct::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 onstruct::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 throughstruct::graph.

**OPERATIONS**

struct::graph::op::toAdjacencyMatrixgThis command takes the graphgand returns a nested list containing the adjacency matrix ofg. 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,Trueif there is an arc between the 2 nodes of the respective row and column, andFalseotherwise. 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 ing.struct::graph::op::toAdjacencyListG?options...? Procedure creates for input graphG, it's representation asAdjacencyList. 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 objectG(input) A graph to convert into anAdjacencyList. Options:-directedBy defaultGis operated as if it were anUndirectedgraph. Using this option tells the command to handleGas the directed graph it is.-weightsBy default any weight information the graphGmay 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::kruskalgThis command takes the graphgand returns a list containing the names of the arcs ingwhich 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 ofO(E*logE)orO(E*logV), whereVis the number of vertices andEis the number of edges in graphg. The command will throw an error if one or more arcs inghave 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::primgThis command takes the graphgand returns a list containing the names of the arcs ingwhich 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 betweenO(E+V*logV)andO(V*V), depending on the implementation (Fibonacci heap + Adjacency list versus Adjacency Matrix). As usualVis the number of vertices andEthe number of edges in graphg. The command will throw an error if one or more arcs inghave 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 graphgand returns a boolean value indicating whether it is bipartite (true) or not (false). If the variablebipartvaris 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::tarjangThis command computes the set ofstronglyconnectedcomponents (SCCs) of the graphg. The result of the command is a list of sets, each of which contains the nodes for one of the SCCs ofg. The union of all SCCs covers the whole graph, and no two SCCs intersect with each other. The graphgisacyclicif all SCCs in the result contain only a single node. The graphgisstronglyconnectedif the result contains only a single SCC containing all nodes ofg.struct::graph::op::connectedComponentsgThis command computes the set ofconnectedcomponents (CCs) of the graphg. The result of the command is a list of sets, each of which contains the nodes for one of the CCs ofg. The union of all CCs covers the whole graph, and no two CCs intersect with each other. The graphgisconnectedif the result contains only a single SCC containing all nodes ofg.struct::graph::op::connectedComponentOfgnThis command computes theconnectedcomponent (CC) of the graphgcontaining the noden. The result of the command is a sets which contains the nodes for the CC ofning. The command will throw an error ifnis not a node of the graphg.struct::graph::op::isConnected?gThis is a convenience command determining whether the graphgisconnectedor not. The result is a boolean value,trueif the graph is connected, andfalseotherwise.struct::graph::op::isCutVertex?gnThis command determines whether the nodenin the graphgis acutvertex(akaarticulationpoint). The result is a boolean value,trueif the node is a cut vertex, andfalseotherwise. The command will throw an error ifnis not a node of the graphg.struct::graph::op::isBridge?gaThis command determines whether the arcain the graphgis abridge(akacutedge, oristhmus). The result is a boolean value,trueif the arc is a bridge, andfalseotherwise. The command will throw an error ifais not an arc of the graphg.struct::graph::op::isEulerian?g?tourvar? This command determines whether the graphgiseulerianor not. The result is a boolean value,trueif the graph is eulerian, andfalseotherwise. If the graph is eulerian andtourvaris 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 graphgissemi-eulerianor not. The result is a boolean value,trueif the graph is semi-eulerian, andfalseotherwise. If the graph is semi-eulerian andpathvaris 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 weightedgfrom the nodestartto all other nodes in the graph. The options specify how to traverse graphs, and the format of the result. Two options are recognized-arcmodemode The accepted mode values aredirectedandundirected. 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.-outputformatformat The accepted format values aredistancesandtree. In both cases the result is a dictionary keyed by the names of all nodes in the graph. Fordistancesthe value is the distance of the node tostart, whereas fortreethe value is the path from the node tostart, excluding the node itself, but includingstart. Tree format is the default.struct::graph::op::distancegorigindestination?options...? This command determines the (un)directed distance between the two nodesoriginanddestinationin the graphg. It accepts the option-arcmodeofstruct::graph::op::dijkstra.struct::graph::op::eccentricitygn?options...? This command determines the (un)directedeccentricityof the nodenin the graphg. It accepts the option-arcmodeofstruct::graph::op::dijkstra. The (un)directedeccentricityof 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)directedradiusof the graphg. It accepts the option-arcmodeofstruct::graph::op::dijkstra. The (un)directedradiusof a graph is the minimal (un)directedeccentricityof all nodes in the graph.struct::graph::op::diameterg?options...? This command determines the (un)directeddiameterof the graphg. It accepts the option-arcmodeofstruct::graph::op::dijkstra. The (un)directeddiameterof a graph is the maximal (un)directedeccentricityof all nodes in the graph.struct::graph::op::BellmanFordGstartnodeSearching forshortestspathsbetween chosen node and all other nodes in graphG. Based on relaxation method. In comparison tostruct::graph::op::dijkstrait doesn't need assumption that all weights on edges in input graphGhave to be positive. That generality sets the complexity of algorithm to -O(V*E), whereVis the number of vertices andEis number of edges in graphG. Arguments: Graph objectG(input) Directed, connected and edge weighted graphG, 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. Nodestartnode(input) The node for which we find all shortest paths to each other node in graphG. Result: Dictionary containing for each node (key) distances to each other node in graphG.Note:If algorithm finds a negative cycle, it will return error message.struct::graph::op::JohnsonsG?options...? Searching forshortestpathsbetween all pairs of vertices in graph. For sparse graphs asymptotically quicker thanstruct::graph::op::FloydWarshallalgorithm. Johnson's algorithm usesstruct::graph::op::BellmanFordandstruct::graph::op::dijkstraas subprocedures. Time complexity:O(n**2*log(3tcl)+n*m), wherenis the number of nodes andmis the number of edges in graphG. Arguments: Graph objectG(input) Directed graphG, 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:-filterReturns only existing distances, cuts allInfvalues for non-existing connections between pairs of nodes. Result: Dictionary containing distances between all pairs of vertices.struct::graph::op::FloydWarshallGSearching forshortestpathsbetween all pairs of edges in weighted graphs. Time complexity:O(V^3)- whereVis number of vertices. Memory complexity:O(V^2). Arguments: Graph objectG(input) Directed and weighted graphG. 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 nodesvandu(whenvis the same node asu) is negative, that node surely belong to at least one negative cycle.struct::graph::op::MetricTravellingSalesmanGAlgorithm for solving a metric variation ofTravellingsalesmanproblem.TSPproblemisNP-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 objectG(input) Undirected, weighted graphG. Result: Approximated solution of minimumHamiltonCycle- closed path visiting all nodes, each exactly one time.Note:It's2-approximationalgorithm.struct::graph::op::ChristofidesGAnother algorithm for solvingmetricTSPproblem. Christofides implementation usesMaxMatchingfor reaching better approximation factor. Arguments: Graph ObjectG(input) Undirected, weighted graphG. Result: Approximated solution of minimumHamiltonCycle- closed path visiting all nodes, each exactly one time.Note:It'sisa3/2approximationalgorithm.struct::graph::op::GreedyMaxMatchingGGreedyMaxMatchingprocedure, which findsmaximalmatching(not maximum) for given graphG. It adds edges to solution, beginning from edges with the lowest cost. Arguments: Graph ObjectG(input) Undirected graphG. Result: Set of edges - the max matching for graphG.struct::graph::op::MaxCutGUVAlgorithm solving aMaximumCutProblem. Arguments: Graph ObjectG(input) The graph to cut. ListU(output) Variable storing first set of nodes (cut) given by solution. ListV(output) Variable storing second set of nodes (cut) given by solution. Result: Algorithm returns number of edges between found two sets of nodes.Note:MaxCutis a2-approximationalgorithm.struct::graph::op::UnweightedKCenterGkApproximation algorithm that solves ak-centerproblem. Arguments: Graph ObjectG(input) Undirected complete graphG, which satisfies triangle inequality. Integerk(input) Positive integer that sets the number of nodes that will be included ink-center. Result: Set of nodes -kcenter for graphG.Note:UnweightedKCenteris a2-approximationalgorithm.struct::graph::op::WeightedKCenterGnodeWeightsWApproximation algorithm that solves a weighted version ofk-centerproblem. Arguments: Graph ObjectG(input) Undirected complete graphG, which satisfies triangle inequality. IntegerW(input) Positive integer that sets the maximum possible weight ofk-centerfound by algorithm. ListnodeWeights(input) List of nodes and its weights in graphG. Result: Set of nodes, which is solution found by algorithm.Note:WeightedKCenteris a3-approximationalgorithm.struct::graph::op::GreedyMaxIndependentSetGAmaximalindependentsetis anindependentsetsuch that adding any other node to the set forces the set to contain an edge. Algorithm for input graphGreturns set of nodes (list), which are contained in Max Independent Set found by algorithm.struct::graph::op::GreedyWeightedMaxIndependentSetGnodeWeightsWeighted variation ofMaximalIndependentSet. It takes as an input argument not only graphGbut also set of weights for all vertices in graphG.Note:Read alsoMaximalIndependentSetdescription for more info.struct::graph::op::VerticesCoverGVerticescoveris 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 minimumverticescover, which is a classical optimization problem in computer science and is a typical example of anNP-hardoptimization problem that has an approximation algorithm. For input graphGalgorithm returns the set of edges (list), which is Vertex Cover found by algorithm.struct::graph::op::EdmondsKarpGstImproved Ford-Fulkerson's algorithm, computing themaximumflowin given flow networkG. Arguments: Graph ObjectG(input) Weighted and directed graph. Each edge should have set integer attribute considered as maximum throughputs that can be carried by that link (edge). Nodes(input) The node that is a source for graphG. Nodet(input) The node that is a sink for graphG. Result: Procedure returns the dictionary containing throughputs for all edges. For each key ( the edge between nodesuandvin the form oflistuv) 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 graphG, 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), whereVis the number of nodes andEis the number of edges in graphG.struct::graph::op::BusackerGowenGdesiredFlowstAlgorithm finds solution for aminimumcostflowproblem. So, the goal is to find a flow, whose max value can bedesiredFlow, from source nodesto sink nodetin given flow networkG. 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 ObjectG(input) Flow network (directed graph), each edge in graph should have two integer attributes:costandthroughput. IntegerdesiredFlow(input) Max value of the flow for that network. Nodes(input) The source node for graphG. Nodet(input) The sink node for graphG. Result: Dictionary containing values of used throughputs for each edge ( key ). found by algorithm.Note:Algorithm complexity :O(V**2*desiredFlow), whereVis the number of nodes in graphG.struct::graph::op::ShortestsPathsByBFSGsoutputFormatShortest pathfinding algorithm using BFS method. In comparison tostruct::graph::op::dijkstrait 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 ObjectG(input) Input graph. Nodes(input) Source node for which all distances to each other node in graphGare computed. Options and result:distancesWhen selectedoutputFormatisdistances- procedure returns dictionary containing distances between source nodesand each other node in graphG.pathsWhen selectedoutputFormatispaths- procedure returns dictionary containing for each nodev, a list of nodes, which is a path between source nodesand nodev.struct::graph::op::BFSGs?outputFormat...? Breadth-First Search - algorithm creates the BFS Tree. Memory and time complexity:O(V+E), whereVis the number of nodes andEis number of edges. Arguments: Graph ObjectG(input) Input graph. Nodes(input) Source node for BFS procedure. Options and result:graphWhen selectedoutputFormatisgraph- procedure returns a graph structure (struct::graph), which is equivalent to BFS tree found by algorithm.treeWhen selectedoutputFormatistree- procedure returns a tree structure (struct::tree), which is equivalent to BFS tree found by algorithm.struct::graph::op::MinimumDiameterSpanningTreeGThe goal is to find for input graphG, thespanningtreethat has the minimumdiametervalue. General idea of algorithm is to runBFSover all vertices in graphG. If the diameterdof the tree is odd, then we are sure that tree given byBFSis minimum (considering diameter value). When, diameterdis even, then optimal tree can have minimumdiameterequal todord-1. In that case, what algorithm does is rebuilding the tree given byBFS, 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 againBFSwith new node as root node. If the height of the tree didn't changed, we have found a better solution. For input graphGalgorithm returns the graph structure (struct::graph) that is a spanning tree with minimum diameter found by algorithm.struct::graph::op::MinimumDegreeSpanningTreeGAlgorithm finds for input graphG, a spanning treeTwith the minimum possible degree. That problem isNP-hard, so algorithm is an approximation algorithm. LetVbe the set of nodes for graphGand letWbe any subset ofV. Lets assume also thatOPTis optimal solution andALGis solution found by algorithm for input graphG. 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 ObjectG(input) Undirected simple graph. Result: Algorithm returns graph structure, which is equivalent to spanning treeTfound by algorithm.struct::graph::op::MaximumFlowByDinicGstblockingFlowAlgAlgorithm findsmaximumflowfor the flow network represented by graphG. It is based on the blocking-flow finding methods, which give us different complexities what makes a better fit for different graphs. Arguments: Graph ObjectG(input) Directed graphGrepresenting the flow network. Each edge should have attributethroughputset with integer value. Nodes(input) The source node for the flow networkG. Nodet(input) The sink node for the flow networkG. Options:dinicProcedure will find maximum flow for flow networkGusing Dinic's algorithm (struct::graph::op::BlockingFlowByDinic) for blocking flow computation.mkmProcedure will find maximum flow for flow networkGusing 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 networkG.Note:struct::graph::op::BlockingFlowByDinicgivesO(m*n^2)complexity andstruct::graph::op::BlockingFlowByMKMgivesO(n^3)complexity, wherenis the number of nodes andmis the number of edges in flow networkG.struct::graph::op::BlockingFlowByDinicGstAlgorithm for given networkGwith sourcesand sinkt, finds ablockingflow, which can be used to obtain amaximumflowfor that networkG. Arguments: Graph ObjectG(input) Directed graphGrepresenting the flow network. Each edge should have attributethroughputset with integer value. Nodes(input) The source node for the flow networkG. Nodet(input) The sink node for the flow networkG. Result: Algorithm returns dictionary containing it's blocking flow value for each edge (key) in networkG.Note:Algorithm's complexity isO(n*m), wherenis the number of nodes andmis the number of edges in flow networkG.struct::graph::op::BlockingFlowByMKMGstAlgorithm for given networkGwith sourcesand sinkt, finds ablockingflow, which can be used to obtain amaximumflowfor thatnetworkG. Arguments: Graph ObjectG(input) Directed graphGrepresenting the flow network. Each edge should have attributethroughputset with integer value. Nodes(input) The source node for the flow networkG. Nodet(input) The sink node for the flow networkG. Result: Algorithm returns dictionary containing it's blocking flow value for each edge (key) in networkG.Note:Algorithm's complexity isO(n^2), wherenis the number of nodes in flow networkG.struct::graph::op::createResidualGraphGfProcedure creates aresidualgraph(orresidualnetwork) for networkGand given flowf. Arguments: Graph ObjectG(input) Flow network (directed graph where each edge has set attribute:throughput). dictionaryf(input) Current flows in flow networkG. Result: Procedure returns graph structure that is aresidualgraphcreated from input flow networkG.struct::graph::op::createAugmentingNetworkGfpathProcedure creates anaugmentingnetworkfor a given residual networkG, flowfand augmenting pathpath. Arguments: Graph ObjectG(input) Residual network (directed graph), where for every edge there are set two attributes: throughput and cost. Dictionaryf(input) Dictionary which contains for every edge (key), current value of the flow on that edge. Listpath(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::createLevelGraphGfsFor given residual graphGfprocedure finds thelevelgraph. Arguments: Graph ObjectGf(input) Residual network, where each edge has it's attributethroughputset with certain value. Nodes(input) The source node for the residual networkGf. Result: Procedure returns alevelgraphcreated from inputresidualnetwork.struct::graph::op::TSPLocalSearchingGCAlgorithm is aheuristicoflocalsearchingforTravellingSalesmanProblem. For some solution ofTSPproblem, it checks if it's possible to find a better solution. AsTSPis well known NP-Complete problem, so algorithm is a approximation algorithm (with 2 approximation factor). Arguments: Graph ObjectG(input) Undirected and complete graph with attributes "weight" set on each single edge. ListC(input) A list of edges beingHamiltoniancycle, which is solution ofTSPProblemfor graphG. Result: Algorithm returns the best solution forTSPproblem, it was able to find.Note:The solution depends on the choosing of the beginning cycleC. 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::TSPLocalSearching3ApproxGCAlgorithm is aheuristicoflocalsearchingforTravellingSalesmanProblem. For some solution ofTSPproblem, it checks if it's possible to find a better solution. AsTSPis well known NP-Complete problem, so algorithm is a approximation algorithm (with 3 approximation factor). Arguments: Graph ObjectG(input) Undirected and complete graph with attributes "weight" set on each single edge. ListC(input) A list of edges beingHamiltoniancycle, which is solution ofTSPProblemfor graphG. Result: Algorithm returns the best solution forTSPproblem, 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::createSquaredGraphGX-Squared graph is a graph with the same set of nodes as input graphG, but a different set of edges. X-Squared graph has edge(u,v), if and only if, the distance betweenuandvnodes is not greater than X andu!=v. Procedure for input graphG, 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::createCompleteGraphGoriginalEdgesFor input graphGprocedure adds missing arcs to make it acompletegraph. It also holds in variableoriginalEdgesthe set of arcs that graphGpossessed before that operation.

**BACKGROUND** **THEORY** **AND** **TERMS**

SHORTESTPATHPROBLEMDefinition (single-pairshortestpathproblem): Formally, given a weighted graph (letVbe the set of vertices, andEa set of edges), and one verticevofV, find a pathPfromvto av'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 ofShortestPathproblemcan beShortestPathtree, 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.TRAVELLINGSALESMANPROBLEMDefinition: 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 theTSPis to require that the distances between cities form ametric, i.e., they satisfythetriangleinequality. That is, for any 3 citiesA,BandC, the distance betweenAandCmust be at most the distance fromAtoBplus the distance fromBtoC. Most natural instances ofTSPsatisfy this constraint. ·EuclideanTSP- Euclidean TSP, orplanarTSP, is theTSPwith the distance being the ordinaryEuclideandistance.EuclideanTSPis a particular case ofTSPwithtriangleinequality, since distances in plane obey triangle inequality. However, it seems to be easier than generalTSPwithtriangleinequality. For example,theminimumspanningtreeof the graph associated with an instance ofEuclideanTSPis aEuclideanminimumspanningtree, and so can be computed in expectedO(nlogn)time fornpoints (considerably less than the number of edges). This enables the simple2-approximationalgorithmfor TSP with triangle inequality above to operate more quickly. ·AsymmetricTSP- In most cases, the distance between two nodes in theTSPnetwork is the same in both directions. The case where the distance fromAtoBis not equal to the distance fromBtoAis calledasymmetricTSP. A practical application of anasymmetricTSPis route optimisation using street-level routing (asymmetric due to one-way streets, slip-roads and motorways).MATCHINGPROBLEMDefinition: Given a graphG=(V,E), a matching oredge-independentsetMinGis a set of pairwise non-adjacent edges, that is, no two edges share a common vertex. A vertex ismatchedif it is incident to an edge in thematchingM. Otherwise the vertex isunmatched. Generalizations: ·Maximalmatching- a matchingMof a graph G with the property that if any edge not inMis added toM, it is no longer amatching, that is,Mis maximal if it is not a proper subset of any othermatchingin graph G. In other words, amatchingMof a graph G is maximal if every edge in G has a non-empty intersection with at least one edge inM. ·Maximummatching- a matching that contains the largest possible number of edges. There may be manymaximummatchings. Thematchingnumberof a graph G is the size of amaximummatching. Note that everymaximummatchingismaximal, but not everymaximalmatchingis amaximummatching. ·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. Everyperfectmatchingismaximumand hencemaximal. In some literature, the termcompletematchingis used. Aperfectmatchingis also aminimum-sizeedgecover. Moreover, the size of amaximummatchingis no larger than the size of aminimumedgecover. ·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 amatchingmust bemaximum. If, for every vertex in a graph, there is a near- perfect matching that omits only that vertex, the graph is also calledfactor-critical. Related terms: ·Alternatingpath- given a matchingM, analternatingpathis a path in which the edges belong alternatively to the matching and not to the matching. ·Augmentingpath- given a matchingM, anaugmentingpathis analternatingpaththat starts from and ends on free (unmatched) vertices.CUTPROBLEMSDefinition: Acutis a partition of the vertices of a graph into twodisjointsubsets. Thecut-setof thecutis 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 itscut-set. Formally: · acutC=(S,T)is a partition ofVof a graphG=(V,E). · ans-tcutC=(S,T)of aflownetworkN=(V,E)is a cut ofNsuch thatsis included inSandtis included inT, wheresandtare thesourceand thesinkofNrespectively. · Thecut-setof acutC=(S,T)is such set of edges from graphG=(V,E)that each edge(u,v)satisfies condition thatuis included inSandvis included inT. In anunweightedundirectedgraph, the size or weight of a cut is the number of edges crossing the cut. In aweightedgraph, the same term is defined by the sum of the weights of the edges crossing the cut. In aflownetwork, ans-tcutis a cut that requires thesourceand thesinkto be in different subsets, and itscut-setonly consists of edges going from thesource'sside to thesink'sside. The capacity of ans-tcutis defined by the sum of capacity of each edge in thecut-set. Thecutof a graph can sometimes refer to itscut-setinstead 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- TheSparsestcutproblemis 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-CENTERPROBLEMDefinitions:UnweightedK-CenterFor any setS( which is subset ofV) and nodev, let theconnect(v,S)be the cost of cheapest edge connectingvwith any node inS. The goal is to find suchS, that|S|=kandmax_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-CenterThe variation ofunweightedk-centerproblem. Besides the fact graph is edge-weighted, there are also weights on vertices of input graphG. We've got also restrictionW. The goal is to choose such set of nodesS( which is a subset ofV), that it's total weight is not greater thanWand also function:max_v{min_u{cost(u,v)}}has the smallest possible worth (vis a node inVanduis a node inS).FLOWPROBLEMSDefinitions: ·themaximumflowproblem- the goal is to find a feasible flow through a single-source, single-sink flow network that is maximum. Themaximumflowproblemcan be seen as a special case of more complex network flow problems, such as thecirculationproblem. The maximum value of ans-tflowis equal to the minimum capacity of ans-tcutin the network, as stated in themax-flowmin-cuttheorem. More formally for flow networkG=(V,E), where for each edge(u,v)we have its throuhgputc(u,v)defined. AsflowFwe define set of non-negative integer attributesf(u,v)assigned to edges, satisfying such conditions: [1] for each edge(u,v)inGsuch condition should be satisfied: 0 <= f(u,v) <= c(u,v) [2] NetworkGhas source nodessuch that the flowFis equal to the sum of outcoming flow decreased by the sum of incoming flow from that source nodes. [3] NetworkGhas sink nodetsuch that the the-Fvalue is equal to the sum of the incoming flow decreased by the sum of outcoming flow from that sink nodet. [4] For each node that is not asourceorsinkthe 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 aflownetwork. ·blockingflow- ablockingflowfor aresidualnetworkGfwe name such flowbinGfthat: [1] Each path fromsinktosourceis the shortest path inGf. [2] Each shortest path inGfcontains an edge with fully used throughput inGf+b. ·residualnetwork- for a flow networkGand flowfresidualnetworkis 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 asresidualgraph, but has only those edges(u,v)fromGffor which such equality is satisfied:distance(s,u)+1=distance(s,v). ·augmentingnetwork- it is a modification ofresidualnetworkconsidering the new flow values. Structure stays unchanged but values of throughputs and costs at edges are different.APPROXIMATIONALGORITHMk-approximation algorithm: Algorithm is a k-approximation, when forALG(solution returned by algorithm) andOPT(optimal solution), such inequality is true: · for minimalization problems:ALG/OPT<=k· for maximalization problems:OPT/ALG<=k

**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]

**BUGS,** **IDEAS,** **FEEDBACK**

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

**KEYWORDS**

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

**CATEGORY**

Data structures

**COPYRIGHT**

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