Lines Matching +defs:struct +defs:graph +defs:op +defs:isSemiEulerian
3 # Operations on and algorithms for graph data structures.
6 # Copyright (c) 2008 Andreas Kupries, integration with Tcllib's struct::graph
18 package require struct::disjointset ; # Used by kruskal
19 package require struct::prioqueue ; # Used by kruskal, prim
20 package require struct::queue ; # Used by isBipartite?, connectedComponent(Of)
21 package require struct::stack ; # Used by tarjan
22 package require struct::graph ; # isBridge, isCutVertex
23 package require struct::tree ; # Used by BFS
28 namespace eval ::struct::graph::op {}
34 # graph argument.
46 proc ::struct::graph::op::toAdjacencyMatrix {g} {
50 # Tcl and struct::graph (critcl) may generate different, yet
52 # search is done, or nodes have been added to the graph, or ...
102 # un-directional form of the graph with parallel arcs collapsed.
109 #Procedure creates for graph G, it's representation as Adjacency List.
117 #On the other hand, checking if particular edge exists in graph G takes longer
122 # graph G ( directed or undirected ). Default is undirected.
125 # Adjacency List for graph G, represented by dictionary containing lists of adjacent nodes
132 # -directed - sets graph G to be interpreted as directed graph.
138 proc ::struct::graph::op::toAdjacencyList {G args} {
213 #all other nodes in graph G. Based on relaxation method. In comparison to Dijkstra
219 #Directed graph G, weighted on edges and not containing
225 #dictionary d[u] - distances from start node to each other node in graph G.
230 proc ::struct::graph::op::BellmanFord { G startnode } {
235 #checking if the startnode exists in given graph G
237 return -code error "node \"$startnode\" does not exist in graph \"$G\""
240 #sets of nodes and edges for graph G
270 return -code error "Error. Given graph \"$G\" contains cycle with negative sum of weights."
281 #Searching paths between all pairs of vertices in graph. For rare graphs
286 #Directed graph G, weighted on edges and not containing
300 proc ::struct::graph::op::Johnsons { G args } {
318 #Transformation of graph G - adding one more node connected with
334 #transformed graph no needed longer - deleting added node and edges
337 #setting new weights for edges in graph G
363 #setting back edge weights for graph G
379 #Input: directed weighted graph G
382 #Algorithm finds solutions dynamically. It compares all possible paths through the graph
393 proc ::struct::graph::op::FloydWarshall { G } {
427 return -code error "Error. Given graph \"$G\" contains cycle with negative sum of weights."
436 #Travelling salesman problem is a very popular problem in graph theory, where
437 #we are trying to find minimal Hamilton cycle in weighted complete graph. In other words:
443 #For this algorithm we consider a case when for given graph G, the triangle inequality is
448 #Input: undirected, weighted graph G
455 proc ::struct::graph::op::MetricTravellingSalesman { G } {
457 #checking if graph is connected
459 return -code error "Error. Given graph \"$G\" is not a connected graph."
464 # Extend graph to make it complete.
465 # NOTE: The graph is modified in place.
468 #create minimum spanning tree for graph G
471 #TGraph - spanning tree of graph G
483 # input is a symmetric graph, i.e. u->v and v->u have the same
485 # graph as our input we really have to check the two possible
513 proc ::struct::graph::op::TourWeight {w tour} {
529 #Travelling salesman problem is a very popular problem in graph theory, where
530 #we are trying to find minimal Hamilton cycle in weighted complete graph. In other words:
536 #For this algorithm we consider a case when for given graph G, the triangle inequality is
541 #Christofides is a 3/2 approximation algorithm. For a graph given at input, it returns
547 proc ::struct::graph::op::Christofides { G } {
549 #checking if graph is connected
551 return -code error "Error. Given graph \"$G\" is not a connected graph."
558 #create minimum spanning tree for graph G
561 #setting graph algorithm is working on - spanning tree of graph G
564 set oddTGraph [struct::graph]
572 #create complete graph
589 if { ![struct::set contains $M $e] } {
621 #for given graph G. It adds edges to solution, beginning from edges with the
624 proc ::struct::graph::op::GreedyMaxMatching {G} {
650 #Subprocedure which for given graph G, returns the set of edges
652 proc ::struct::graph::op::sortEdges {G} {
671 #Subprocedure, which for given graph G, returns the dictionary
675 proc ::struct::graph::op::sortGraph {G sortMode} {
710 #Finds Hamilton cycle in given graph G
714 proc ::struct::graph::op::findHamiltonCycle {G originalEdges originalGraph} {
773 #Creating graph from sets of given nodes and edges.
779 #Note that it assumes that graph's edges are properly weighted. That
784 proc ::struct::graph::op::createTGraph {G Edges doubledArcs} {
785 #checking if given set of edges is proper (all edges are in graph G)
788 return -code error "Edge \"$e\" doesn't exist in graph \"$G\". Set the proper set of edges."
792 set TGraph [struct::graph]
820 #It returns graph filled with arcs missing to say that graph is complete.
822 #graph G at beginning, before extending the set of edges.
825 proc ::struct::graph::op::createCompleteGraph {G originalEdges} {
851 #other words, we divide set of nodes for graph G into such 2 sets of nodes U and V,
868 proc ::struct::graph::op::MaxCut {G U V} {
895 proc ::struct::graph::op::cut {G Uvar Vvar param} {
939 proc ::struct::graph::op::lremove {listVariable value} {
946 proc ::struct::graph::op::countEdges {G U V} {
971 #Undirected complete graph G, which satisfies triangle inequality.
980 #of input graph ) for placing k buildings, such that those buildings will be as close
984 #set of nodes - k center for graph G
987 proc ::struct::graph::op::UnweightedKCenter {G k} {
989 #checking if all weights for edges in graph G are set well
999 #variable for holding the graph G(i) in each iteration
1000 set Gi [struct::graph]
1001 #two squared graph G
1002 set GiSQ [struct::graph]
1003 #sorted set of edges for graph G
1006 #initializing both graph variables
1022 #adding edge Ei to graph G(i)
1042 #The variation of unweighted k-center problem. Besides the fact graph is edge-weighted,
1043 #there are also weights on vertices of input graph G. We've got also restriction
1052 proc ::struct::graph::op::WeightedKCenter {G nodeWeights W} {
1054 #checking if all weights for edges in graph G are set well
1065 set Gi [struct::graph]
1066 set GiSQ [struct::graph]
1067 #the set of arcs for graph G sorted with their weights (increasing)
1087 #extending graph G(i)
1090 #extending graph G(i)**2 from G(i-1)**2 using G(i)
1093 #finding maximal independent set (Mi) for graph G(i)**2 found in the
1114 if {[struct::set contains $neighbours $node]} {
1160 #for a given graph G.
1164 proc ::struct::graph::op::GreedyMaxIndependentSet {G} {
1170 if { [struct::set contains $nodes $v] } {
1174 struct::set exclude nodes $neighbour
1186 #not only graph G but also set of weights for all vertices in graph G.
1193 proc ::struct::graph::op::GreedyWeightedMaxIndependentSet {G nodeWeights} {
1202 if { [struct::set contains $nodes $v] } {
1208 struct::set exclude nodes $neighbour
1216 #subprocedure creating from graph G two squared graph
1217 #G^2 - graph in which edge between nodes u and v exists,
1221 proc ::struct::graph::op::createSquaredGraph {G} {
1223 set H [struct::graph]
1247 #previousGsq - graph G(i-1)**2
1248 #currentGi - graph G(i)
1254 proc ::struct::graph::op::extendTwoSquaredGraph {previousGsq currentGi u v} {
1261 #adding new edges to solution graph:
1280 #Vertices cover is a set o vertices such that each edge of the graph is incident to
1289 proc ::struct::graph::op::VerticesCover {G} {
1292 #variable containing sorted (with degree) set of arcs for graph G
1301 #target nodes for each edge in graph G
1316 #for each node in graph G, we add it to the final solution and
1321 if { [struct::set contains $arcs $e] } {
1327 struct::set exclude arcs $n
1339 #The general idea of algorithm is finding augumenting paths in graph G, as long
1345 #graph G - weighted and directed graph. Weights at edges are considered as
1347 #s - the node that is a source for graph G
1348 #t - the node that is a sink for graph G
1359 proc ::struct::graph::op::FordFulkerson {G s t} {
1361 #checking if nodes s and t are in graph G
1363 return -code error "Nodes \"$s\" and \"$t\" should be contained in graph's G set of nodes"
1369 return -code error "The input network doesn't have all attributes set correctly... Please, check again attributes: \"throughput\" for input graph."
1381 #setting the residual graph for the first iteration
1438 #when the current throughput for the graph is updated, we generate new residual graph
1463 #for input graph G and given throughput f residual graph
1466 proc ::struct::graph::op::createResidualGraph {G f} {
1469 set residualG [struct::graph]
1508 #when double arcs in graph G (u->v , v->u)
1528 #graph G - flow network. Graph G has two attributes for each edge:
1545 proc ::struct::graph::op::createAugmentingNetwork {G f path} {
1547 set Gf [struct::graph]
1549 #setting the Gf graph
1616 #graph G - flow network, weights at edges are costs of using particular edge
1619 #node s - the source node for graph G
1620 #node t - the sink node for graph G
1629 proc ::struct::graph::op::BusackerGowen {G desiredFlow s t} {
1631 #checking if nodes s and t are in graph G
1633 return -code error "Nodes \"$s\" and \"$t\" should be contained in graph's G set of nodes"
1643 return -code error "The input network doesn't have all attributes set correctly... Please, check again attributes: \"throughput\" and \"cost\" for input graph."
1647 set Gf [struct::graph]
1742 proc ::struct::graph::op::ShortestsPathsByBFS {G s outputFormat} {
1845 proc ::struct::graph::op::BFS {G s outputFormat} {
1850 graph {
1851 set outputMode graph
1857 return -code error "Unknown output format \"$outputFormat\", expected graph, or tree."
1861 if { $outputMode eq "graph" } {
1862 #graph initializing
1863 set BFSGraph [struct::graph]
1869 set BFSTree [struct::tree]
1894 if { $outputMode eq "graph" } {
1903 if { $outputMode eq "graph" } {
1913 #The goal is to find for input graph G, the spanning tree that
1916 #General idea of algorithm is to run BFS over all vertices in graph
1929 proc ::struct::graph::op::MinimumDiameterSpanningTree {G} {
1932 set best_Tree [struct::graph]
1939 set TGraph [BFS $G $v graph]
1975 set tempGraph [struct::graph]
2001 set newtempGraph [BFS $tempGraph $node graph]
2045 #In graph theory, minimum degree spanning tree (or degree-constrained spanning tree)
2048 #determine whether a particular graph has such a spanning tree for a particular k.
2050 #Algorithm for input undirected graph G finds its spanning tree with the smallest
2056 proc ::struct::graph::op::MinimumDegreeSpanningTree {G} {
2059 set MST [struct::graph]
2128 proc ::struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} {
2170 #1. constructing the level graph from network G
2171 #2. until there are edges in level graph:
2172 # 3. find the path between s and t nodes in level graph
2177 proc ::struct::graph::op::BlockingFlowByDinic {G s t} {
2257 #1. constructing the level graph from network G
2258 #2. until there are edges in level graph:
2265 # 8. delete the v node from level graph
2268 #10. if no other edges left in level graph, return b - found blocking flow
2271 proc ::struct::graph::op::BlockingFlowByMKM {G s t} {
2281 #1. setting the level graph
2385 #delete that node from the graph
2402 #It's creating a level graph from the residual network.
2403 proc ::struct::graph::op::createLevelGraph {Gf s} {
2405 set LevelGraph [struct::graph]
2439 #It computes for graph G and each of his nodes the throughput value -
2446 proc ::struct::graph::op::countThroughputsAtNodes {G s t} {
2482 proc ::struct::graph::op::sendBack {G node b value} {
2507 proc ::struct::graph::op::sendForward {G node b value} {
2532 #It checks for graph G if node given at input has a exceed
2539 proc ::struct::graph::op::findExcess {G node b} {
2563 proc ::struct::graph::op::TSPLocalSearching {G C} {
2567 return -code error "Given cycle has arcs not included in graph G."
2572 set CGraph [struct::graph]
2573 set GCopy [struct::graph]
2664 if { !([struct::graph::op::distance $CPrim $iu $ju] > 0 ) || $param } {
2675 #adding new ones that will assure the graph is still a cycle
2735 proc ::struct::graph::op::copyGraph {G} {
2737 set newGraph [struct::graph]
2752 proc ::struct::graph::op::countCycleWeight {G} {
2766 # This command finds a minimum spanning tree/forest (MST) of the graph
2775 proc ::struct::graph::op::kruskal {g} {
2776 # Check graph argument for proper configuration.
2785 set consider [::struct::prioqueue -dictionary consider]
2786 set forest [::struct::disjointset forest]
2788 # Start with all nodes in the graph each in their partition.
2839 # This command finds a minimum spanning tree/forest (MST) of the graph
2847 proc ::struct::graph::op::prim {g} {
2854 # the whole graph minus unconnected nodes, instead of only the MST
2868 set consider [::struct::prioqueue -dictionary consider]
2947 # This command checks whether the graph argument is bi-partite or not,
2949 # graph, and false otherwise. A variable can be provided to store the
2954 proc ::struct::graph::op::isBipartite? {g {bipartitionvar {}}} {
2975 set pending [struct::queue pending]
2990 # paradox, as that means that the graph is not bi-partite.
3013 # different. This graph is not bi-partite. Kill
3023 # The graph is bi-partite. Kill the transient data structure, and
3052 # graph argument G and its bi-partition as specified through the node
3053 # sets X and Y. As is implied, this method requires that the graph is
3057 proc ::struct::graph::op::maxMatching {g X Y} {
3065 # the graph argument G. The result is a list of node-sets, each set
3068 # only a single node the graph is acyclic.
3070 proc ::struct::graph::op::tarjan {g} {
3088 set pending [::struct::stack pending]
3108 proc ::struct::graph::op::TarjanSub {start counter} {
3112 struct::set subtract all $start
3155 # This command computes the connected components (CCs) of the graph
3160 proc ::struct::graph::op::connectedComponents {g} {
3182 struct::set subtract all $component
3188 # the graph argument G containing the node N. The result is a node-set
3191 proc ::struct::graph::op::connectedComponentOf {g n} {
3194 return -code error "node \"$n\" does not exist in graph \"$g\""
3207 proc ::struct::graph::op::ComponentOf {g start} {
3208 set pending [::struct::queue pending]
3229 # This command determines if the specified arc A in the graph G is a
3234 proc ::struct::graph::op::isBridge? {g arc} {
3236 return -code error "arc \"$arc\" does not exist in graph \"$g\""
3239 # Note: We could avoid the need for a copy of the graph if we were
3242 # future consider the creation of a graph class which represents
3259 set copy [struct::graph BridgeCopy = $g]
3267 # This command determines if the specified node N in the graph G is a
3272 proc ::struct::graph::op::isCutVertex? {g n} {
3274 return -code error "node \"$n\" does not exist in graph \"$g\""
3277 # Note: We could avoid the need for a copy of the graph if we were
3280 # future consider the creation of a graph class which represents
3302 struct::set subtract compBefore $n
3304 set copy [struct::graph CutVertexCopy = $g]
3312 # This command determines if the graph G is connected.
3314 proc ::struct::graph::op::isConnected? {g} {
3321 # This command determines if the specified graph G has an eulerian
3326 # Note that for a graph to be eulerian all nodes have to have an even
3327 # degree, and the graph has to be connected. And if more than two
3328 # nodes have an odd degree the graph is not even semi-eulerian (cannot
3331 proc ::struct::graph::op::isEulerian? {g {eulervar {}} {tourstart {}}} {
3352 # At this point the graph is connected, with all nodes of even
3353 # degree. As per Carl Hierholzer the graph has to have an euler
3373 # This command determines if the specified graph G has an eulerian
3379 # Note that for a graph to be semi-eulerian at most two nodes are
3381 # and the graph has to be connected.
3383 proc ::struct::graph::op::isSemiEulerian? {g {eulervar {}}} {
3404 # At this point the graph is connected, with the node degrees
3428 proc ::struct::graph::op::Fleury {g start eulervar} {
3433 set copy [struct::graph FleuryCopy = $g]
3441 while {![struct::set empty $arcs]} {
3467 struct::set exclude arcs $arc
3479 # the graph G starting at node N. The operation can be configured to
3482 proc ::struct::graph::op::dijkstra {g node args} {
3523 # And the start node has to belong to the graph too, of course.
3525 return -code error "node \"$node\" does not exist in graph \"$g\""
3531 set pending [::struct::prioqueue -dictionary DijkstraQueue]
3608 # find the (un)directed distance between two nodes in the graph G.
3610 proc ::struct::graph::op::distance {g origin destination args} {
3612 return -code error "node \"$origin\" does not exist in graph \"$g\""
3615 return -code error "node \"$destination\" does not exist in graph \"$g\""
3654 # find the (un)directed eccentricity of the node N in the graph G. The
3655 # eccentricity is the maximal distance to any other node in the graph.
3657 proc ::struct::graph::op::eccentricity {g node args} {
3659 return -code error "node \"$node\" does not exist in graph \"$g\""
3696 # the (un)directed radius of the graph G. The radius is the minimal
3697 # eccentricity over all nodes in the graph.
3699 proc ::struct::graph::op::radius {g args} {
3704 # the (un)directed diameter of the graph G. The diameter is the
3705 # maximal eccentricity over all nodes in the graph.
3707 proc ::struct::graph::op::diameter {g args} {
3711 proc ::struct::graph::op::RD {g options} {
3757 proc ::struct::graph::op::Min {first second} {
3765 proc ::struct::graph::op::Max {first second} {
3773 # This method verifies that every arc on the graph has a weight
3775 proc ::struct::graph::op::VerifyWeightsAreOk {g} {
3777 return -code error "Operation invalid for graph with unweighted arcs."
3783 namespace eval ::struct::graph::op {
3787 package provide struct::graph::op 0.11.3