graphops man page on OpenSuSE

Man page or keyword search:  
man Server   25941 pages
apropos Keyword Search (all sections)
Output format
OpenSuSE logo
[printable version]

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

______________________________________________________________________________

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

SYNOPSIS
       package require Tcl  8.4

       package require struct::graph::op  ?0.11.3?

       struct::graph::op::toAdjacencyMatrix g

       struct::graph::op::toAdjacencyList G ?options...?

       struct::graph::op::kruskal g

       struct::graph::op::prim g

       struct::graph::op::isBipartite? g ?bipartvar?

       struct::graph::op::tarjan g

       struct::graph::op::connectedComponents g

       struct::graph::op::connectedComponentOf g n

       struct::graph::op::isConnected? g

       struct::graph::op::isCutVertex? g n

       struct::graph::op::isBridge? g a

       struct::graph::op::isEulerian? g ?tourvar?

       struct::graph::op::isSemiEulerian? g ?pathvar?

       struct::graph::op::dijkstra g start ?options...?

       struct::graph::op::distance g origin destination ?options...?

       struct::graph::op::eccentricity g n ?options...?

       struct::graph::op::radius g ?options...?

       struct::graph::op::diameter g ?options...?

       struct::graph::op::BellmanFord G startnode

       struct::graph::op::Johnsons G ?options...?

       struct::graph::op::FloydWarshall G

       struct::graph::op::MetricTravellingSalesman G

       struct::graph::op::Christofides G

       struct::graph::op::GreedyMaxMatching G

       struct::graph::op::MaxCut G U V

       struct::graph::op::UnweightedKCenter G k

       struct::graph::op::WeightedKCenter G nodeWeights W

       struct::graph::op::GreedyMaxIndependentSet G

       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights

       struct::graph::op::VerticesCover G

       struct::graph::op::EdmondsKarp G s t

       struct::graph::op::BusackerGowen G desiredFlow s t

       struct::graph::op::ShortestsPathsByBFS G s outputFormat

       struct::graph::op::BFS G s ?outputFormat...?

       struct::graph::op::MinimumDiameterSpanningTree G

       struct::graph::op::MinimumDegreeSpanningTree G

       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg

       struct::graph::op::BlockingFlowByDinic G s t

       struct::graph::op::BlockingFlowByMKM G s t

       struct::graph::op::createResidualGraph G f

       struct::graph::op::createAugmentingNetwork G f path

       struct::graph::op::createLevelGraph Gf s

       struct::graph::op::TSPLocalSearching G C

       struct::graph::op::TSPLocalSearching3Approx G C

       struct::graph::op::createSquaredGraph G

       struct::graph::op::createCompleteGraph G originalEdges

_________________________________________________________________

DESCRIPTION
       The package described by this document, struct::graph::op, is a compan‐
       ion to the package struct::graph. It provides a series of common opera‐
       tions 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 opera‐
       tions of this package can be applied to any and all graph objects which
       provide the same API as the objects created through struct::graph.

