doc/graph_orientation.dox
changeset 1956 a055123339d5
parent 1715 e71778873dd0
child 2158 0b620ff10e7c
equal deleted inserted replaced
2:b4ffd5335540 3:14376c5a0d48
    61 
    61 
    62 Well, we are ready to start <tt>main()</tt>.
    62 Well, we are ready to start <tt>main()</tt>.
    63 \skip main
    63 \skip main
    64 \until {
    64 \until {
    65 
    65 
    66 First we check whether the program is called with exactly 1 parameter.
    66 First we check whether the program is called with exactly one parameter.
    67 If it isn't, we print a short help message end exit.
    67 If it isn't, we print a short help message end exit.
    68 The vast majority of people would probably skip this block.
    68 The vast majority of people would probably skip this block.
    69 \skip if
    69 \skip if
    70 \until }
    70 \until }
    71 
    71 
    72 Now, we read a graph \c g, and a map \c f containing
    72 Now, we read a graph \c g, and a map \c f containing
    73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    73 the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
    74 file. To generate the output picture, we also read the node titles (\c id) and
    74 file. To generate the output picture, we also read the node titles (\c label)
       
    75 and
    75 coordinates (\c coords).
    76 coordinates (\c coords).
    76 So, first we create the graph
    77 So, first we create the graph
    77 \skipline ListGraph
    78 \skipline ListGraph
    78 and the corresponding NodeMaps.
    79 and the corresponding NodeMaps.
    79 \skipline NodeMap
    80 \skipline NodeMap
    84 the file is missing or corrupt.
    85 the file is missing or corrupt.
    85 \skip try
    86 \skip try
    86 \until }
    87 \until }
    87 \until }
    88 \until }
    88 
    89 
    89 The algorithm needs a "level" integer value assigned to each node. In the
    90 The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
    90 beginning, the nodes are on level 0.
    91 beginning of the execution.
       
    92 
    91 \skipline level
    93 \skipline level
    92 
    94 
    93 The deficiency (\c def) of a node is the in-degree requirement minus the 
    95 The deficiency (\c def) of a node is the in-degree requirement minus the 
    94 actual in-degree.
    96 actual in-degree.
    95 
    97 
    99 A node is \e active if its deficiency is positive (i.e. if it doesn't meet
   101 A node is \e active if its deficiency is positive (i.e. if it doesn't meet
   100 the degree requirement).
   102 the degree requirement).
   101 \skip active
   103 \skip active
   102 \until def
   104 \until def
   103 
   105 
   104 We also store in a bool map indicating which edges are reverted. Actually this is only
   106 We also store in a bool map indicating which edges are reverted.
       
   107 Actually this map called \c rev is only
   105 used to draw these edges with different color in the output picture. The
   108 used to draw these edges with different color in the output picture. The
   106 algorithm will update this map called \c rev, but will not use it otherwise.
   109 algorithm updates this map, but will not use it otherwise.
   107 \skip rev
   110 \skip rev
   108 \until reversed
   111 \until reversed
   109 
   112 
   110 The variable \c nodeNum will refer to the number of nodes.
   113 The variable \c nodeNum will refer to the number of nodes.
   111 \skipline nodeNum
   114 \skipline nodeNum
   112 
   115 
   113 Here comes the algorithms itself. 
   116 Here comes the algorithms itself. 
   114 In each iteration we choose an active node (\c act will store it). If there is
   117 In each iteration we choose an active node (\c act will do it for us).
       
   118 If there is
   115 no such a node, then the orientation is feasible so we are done.
   119 no such a node, then the orientation is feasible so we are done.
   116 \skip act
   120 \skip act
   117 \until while
   121 \until while
   118 
   122 
   119 Then we check if there exists an edge leaving this node that steps down exactly
   123 Then we check if there exists an edge leaving this node that steps down exactly