NAME

       ::struct::graph  -  Create  and  manipulate directed graph
       objects


SYNOPSIS

       package require struct ?1.0?

       ::struct::graph graphName

_________________________________________________________________


DESCRIPTION

       The ::struct::graph command creates  a  new  graph  object
       with an associated global Tcl command whose name is graph­
       Name.  This command may be used to invoke  various  opera­
       tions on the graph.  It has the following general form:
              graphName option ?arg arg ...?
       Option  and  the  args determine the exact behavior of the
       command.

       A directed graph is a structure containing two collections
       of  elements, called nodes and arcs resp., together with a
       relation ("connectivity") that places a general  structure
       upon the nodes and arcs.

       Each arc is connected to two nodes, one of which is called
       the source and the other the target. This imposes a direc­
       tion  upon the arc, which is said to go from the source to
       the target. It is allowed that source and target of an arc
       are  the same node. Such an arc is called a loop. Whenever
       a node is source or target of an arc both are said  to  be
       adjacent. This extends into a relation between nodes, i.e.
       if two nodes are connected through at least one  arc  they
       are said to be adjacent too.

       Each  node  can be the source and target for any number of
       arcs. The former are called the outgoing arcs of the node,
       the  latter  the  incoming arcs of the node. The number of
       edges in either set is called the in- resp. the out-degree
       of the node.

       In addition to maintaining the node and arc relationships,
       this graph implementation allows any number of keyed  val­
       ues to be associated with each node and arc.

       The following commands are possible for graph objects:

       graphName destroy
              Destroy  the graph, including its storage space and
              associated command.

              Remove the specified arcs from the graph.

       graphName arc exists arc
              Return true if the  specified  arc  exists  in  the
              graph.

       graphName arc get arc ?-key key?
              Return  the  value  associated with the key key for
              the arc.  If no key is specified, the key  data  is
              assumed.

       graphName arc insert start end ?child?
              Insert  an arc named child into the graph beginning
              at the node start and ending at the  node  end.  If
              the name of the new arc is not specified the system
              will generate a unique name of the form arcx.

       graphName arc set arc ?-key key? ?value?
              Set or get one of the keyed values associated  with
              an  arc.   If  no key is specified, the key data is
              assumed.  Each arc that is added to a graph has the
              value  ""  assigned  to the key data automatically.
              An arc may have any number of keyed values  associ­
              ated with it.  If value is not specified, this com­
              mand returns the current value assigned to the key;
              if  value  is  specified, this command assigns that
              value to the key.

       graphName arc source arc
              Return the node the given arc begins at.

       graphName arc target arc
              Return the node the given arc ends at.

       graphName arc unset arc ?-key key?
              Remove a keyed value from the arc arc.  If  no  key
              is specified, the key data is assumed.

       graphName arcs ?-in|-out|-adj|-inner|-embedding nodelist?

              Return  a list of arcs in the graph. If no restric­
              tion is specified a list  containing  all  arcs  is
              returned.  If one of the five possible restrictions
              is specified only arcs satisfying that  restriction
              are  returned.  All  restrictions involve a list of
              nodes, specified after the key for the  restriction
              itself.

              -in  Return  a list of all arcs whose target is one
              of the nodes in the nodelist.

              -out Return a list of all arcs whose source is  one
              of the nodes in the nodelist.

              one of the nodes in the nodelist. This is the union
              of the nodes returned by -in and -out.

              -inner Return a list of all arcs adjacent to two of
              the nodes in the nodelist. This is the set of  arcs
              in the subgraph spawned by the specified nodes.

              -embedding  Return  a  list of all arcs adjacent to
              exactly one of the nodes in the nodelist.  This  is
              the  set of arcs connecting the subgraph spawned by
              the specified nodes to the rest of the graph.

       graphName node degree ?-in|-out? node
              Return the number of arcs adjacent to the specified
              node.  If  one  of  the restrictions -in or -out is
              given only the incoming  resp.  outgoing  arcs  are
              counted.

       graphName node delete node ?node ...?
              Remove  the specified nodes from the graph.  All of
              the nodes' arcs will be removed as well to  prevent
              unconnected arcs.

       graphName node exists node
              Return  true  if  the  specified node exists in the
              graph.

       graphName node get node ?-key key?
              Return the value associated with the  key  key  for
              the  node.  If no key is specified, the key data is
              assumed.

       graphName node insert ?child?
              Insert a node named child into the graph. The nodes
              has no arcs connected to it. If the name of the new
              child is not specified the system will  generate  a
              unique name of the form nodex.

       graphName node opposite node arc
              Return  the  node at the other end of the specified
              arc, which has to be adjacent to the given node.

       graphName node set node ?-key key? ?value?
              Set or get one of the keyed values associated  with
              a  node.   If  no key is specified, the key data is
              assumed.  Each node that is added to  a  graph  has
              the  value  ""  assigned  to the key data automati­
              cally.  A node may have any number of keyed  values
              associated  with  it.   If  value is not specified,
              this command returns the current value assigned  to
              the  key;  if  value  is  specified,  this  command
              assigns that value to the key.

              Remove a keyed value from the node node.  If no key
              is specified, the key data is assumed.

       graphName nodes ?-in|-out|-adj|-inner|-embedding nodelist?
              Return a list of nodes in the graph. If no restric­
              tion  is  specified  a list containing all nodes is
              returned. If one of the five possible  restrictions
              is specified only nodes satisfying that restriction
              are returned. All restrictions involve  a  list  of
              nodes,  specified after the key for the restriction
              itself.

              The possible  restrictions  are  the  same  as  for
              method arcs. The set of nodes to return is computed
              as the union of all source and target nodes for all
              the  arcs satisfying the restriction as defined for
              arcs.

       graphName swap node1 node2
              Swap the position of node1 and node2 in the  graph.

       graphName  walk node ?-order order? ?-type type? ?-dir
              direction? -command cmd

              Perform  a breadth-first or depth-first walk of the
              graph starting at the node node going in either the
              direction  of  outgoing or opposite to the incoming
              arcs.

              The type of walk, breadth-first or depth-first,  is
              determined  by  the  value  of  type; bfs indicates
              breadth-first, dfs indicates  depth-first.   Depth-
              first is the default.

              The  order  of  the  walk, pre-order, post-order or
              both-order is determined by the value of order; pre
              indicates  pre-order,  post  indicates  post-order,
              both  indicates  both-order.   Pre-order   is   the
              default.  Pre-order  walking  means  that a node is
              visited before any of its neighbors (as defined  by
              the direction, see below). Post-order walking means
              that a parent is visited after any  of  its  neigh­
              bors.  Both-order walking means that a node is vis­
              ited before and after any  of  its  neighbors.  The
              combination  of  a  bread-first  walk with post- or
              both-order is illegal.

              The direction of the  walk  is  determined  by  the
              value  of  dir;  backward  indicates  the direction
              opposite to the incoming  arcs,  forward  indicates
              the direction of the outgoing arcs.

              As  the  walk  progresses,  the command cmd will be

              (enter  or leave) and values graphName and the name
              of the current node appended. For a pre-order  walk
              all  nodes are Bentered, for a post-order all nodes
              are left. In a both-order walk the first visit of a
              node enters it, the second visit leaves it.


KEYWORDS

       graph


Man(1) output converted with man2html