johnson.go

Documentation: gonum.org/v1/plot/plotter

     1  // Copyright ©2015 The Gonum Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package plotter
     6  
     7  // johnson implements Johnson's "Finding all the elementary
     8  // circuits of a directed graph" algorithm. SIAM J. Comput. 4(1):1975.
     9  //
    10  // Comments in the johnson methods are kept in sync with the comments
    11  // and labels from the paper.
    12  type johnson struct {
    13  	adjacent graph // SCC adjacency list.
    14  	b        []set // Johnson's "B-list".
    15  	blocked  []bool
    16  	s        int
    17  
    18  	stack []int
    19  
    20  	result [][]int
    21  }
    22  
    23  // cyclesIn returns the set of elementary cycles in the graph g.
    24  func cyclesIn(g graph) [][]int {
    25  	j := johnson{
    26  		adjacent: g.clone(),
    27  		b:        make([]set, len(g)),
    28  		blocked:  make([]bool, len(g)),
    29  	}
    30  
    31  	// len(j.adjacent) will be the order of g until Tarjan's analysis
    32  	// finds no SCC, at which point t.sccSubGraph returns nil and the
    33  	// loop breaks.
    34  	for j.s < len(j.adjacent)-1 {
    35  		// We use the previous SCC adjacency to reduce the work needed.
    36  		t := newTarjan(j.adjacent.subgraph(j.s))
    37  		// A_k = adjacency structure of strong component K with least
    38  		//       vertex in subgraph of G induced by {s, s+1, ... ,n}.
    39  		j.adjacent = t.sccSubGraph(2) // Only allow SCCs with >= 2 vertices.
    40  		if len(j.adjacent) == 0 {
    41  			break
    42  		}
    43  
    44  		// s = least vertex in V_k
    45  		for _, v := range j.adjacent {
    46  			s := len(j.adjacent)
    47  			for n := range v {
    48  				if n < s {
    49  					s = n
    50  				}
    51  			}
    52  			if s < j.s {
    53  				j.s = s
    54  			}
    55  		}
    56  		for i, v := range j.adjacent {
    57  			if len(v) > 0 {
    58  				j.blocked[i] = false
    59  				j.b[i] = make(set)
    60  			}
    61  		}
    62  
    63  		//L3:
    64  		_ = j.circuit(j.s)
    65  		j.s++
    66  	}
    67  
    68  	return j.result
    69  }
    70  
    71  // circuit is the CIRCUIT sub-procedure in the paper.
    72  func (j *johnson) circuit(v int) bool {
    73  	f := false
    74  	j.stack = append(j.stack, v)
    75  	j.blocked[v] = true
    76  
    77  	//L1:
    78  	for w := range j.adjacent[v] {
    79  		if w == j.s {
    80  			// Output circuit composed of stack followed by s.
    81  			r := make([]int, len(j.stack)+1)
    82  			copy(r, j.stack)
    83  			r[len(r)-1] = j.s
    84  			j.result = append(j.result, r)
    85  			f = true
    86  		} else if !j.blocked[w] {
    87  			if j.circuit(w) {
    88  				f = true
    89  			}
    90  		}
    91  	}
    92  
    93  	//L2:
    94  	if f {
    95  		j.unblock(v)
    96  	} else {
    97  		for w := range j.adjacent[v] {
    98  			j.b[w][v] = struct{}{}
    99  		}
   100  	}
   101  	j.stack = j.stack[:len(j.stack)-1]
   102  
   103  	return f
   104  }
   105  
   106  // unblock is the UNBLOCK sub-procedure in the paper.
   107  func (j *johnson) unblock(u int) {
   108  	j.blocked[u] = false
   109  	for w := range j.b[u] {
   110  		delete(j.b[u], w)
   111  		if j.blocked[w] {
   112  			j.unblock(w)
   113  		}
   114  	}
   115  }
   116  
   117  func min(a, b int) int {
   118  	if a < b {
   119  		return a
   120  	}
   121  	return b
   122  }
   123  
   124  // tarjan implements Tarjan's strongly connected component finding
   125  // algorithm. The implementation is from the pseudocode at
   126  //
   127  // http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm?oldid=642744644
   128  type tarjan struct {
   129  	g graph
   130  
   131  	index      int
   132  	indexTable []int
   133  	lowLink    []int
   134  	onStack    []bool
   135  
   136  	stack []int
   137  
   138  	sccs [][]int
   139  }
   140  
   141  // newTarjan returns a tarjan with the sccs field filled with the
   142  // strongly connected components of the directed graph g.
   143  func newTarjan(g graph) *tarjan {
   144  	t := tarjan{
   145  		g: g,
   146  
   147  		indexTable: make([]int, len(g)),
   148  		lowLink:    make([]int, len(g)),
   149  		onStack:    make([]bool, len(g)),
   150  	}
   151  	for v := range t.g {
   152  		if t.indexTable[v] == 0 {
   153  			t.strongconnect(v)
   154  		}
   155  	}
   156  	return &t
   157  }
   158  
   159  // strongconnect is the strongconnect function described in the
   160  // wikipedia article.
   161  func (t *tarjan) strongconnect(v int) {
   162  	// Set the depth index for v to the smallest unused index.
   163  	t.index++
   164  	t.indexTable[v] = t.index
   165  	t.lowLink[v] = t.index
   166  	t.stack = append(t.stack, v)
   167  	t.onStack[v] = true
   168  
   169  	// Consider successors of v.
   170  	for w := range t.g[v] {
   171  		if t.indexTable[w] == 0 {
   172  			// Successor w has not yet been visited; recur on it.
   173  			t.strongconnect(w)
   174  			t.lowLink[v] = min(t.lowLink[v], t.lowLink[w])
   175  		} else if t.onStack[w] {
   176  			// Successor w is in stack s and hence in the current SCC.
   177  			t.lowLink[v] = min(t.lowLink[v], t.indexTable[w])
   178  		}
   179  	}
   180  
   181  	// If v is a root node, pop the stack and generate an SCC.
   182  	if t.lowLink[v] == t.indexTable[v] {
   183  		// Start a new strongly connected component.
   184  		var (
   185  			scc []int
   186  			w   int
   187  		)
   188  		for {
   189  			w, t.stack = t.stack[len(t.stack)-1], t.stack[:len(t.stack)-1]
   190  			t.onStack[w] = false
   191  			// Add w to current strongly connected component.
   192  			scc = append(scc, w)
   193  			if w == v {
   194  				break
   195  			}
   196  		}
   197  		// Output the current strongly connected component.
   198  		t.sccs = append(t.sccs, scc)
   199  	}
   200  }
   201  
   202  // sccSubGraph returns the graph of the tarjan's strongly connected
   203  // components with each SCC containing at least min vertices.
   204  // sccSubGraph returns nil if there is no SCC with at least min
   205  // members.
   206  func (t *tarjan) sccSubGraph(min int) graph {
   207  	if len(t.g) == 0 {
   208  		return nil
   209  	}
   210  	sub := make(graph, len(t.g))
   211  
   212  	var n int
   213  	for _, scc := range t.sccs {
   214  		if len(scc) < min {
   215  			continue
   216  		}
   217  		n++
   218  		for _, u := range scc {
   219  			for _, v := range scc {
   220  				if _, ok := t.g[u][v]; ok {
   221  					if sub[u] == nil {
   222  						sub[u] = make(set)
   223  					}
   224  					sub[u][v] = struct{}{}
   225  				}
   226  			}
   227  		}
   228  	}
   229  	if n == 0 {
   230  		return nil
   231  	}
   232  
   233  	return sub
   234  }
   235  
   236  // set is an integer set.
   237  type set map[int]struct{}
   238  
   239  // graph is an edge list representation of a graph.
   240  type graph []set
   241  
   242  // remove deletes edges that make up the given paths from the graph.
   243  func (g graph) remove(paths [][]int) {
   244  	for _, p := range paths {
   245  		for i, u := range p[:len(p)-1] {
   246  			delete(g[u], p[i+1])
   247  		}
   248  	}
   249  }
   250  
   251  // subgraph returns a subgraph of g induced by {s, s+1, ... , n}. The
   252  // subgraph is destructively generated in g.
   253  func (g graph) subgraph(s int) graph {
   254  	for u := range g[:s] {
   255  		g[u] = nil
   256  	}
   257  	for u, e := range g[s:] {
   258  		for v := range e {
   259  			if v < s {
   260  				delete(g[u+s], v)
   261  			}
   262  		}
   263  	}
   264  	return g
   265  }
   266  
   267  // clone returns a deep copy of the graph g.
   268  func (g graph) clone() graph {
   269  	c := make(graph, len(g))
   270  	for u, e := range g {
   271  		for v := range e {
   272  			if c[u] == nil {
   273  				c[u] = make(set)
   274  			}
   275  			c[u][v] = struct{}{}
   276  		}
   277  	}
   278  	return c
   279  }
   280
View as plain text