OPERATIONS
       struct::graph::op::toAdjacencyMatrix g
	      This command takes the graph g and returns a  nested  list  con‐
	      taining the adjacency matrix of g.

	      The  elements  of the outer list are the rows of the matrix, the
	      inner elements are the column values in each row. The matrix has
	      "n+1"  rows and columns, with the first row and column (index 0)
	      containing the name of the node the row/column is for. All other
	      elements are boolean values, True if there is an arc between the
	      2 nodes of the respective row and column, and False otherwise.

	      Note that the matrix is symmetric. It  does  not	represent  the
	      directionality of arcs, only their presence between nodes. It is
	      also unable to represent parallel arcs in g.

       struct::graph::op::toAdjacencyList G ?options...?
	      Procedure creates for input  graph  G,  it's  representation  as
	      Adjacency	 List.	It handles both directed and undirected graphs
	      (default is undirected).	It returns dictionary  that  for  each
	      node  (key) returns list of nodes adjacent to it. When consider‐
	      ing weighted version, for	 each  adjacent	 node  there  is  also
	      weight of the edge included.

	      Arguments:

		     Graph object G (input)
			    A graph to convert into an Adjacency List.

	      Options:

		     -directed
			    By	default	 G  is operated as if it were an Undi‐
			    rected graph.  Using this option tells the command
			    to handle G as the directed graph it is.

		     -weights
			    By	default any weight information the graph G may
			    have is ignored.  Using this option tells the com‐
			    mand  to  put  weight information into the result.
			    In that case it is expected that all arcs  have  a
			    proper  weight,  and an error is thrown if that is
			    not the case.

       struct::graph::op::kruskal g
	      This command takes the graph g and returns a list containing the
	      names  of	 the arcs in g which span up a minimum weight spanning
	      tree (MST), or, in the case of an un-connected graph, a  minimum
	      weight  spanning	forest	(except	 for the 1-vertex components).
	      Kruskal's algorithm is used to compute the tree or forest.  This
	      algorithm	 has  a	 time complexity of O(E*log E) or O(E* log V),
	      where V is the number of vertices and E is the number  of	 edges
	      in graph g.

	      The command will throw an error if one or more arcs in g have no
	      weight associated with them.

	      A note regarding the result, the command refrains	 from  explic‐
	      itly listing the nodes of the MST as this information is implic‐
	      itly provided in the arcs already.

       struct::graph::op::prim g
	      This command takes the graph g and returns a list containing the
	      names  of	 the arcs in g which span up a minimum weight spanning
	      tree (MST), or, in the case of an un-connected graph, a  minimum
	      weight  spanning	forest	(except	 for the 1-vertex components).
	      Prim's algorithm is used to compute the tree  or	forest.	  This
	      algorithm has a time complexity between O(E+V*log V) and O(V*V),
	      depending on the implementation (Fibonacci heap + Adjacency list
	      versus  Adjacency Matrix).  As usual V is the number of vertices
	      and E the number of edges in graph g.

	      The command will throw an error if one or more arcs in g have no
	      weight associated with them.

	      A	 note  regarding the result, the command refrains from explic‐
	      itly listing the nodes of the MST as this information is implic‐
	      itly provided in the arcs already.

       struct::graph::op::isBipartite? g ?bipartvar?
	      This command takes the graph g and returns a boolean value indi‐
	      cating whether it is bipartite (true) or	not  (false).  If  the
	      variable	bipartvar is specified the two partitions of the graph
	      are there as a list, if, and only if the graph is	 bipartit.  If
	      it is not the variable, if specified, is not touched.

       struct::graph::op::tarjan g
	      This  command  computes the set of strongly connected components
	      (SCCs) of the graph g. The result of the command is  a  list  of
	      sets, each of which contains the nodes for one of the SCCs of g.
	      The union of all SCCs covers the whole graph, and	 no  two  SCCs
	      intersect with each other.

	      The  graph g is acyclic if all SCCs in the result contain only a
	      single node. The graph g is strongly  connected  if  the	result
	      contains only a single SCC containing all nodes of g.

       struct::graph::op::connectedComponents g
	      This  command  computes the set of connected components (CCs) of
	      the graph g. The result of the command is a list of  sets,  each
	      of  which	 contains the nodes for one of the CCs of g. The union
	      of all CCs covers the whole graph, and no two CCs intersect with
	      each other.

	      The  graph  g  is connected if the result contains only a single
	      SCC containing all nodes of g.

       struct::graph::op::connectedComponentOf g n
	      This command computes the connected component (CC) of the	 graph
	      g	 containing  the  node	n. The result of the command is a sets
	      which contains the nodes for the CC of n in g.

	      The command will throw an error if n is not a node of the	 graph
	      g.

       struct::graph::op::isConnected? g
	      This is a convenience command determining whether the graph g is
	      connected or not.	 The result is a boolean value,	 true  if  the
	      graph is connected, and false otherwise.

       struct::graph::op::isCutVertex? g n
	      This  command  determines whether the node n in the graph g is a
	      cut vertex (aka articulation point). The	result	is  a  boolean
	      value, true if the node is a cut vertex, and false otherwise.

	      The  command will throw an error if n is not a node of the graph
	      g.

       struct::graph::op::isBridge? g a
	      This command determines whether the arc a in the graph  g	 is  a
	      bridge  (aka  cut	 edge,	or  isthmus).  The result is a boolean
	      value, true if the arc is a bridge, and false otherwise.

	      The command will throw an error if a is not an arc of the	 graph
	      g.

       struct::graph::op::isEulerian? g ?tourvar?
	      This  command determines whether the graph g is eulerian or not.
	      The result is a boolean value, true if the  graph	 is  eulerian,
	      and false otherwise.

	      If  the graph is eulerian and tourvar is specified then an euler
	      tour is computed as well and stored in the named	variable.  The
	      tour  is represented by the list of arcs traversed, in the order
	      of traversal.

       struct::graph::op::isSemiEulerian? g ?pathvar?
	      This command determines whether the graph g is semi-eulerian  or
	      not.   The result is a boolean value, true if the graph is semi-
	      eulerian, and false otherwise.

	      If the graph is semi-eulerian and pathvar is specified  then  an
	      euler path is computed as well and stored in the named variable.
	      The path is represented by the list of arcs  traversed,  in  the
	      order of traversal.

       struct::graph::op::dijkstra g start ?options...?
	      This  command  determines	 distances  in the weighted g from the
	      node start to all other nodes in the graph. The options  specify
	      how to traverse graphs, and the format of the result.

	      Two options are recognized

	      -arcmode mode
		     The  accepted  mode  values  are directed and undirected.
		     For directed traversal all arcs are traversed from source
		     to	 target.  For  undirected  traversal all arcs are tra‐
		     versed in the opposite direction as well. Undirected tra‐
		     versal is the default.

	      -outputformat format
		     The  accepted  format  values  are distances and tree. In
		     both cases the result is a dictionary keyed by the	 names
		     of all nodes in the graph. For distances the value is the
		     distance of the node to start, whereas for tree the value
		     is	 the  path  from the node to start, excluding the node
		     itself, but including start. Tree format is the default.

       struct::graph::op::distance g origin destination ?options...?
	      This command determines the (un)directed	distance  between  the
	      two  nodes origin and destination in the graph g. It accepts the
	      option -arcmode of struct::graph::op::dijkstra.

       struct::graph::op::eccentricity g n ?options...?
	      This command determines the  (un)directed	 eccentricity  of  the
	      node  n  in  the	graph  g.  It  accepts	the option -arcmode of
	      struct::graph::op::dijkstra.

	      The  (un)directed	 eccentricity  of  a  node  is	 the   maximal
	      (un)directed distance between the node and any other node in the
	      graph.

       struct::graph::op::radius g ?options...?
	      This command determines the (un)directed radius of the graph  g.
	      It accepts the option -arcmode of struct::graph::op::dijkstra.

	      The  (un)directed	 radius of a graph is the minimal (un)directed
	      eccentricity of all nodes in the graph.

       struct::graph::op::diameter g ?options...?
	      This command determines the (un)directed diameter of  the	 graph
	      g.  It  accepts  the option -arcmode of struct::graph::op::dijk‐
	      stra.

	      The (un)directed diameter of a graph is the maximal (un)directed
	      eccentricity of all nodes in the graph.

       struct::graph::op::BellmanFord G startnode
	      Searching	 for shortests paths between chosen node and all other
	      nodes in graph G. Based on relaxation method. In	comparison  to
	      struct::graph::op::dijkstra  it doesn't need assumption that all
	      weights on edges in input graph G have to be positive.

	      That generality sets the complexity of algorithm	to  -  O(V*E),
	      where  V	is  the number of vertices and E is number of edges in
	      graph G.

	      Arguments:

		     Graph object G (input)
			    Directed, connected and  edge  weighted  graph  G,
			    without  any  negative cycles ( presence of cycles
			    with the negative sum of weight means  that	 there
			    is	no  shortest  path,  since  the	 total	weight
			    becomes lower each time the cycle is traversed  ).
			    Negative weights on edges are allowed.

		     Node startnode (input)
			    The	 node  for which we find all shortest paths to
			    each other node in graph G.

	      Result:
		     Dictionary containing for each node  (key)	 distances  to
		     each other node in graph G.

       Note:  If  algorithm  finds a negative cycle, it will return error mes‐
       sage.

       struct::graph::op::Johnsons G ?options...?
	      Searching for shortest paths between all pairs  of  vertices  in
	      graph.   For   sparse   graphs   asymptotically	quicker	  than
	      struct::graph::op::FloydWarshall algorithm. Johnson's  algorithm
	      uses struct::graph::op::BellmanFord and struct::graph::op::dijk‐
	      stra as subprocedures.

	      Time complexity: O(n**2*log(n) +n*m), where n is the  number  of
	      nodes and m is the number of edges in graph G.

	      Arguments:

		     Graph object G (input)
			    Directed  graph  G, weighted on edges and not con‐
			    taining 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 val‐
			    ues	 for non-existing connections between pairs of
			    nodes.

	      Result:
		     Dictionary containing distances between all pairs of ver‐
		     tices.

       struct::graph::op::FloydWarshall G
	      Searching	 for  shortest	paths  between	all  pairs of edges in
	      weighted graphs.

	      Time complexity: O(V^3) - where V is number of vertices.

	      Memory complexity: O(V^2).

	      Arguments:

		     Graph object G (input)
			    Directed and weighted graph G.

	      Result:
		     Dictionary containing shortest  distances	to  each  node
		     from each node.

	      Note:  Algorithm	finds  solutions  dynamically. It compares all
	      possible paths through the graph between each pair of  vertices.
	      Graph  shouldn't	possess any cycle with negative sum of weights
	      (the presence of such cycles means there is  no  shortest	 path,
	      since the total weight becomes lower each time the cycle is tra‐
	      versed).

	      On the other hand algorithm can be used to find those  cycles  -
	      if  any shortest distance found by algorithm for any nodes v and
	      u (when v is the same node as u) is negative, that  node	surely
	      belong to at least one negative cycle.

       struct::graph::op::MetricTravellingSalesman G
	      Algorithm	 for solving a metric variation of Travelling salesman
	      problem.	TSP problem is NP-Complete, so there is	 no  efficient
	      algorithm	 to  solve  it.	 Greedy	 methods are getting extremely
	      slow, with the increase in the set of nodes.

	      Arguments:

		     Graph object G (input)
			    Undirected, weighted graph G.

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

	      Note: It's 2-approximation algorithm.

       struct::graph::op::Christofides G
	      Another  algorithm for solving metric TSP problem.  Christofides
	      implementation uses Max Matching for reaching better  approxima‐
	      tion factor.

	      Arguments:

		     Graph Object G (input)
			    Undirected, weighted graph G.

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

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

       struct::graph::op::GreedyMaxMatching G
	      Greedy Max Matching procedure, which finds maximal matching (not
	      maximum) for given graph G. It adds edges to solution, beginning
	      from edges with the lowest cost.

	      Arguments:

		     Graph Object G (input)
			    Undirected graph G.

	      Result:
		     Set of edges - the max matching for graph G.

       struct::graph::op::MaxCut G U V
	      Algorithm solving a Maximum Cut Problem.

	      Arguments:

		     Graph Object G (input)
			    The graph to cut.

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

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

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

	      Note: MaxCut is a 2-approximation algorithm.

       struct::graph::op::UnweightedKCenter G k
	      Approximation algorithm that solves a k-center problem.

	      Arguments:

		     Graph Object G (input)
			    Undirected	complete graph G, which satisfies tri‐
			    angle inequality.

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

	      Result:
		     Set of nodes - k center for graph G.

	      Note: UnweightedKCenter is a 2-approximation algorithm.

       struct::graph::op::WeightedKCenter G nodeWeights W
	      Approximation algorithm that solves a weighted version of k-cen‐
	      ter problem.

	      Arguments:

		     Graph Object G (input)
			    Undirected complete graph G, which satisfies  tri‐
			    angle inequality.

		     Integer W (input)
			    Positive  integer  that  sets the maximum possible
			    weight of k-center found by algorithm.

		     List nodeWeights (input)
			    List of nodes and its weights in graph G.

	      Result:
		     Set of nodes, which is solution found by algorithm.

	      Note:WeightedKCenter is a 3-approximation algorithm.

       struct::graph::op::GreedyMaxIndependentSet G
	      A maximal independent set is an independent set such that adding
	      any other node to the set forces the set to contain an edge.

	      Algorithm	 for  input graph G returns set of nodes (list), which
	      are contained in Max Independent Set found by algorithm.

       struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
	      Weighted variation of Maximal Independent Set. It	 takes	as  an
	      input  argument not only graph G but also set of weights for all
	      vertices in graph G.

	      Note: Read also Maximal Independent  Set	description  for  more
	      info.

       struct::graph::op::VerticesCover G
	      Vertices	cover  is a set of vertices such that each edge of the
	      graph is incident to at  least  one  vertex  of  the  set.  This
	      2-approximation  algorithm  searches for minimum vertices cover,
	      which is a classical optimization problem	 in  computer  science
	      and is a typical example of an NP-hard optimization problem that
	      has an approximation algorithm.  For  input  graph  G  algorithm
	      returns  the set of edges (list), which is Vertex Cover found by
	      algorithm.

       struct::graph::op::EdmondsKarp G s t
	      Improved Ford-Fulkerson's algorithm, computing the maximum  flow
	      in given flow network G.

	      Arguments:

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

		     Node s (input)
			    The node that is a source for graph G.

		     Node t (input)
			    The node that is a sink for graph G.

	      Result:
		     Procedure returns the dictionary  containing  throughputs
		     for  all  edges.  For each key ( the edge between nodes u
		     and v in the form of list u v ) there is a value that  is
		     a	throughput for that key. Edges where throughput values
		     are equal to 0 are not returned ( it is like there was no
		     link  in the flow network between nodes connected by such
		     edge).

       The general idea of algorithm is finding the shortest augumenting paths
       in  graph  G,  as  long	as  they exist, and for each path updating the
       edge's weights along that path, with maximum possible  throughput.  The
       final  (maximum)	 flow is found when there is no other augumenting path
       from source to sink.

       Note: Algorithm complexity : O(V*E), where V is the number of nodes and
       E is the number of edges in graph G.

       struct::graph::op::BusackerGowen G desiredFlow s t
	      Algorithm	 finds	solution  for a minimum cost flow problem. So,
	      the goal is to find a flow, whose max value can be  desiredFlow,
	      from source node s to sink node t in given flow network G.  That
	      network except throughputs at edges has also defined a non-nega‐
	      tive  cost on each edge - cost of using that edge when directing
	      flow with that edge ( it can illustrate e.g. fuel usage, time or
	      any other measure dependent on usages ).

	      Arguments:

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

		     Integer desiredFlow (input)
			    Max value of the flow for that network.

		     Node s (input)
			    The source node for graph G.

		     Node t (input)
			    The sink node for graph G.

	      Result:
		     Dictionary containing values of used throughputs for each
		     edge ( key ).  found by algorithm.

	      Note: Algorithm complexity : O(V**2*desiredFlow), where V is the
	      number of nodes in graph G.

       struct::graph::op::ShortestsPathsByBFS G s outputFormat
	      Shortest	pathfinding  algorithm using BFS method. In comparison
	      to struct::graph::op::dijkstra it can work with negative weights
	      on  edges.  Of course negative cycles are not allowed. Algorithm
	      is better than dijkstra for sparse graphs, but also there	 exist
	      some  pathological  cases (those cases generally don't appear in
	      practise) that make time complexity increase exponentially  with
	      the growth of the number of nodes.

	      Arguments:

		     Graph Object G (input)
			    Input graph.

		     Node s (input)
			    Source  node for which all distances to each other
			    node in graph G are computed.

	      Options and result:

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

		     paths  When  selected  outputFormat  is paths - procedure
			    returns dictionary containing for each node	 v,  a
			    list of nodes, which is a path between source node
			    s and node v.

       struct::graph::op::BFS G s ?outputFormat...?
	      Breadth-First Search - algorithm creates the BFS	Tree.	Memory
	      and  time	 complexity:  O(V + E), where V is the number of nodes
	      and E is number of edges.

	      Arguments:

		     Graph Object G (input)
			    Input graph.

		     Node s (input)
			    Source node for BFS procedure.

	      Options and result:

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

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

       struct::graph::op::MinimumDiameterSpanningTree G
	      The goal is to find for input graph G, the  spanning  tree  that
	      has the minimum diameter value.

	      General  idea  of	 algorithm  is to run BFS over all vertices in
	      graph G. If the diameter d of the tree is odd, then we are  sure
	      that  tree given by BFS is minimum (considering diameter value).
	      When, diameter d is even, then optimal  tree  can	 have  minimum
	      diameter equal to d or d-1.

	      In  that	case, what algorithm does is rebuilding the tree given
	      by BFS, by adding a vertice between root node and	 root's	 child
	      node  (nodes), such that subtree created with child node as root
	      node is the greatest one (has the greatests height). In the next
	      step  for such rebuilded tree, we run again BFS with new node as
	      root node. If the height of the tree  didn't  changed,  we  have
	      found a better solution.

	      For   input  graph  G  algorithm	returns	 the  graph  structure
	      (struct::graph) that is a spanning tree  with  minimum  diameter
	      found by algorithm.

       struct::graph::op::MinimumDegreeSpanningTree G
	      Algorithm	 finds	for  input graph G, a spanning tree T with the
	      minimum possible degree. That problem is NP-hard,	 so  algorithm
	      is an approximation algorithm.

	      Let V be the set of nodes for graph G and let W be any subset of
	      V. Lets assume also that OPT is  optimal	solution  and  ALG  is
	      solution found by algorithm for input graph G.

	      It  can  be  proven  that solution found with the algorithm must
	      fulfil inequality:

	      ((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(n) + 1.

	      Arguments:

		     Graph Object G (input)
			    Undirected simple graph.

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

       struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
	      Algorithm finds maximum flow for the flow network represented by
	      graph G. It is based on the blocking-flow finding methods, which
	      give  us different complexities what makes a better fit for dif‐
	      ferent 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 block‐
			    ing flow computation.

	      Result:
		     Algorithm returns dictionary containing it's  flow	 value
		     for each edge (key) in network G.

       Note:  struct::graph::op::BlockingFlowByDinic gives O(m*n^2) complexity
       and struct::graph::op::BlockingFlowByMKM gives O(n^3) complexity, where
       n  is  the number of nodes and m is the number of edges in flow network
       G.

       struct::graph::op::BlockingFlowByDinic G s t
	      Algorithm for given network G with source s and sink t, finds  a
	      blocking	flow,  which  can be used to obtain a maximum flow for
	      that network G.

	      Arguments:

		     Graph Object G (input)
			    Directed graph G representing  the	flow  network.
			    Each  edge	should	have  attribute throughput set
			    with integer value.

		     Node s (input)
			    The source node for the flow network G.

		     Node t (input)
			    The sink node for the flow network G.

	      Result:
		     Algorithm returns	dictionary  containing	it's  blocking
		     flow value for each edge (key) in network G.

	      Note: Algorithm's complexity is O(n*m), where n is the number of
	      nodes and m is the number of edges in flow network G.

       struct::graph::op::BlockingFlowByMKM G s t
	      Algorithm for given network G with source s and sink t, finds  a
	      blocking	flow,  which  can be used to obtain a maximum flow for
	      that network G.

	      Arguments:

		     Graph Object G (input)
			    Directed graph G representing  the	flow  network.
			    Each  edge	should	have  attribute throughput set
			    with integer value.

		     Node s (input)
			    The source node for the flow network G.

		     Node t (input)
			    The sink node for the flow network G.

	      Result:
		     Algorithm returns	dictionary  containing	it's  blocking
		     flow value for each edge (key) in network G.

	      Note: Algorithm's complexity is O(n^2), where n is the number of
	      nodes in flow network G.

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

	      Arguments:

		     Graph Object G (input)
			    Flow  network  (directed graph where each edge has
			    set attribute: throughput ).

		     dictionary f (input)
			    Current flows in flow network G.

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

       struct::graph::op::createAugmentingNetwork G f path
	      Procedure	 creates  an  augmenting  network for a given residual
	      network G , flow f and augmenting path path.

	      Arguments:

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

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

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

	      Result:
		     Algorithm returns graph structure containing the modified
		     augmenting network.

       struct::graph::op::createLevelGraph Gf s
	      For given residual graph Gf procedure finds the level graph.

	      Arguments:

		     Graph Object Gf (input)
			    Residual   network,	  where	 each  edge  has  it's
			    attribute throughput set with certain value.

		     Node s (input)
			    The source node for the residual network Gf.

	      Result:
		     Procedure returns a level graph created from input resid‐
		     ual network.

       struct::graph::op::TSPLocalSearching G C
	      Algorithm	 is  a	heuristic  of  local  searching for Travelling
	      Salesman Problem. For some solution of TSP problem, it checks if
	      it's  possible  to  find a better solution. As TSP is well known
	      NP-Complete problem, so algorithm is a  approximation  algorithm
	      (with 2 approximation factor).

	      Arguments:

		     Graph Object G (input)
			    Undirected	and  complete  graph  with  attributes
			    "weight" set on each single edge.

		     List C (input)
			    A list of edges being Hamiltonian cycle, which  is
			    solution of TSP Problem for graph G.

	      Result:
		     Algorithm	returns	 the best solution for TSP problem, it
		     was able to find.

	      Note: The solution depends on  the  choosing  of	the  beginning
	      cycle  C.	 It's  not  true that better cycle assures that better
	      solution will be found, but practise shows that we  should  give
	      starting cycle with as small sum of weights as possible.

       struct::graph::op::TSPLocalSearching3Approx G C
	      Algorithm	 is  a	heuristic  of  local  searching for Travelling
	      Salesman Problem. For some solution of TSP problem, it checks if
	      it's  possible  to  find a better solution. As TSP is well known
	      NP-Complete problem, so algorithm is a  approximation  algorithm
	      (with 3 approximation factor).

	      Arguments:

		     Graph Object G (input)
			    Undirected	and  complete  graph  with  attributes
			    "weight" set on each single edge.

		     List C (input)
			    A list of edges being Hamiltonian cycle, which  is
			    solution of TSP Problem for graph G.

	      Result:
		     Algorithm	returns	 the best solution for TSP problem, it
		     was able to find.

	      Note: In practise 3-approximation algorithm turns out to be  far
	      more effective than 2-approximation, but it gives worser approx‐
	      imation factor. Further  heuristics  of  local  searching	 (e.g.
	      4-approximation)	 doesn't  give	enough	boost  to  square  the
	      increase of approximation factor, so 2 and 3 approximations  are
	      mainly used.

       struct::graph::op::createSquaredGraph G
	      X-Squared	 graph	is a graph with the same set of nodes as input
	      graph G, but a different set of edges. X-Squared graph has  edge
	      (u,v), if and only if, the distance between u and v nodes is not
	      greater than X and u != v.

	      Procedure for input graph G, returns its two-squared graph.

	      Note: Distances used in choosing new set of edges are  consider‐
	      ing the number of edges, not the sum of weights at edges.

       struct::graph::op::createCompleteGraph G originalEdges
	      For  input graph G procedure adds missing arcs to make it a com‐
	      plete graph. It also holds in variable originalEdges the set  of
	      arcs that graph G possessed before that operation.

BACKGROUND THEORY AND TERMS
   SHORTEST PATH PROBLEM
       Definition (single-pair shortest path problem):
	      Formally,	 given a weighted graph (let V be the set of vertices,
	      and E a set of edges), and one vertice v of V,  find  a  path  P
	      from  v  to  a v' of V so that the sum of weights on edges along
	      the path is minimal among all paths connecting v to v'.

       Generalizations:

	      ·	     The single-source shortest path problem, in which we have
		     to	 find  shortest	 paths	from  a source vertex v to all
		     other vertices in the graph.

	      ·	     The single-destination shortest path problem, in which we
		     have  to  find  shortest  paths  from all vertices in the
		     graph to a single	destination  vertex  v.	 This  can  be
		     reduced  to  the  single-source  shortest path problem by
		     reversing the edges in the graph.

	      ·	     The all-pairs shortest path problem, in which we have  to
		     find  shortest paths between every pair of vertices v, v'
		     in the graph.

	      Note: The result of Shortest Path problem can be	Shortest  Path
	      tree,  which  is a subgraph of a given (possibly weighted) graph
	      constructed so that the distance between a  selected  root  node
	      and  all	other  nodes is minimal. It is a tree because if there
	      are two paths between the root node and some vertex  v  (i.e.  a
	      cycle),  we  can delete the last edge of the longer path without
	      increasing the distance from the root node to any	 node  in  the
	      subgraph.

   TRAVELLING SALESMAN PROBLEM
       Definition:
	      For  given  edge-weighted	 (weights on edges should be positive)
	      graph the goal is to find the cycle that	visits	each  node  in
	      graph exactly once (Hamiltonian cycle).

       Generalizations:

	      ·	     Metric  TSP - A very natural restriction of the TSP is to
		     require that the distances between cities form a  metric,
		     i.e.,  they satisfy the triangle inequality. That is, for
		     any 3 cities A, B and C, the distance  between  A	and  C
		     must  be  at  most the distance from A to B plus the dis‐
		     tance from B to C. Most natural instances of TSP  satisfy
		     this constraint.

	      ·	     Euclidean	TSP - Euclidean TSP, or planar TSP, is the TSP
		     with the distance being the ordinary Euclidean  distance.
		     Euclidean	TSP  is a particular case of TSP with triangle
		     inequality,  since	 distances  in	plane  obey   triangle
		     inequality.  However,  it seems to be easier than general
		     TSP with triangle inequality. For	example,  the  minimum
		     spanning tree of the graph associated with an instance of
		     Euclidean TSP is a Euclidean minimum spanning  tree,  and
		     so	 can  be  computed  in	expected O(n log n) time for n
		     points (considerably less than the number of edges). This
		     enables the simple 2-approximation algorithm for TSP with
		     triangle inequality above to operate more quickly.

	      ·	     Asymmetric TSP - In most cases, the distance between  two
		     nodes  in the TSP network is the same in both directions.
		     The case where the distance from A to B is not  equal  to
		     the  distance  from  B  to A is called asymmetric TSP.  A
		     practical application of an asymmetric TSP is route opti‐
		     misation  using  street-level  routing (asymmetric due to
		     one-way streets, slip-roads and motorways).

   MATCHING PROBLEM
       Definition:
	      Given a graph G = (V,E), a matching or edge-independent set M in
	      G is a set of pairwise non-adjacent edges, that is, no two edges
	      share a common vertex. A vertex is matched if it is incident  to
	      an edge in the matching M.  Otherwise the vertex is unmatched.

       Generalizations:

	      ·	     Maximal  matching	-  a  matching M of a graph G with the
		     property that if any edge not in M is added to M,	it  is
		     no	 longer a matching, that is, M is maximal if it is not
		     a proper subset of any other matching  in	graph  G.   In
		     other  words,  a  matching	 M  of a graph G is maximal if
		     every edge in G has  a  non-empty	intersection  with  at
		     least one edge in M.

	      ·	     Maximum  matching	- a matching that contains the largest
		     possible number of	 edges.	 There	may  be	 many  maximum
		     matchings.	  The matching number of a graph G is the size
		     of a maximum matching. Note that every  maximum  matching
		     is	 maximal,  but not every maximal matching is a maximum
		     matching.

	      ·	     Perfect matching - a matching which matches all  vertices
		     of the graph. That is, every vertex of the graph is inci‐
		     dent to exactly one edge of the matching.	Every  perfect
		     matching  is  maximum  and hence maximal. In some litera‐
		     ture, the term  complete  matching	 is  used.  A  perfect
		     matching is also a minimum-size edge cover. Moreover, the
		     size of a maximum matching is no larger than the size  of
		     a minimum edge cover.

	      ·	     Near-perfect  matching  - a matching in which exactly one
		     vertex is unmatched. This can only occur when  the	 graph
		     has  an  odd number of vertices, and such a matching must
		     be maximum. If, for every vertex in a graph, there	 is  a
		     near-perfect  matching  that  omits only that vertex, the
		     graph is also called factor-critical.

       Related terms:

	      ·	     Alternating path - given a	 matching  M,  an  alternating
		     path is a path in which the edges belong alternatively to
		     the matching and not to the matching.

	      ·	     Augmenting path - given a matching M, an augmenting  path
		     is	 an alternating path that starts from and ends on free
		     (unmatched) vertices.

   CUT PROBLEMS
       Definition:
	      A cut is a partition of the vertices of a graph  into  two  dis‐
	      joint  subsets. The cut-set of the cut is the set of edges whose
	      end points are in different subsets of the partition. Edges  are
	      said to be crossing the cut if they are in its cut-set.

	      Formally:

	      ·	     a	cut  C	= (S,T) is a partition of V of a graph G = (V,
		     E).

	      ·	     an s-t cut C = (S,T) of a flow network N = (V,  E)	 is  a
		     cut  of  N such that s is included in S and t is included
		     in T, where s and t are the source	 and  the  sink	 of  N
		     respectively.

	      ·	     The  cut-set of a cut C = (S,T) is such set of edges from
		     graph G = (V, E) that each edge (u, v)  satisfies	condi‐
		     tion that u is included in S and v is included in T.

       In  an  unweighted undirected graph, the size or weight of a cut is the
       number of edges crossing the cut. In a weighted graph, the same term is
       defined by the sum of the weights of the edges crossing the cut.

       In a flow network, an s-t cut is a cut that requires the source and the
       sink to be in different subsets, and its cut-set only consists of edges
       going from the source's side to the sink's side. The capacity of an s-t
       cut is defined by the sum of capacity of each edge in the cut-set.

       The cut of a graph can sometimes refer to its cut-set  instead  of  the
       partition.

       Generalizations:

	      ·	     Minimum  cut - A cut is minimum if the size of the cut is
		     not larger than the size of any other cut.

	      ·	     Maximum cut - A cut is maximum if the size of the cut  is
		     not smaller than the size of any other cut.

	      ·	     Sparsest cut - The Sparsest cut problem is to bipartition
		     the vertices so as to minimize the ratio of the number of
		     edges across the cut divided by the number of vertices in
		     the smaller half of the partition.

   K-CENTER PROBLEM
       Definitions:

	      Unweighted K-Center
		     For any set S ( which is subset of V ) and	 node  v,  let
		     the  connect(v,S) be the cost of cheapest edge connecting
		     v with any node in S. The goal is to find	such  S,  that
		     |S| = k and max_v{connect(v,S)} is possibly small.

		     In other words, we can use it i.e. for finding best loca‐
		     tions in the city ( nodes of input graph ) for placing  k
		     buildings,	 such that those buildings will be as close as
		     possible to all other locations in town.

	      Weighted K-Center
		     The variation of unweighted k-center problem. Besides the
		     fact  graph  is  edge-weighted, there are also weights on
		     vertices of input graph G. We've got also restriction  W.
		     The  goal	is  to choose such set of nodes S ( which is a
		     subset of V ), that it's total weight is not greater than
		     W and also function: max_v { min_u { cost(u,v) }} has the
		     smallest possible worth ( v is a node in V	 and  u	 is  a
		     node in S ).

   FLOW PROBLEMS
       Definitions:

	      ·	     the maximum flow problem - the goal is to find a feasible
		     flow through a single-source,  single-sink	 flow  network
		     that is maximum.  The maximum flow problem can be seen as
		     a special case of more  complex  network  flow  problems,
		     such as the circulation problem.  The maximum value of an
		     s-t flow is equal to the minimum capacity of an  s-t  cut
		     in	 the  network, as stated in the max-flow min-cut theo‐
		     rem.

		     More formally for flow network G = (V,E), where for  each
		     edge  (u,	v)  we	have its throuhgput c(u,v) defined. As
		     flow F we define set of non-negative  integer  attributes
		     f(u,v) assigned to edges, satisfying such conditions:

		     [1]    for each edge (u, v) in G such condition should be
			    satisfied:	    0 <= f(u,v) <= c(u,v)

		     [2]    Network G has source node s such that the  flow  F
			    is equal to the sum of outcoming flow decreased by
			    the sum of incoming flow from that source node s.

		     [3]    Network G has sink node t such  that  the  the  -F
			    value  is  equal  to  the sum of the incoming flow
			    decreased by the sum of outcoming flow  from  that
			    sink node t.

		     [4]    For each node that is not a source or sink the sum
			    of incoming flow and sum of outcoming flow	should
			    be equal.

	      ·	     the  minimum  cost flow problem - the goal is finding the
		     cheapest possible way of sending a certain amount of flow
		     through a flow network.

	      ·	     blocking flow - a blocking flow for a residual network Gf
		     we name such flow b in Gf that:

		     [1]    Each path from sink to source is the shortest path
			    in Gf.

		     [2]    Each  shortest  path  in  Gf contains an edge with
			    fully used throughput in Gf+b.

	      ·	     residual network - for a flow network G and flow f resid‐
		     ual  network  is  built  with those edges, which can send
		     larger flow. It contains only those edges, which can send
		     flow larger than 0.

	      ·	     level  network - it has the same set of nodes as residual
		     graph, but has only those edges (u,v) from Gf  for	 which
		     such   equality  is  satisfied:  distance(s,u)+1  =  dis‐
		     tance(s,v).

	      ·	     augmenting network - it is	 a  modification  of  residual
		     network  considering the new flow values. Structure stays
		     unchanged but values of throughputs and  costs  at	 edges
		     are different.

   APPROXIMATION ALGORITHM
       k-approximation algorithm:
	      Algorithm	 is a k-approximation, when for ALG (solution returned
	      by algorithm) and OPT (optimal  solution),  such	inequality  is
	      true:

	      ·	     for minimalization problems: ALG/OPT <= k

	      ·	     for maximalization problems: OPT/ALG <= k

REFERENCES
       [1]    Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]

       [2]    Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]

       [3]    Kruskal's						     algorithm
	      [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]

       [4]    Prim's  algorithm	  [http://en.wikipedia.org/wiki/Prim%27s_algo‐
	      rithm]

       [5]    Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]

       [6]    Strongly			 connected		    components
	      [http://en.wikipedia.org/wiki/Strongly_connected_components]

       [7]    Tarjan's	   strongly	connected     components     algorithm
	      [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_com‐
	      ponents_algorithm]

       [8]    Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]

       [9]    Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]

       [10]   Bellman-Ford's algorithm	[http://en.wikipedia.org/wiki/Bellman-
	      Ford_algorithm]

       [11]   Johnson's	 algorithm [http://en.wikipedia.org/wiki/Johnson_algo‐
	      rithm]

       [12]   Floyd-Warshall's algorithm  [http://en.wikipedia.org/wiki/Floyd-
	      Warshall_algorithm]

       [13]   Travelling  Salesman Problem [http://en.wikipedia.org/wiki/Trav‐
	      elling_salesman_problem]

       [14]   Christofides					     Algorithm
	      [http://en.wikipedia.org/wiki/Christofides_algorithm]

       [15]   Max Cut [http://en.wikipedia.org/wiki/Maxcut]

       [16]   Matching [http://en.wikipedia.org/wiki/Matching]

       [17]   Max  Independent Set [http://en.wikipedia.org/wiki/Maximal_inde‐
	      pendent_set]

       [18]   Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]

       [19]   Ford-Fulkerson's	algorithm  [http://en.wikipedia.org/wiki/Ford-
	      Fulkerson_algorithm]

       [20]   Maximum	 Flow	 problem   [http://en.wikipedia.org/wiki/Maxi‐
	      mum_flow_problem]

       [21]   Busacker-Gowen's	algorithm  [http://en.wikipedia.org/wiki/Mini‐
	      mum_cost_flow_problem]

       [22]   Dinic's	algorithm  [http://en.wikipedia.org/wiki/Dinic's_algo‐
	      rithm]

       [23]   K-Center	    problem	 [http://www.csc.kth.se/~viggo/wwwcom‐
	      pendium/node128.html]

       [24]   BFS [http://en.wikipedia.org/wiki/Breadth-first_search]

       [25]   Minimum		  Degree	     Spanning		  Tree
	      [http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree]

       [26]   Approximation algorithm [http://en.wikipedia.org/wiki/Approxima‐
	      tion_algorithm]

BUGS, IDEAS, FEEDBACK
       This  document,	and the package it describes, will undoubtedly contain
       bugs and other problems.	 Please report such in the category struct  ::
       graph	 of	the	Tcllib	   SF	  Trackers     [http://source‐
       forge.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,	diame‐
       ter,  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>

struct				    0.11.3		  struct::graph::op(n)
[top]

List of man pages available for OpenSuSE

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net