← Back to branch summary

~ubuntu-branches/ubuntu/karmic/scilab/karmic

« back to all changes in this revision

Viewing changes to routines/metanet/clique.f

  • Committer: Bazaar Package Importer
  • Author(s): Torsten Werner
  • Date: 2002-03-21 16:57:43 UTC
  • Revision ID: james.westby@ubuntu.com-20020321165743-e9mv12c1tb1plztg
Tags: upstream-2.6
Import upstream version 2.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
routines/metanet/clique.f
 
1
c partial enumerative algorithm for the maximum clique problem
 
2
c      subroutine clique(n,m,madj,clmax,clnod,bestn)
 
3
      subroutine clique(n,m,mat,maxclique,actnode,best,edge,start,
 
4
     1 last,adj)
 
5
      integer    row,col
 
6
      integer    mat(n,n),templog
 
7
c      logical*1  mat(n,n),templog
 
8
      integer    actnode(n),edge(n),temp,adj(m,n)
 
9
      integer    start(n),last(n),d,dtemp,best(n)
 
10
c     maxm       greater or equal to the actual size of maxclique
 
11
c     n          number of nodes in graph
 
12
c     mat        adjacency matrix
 
13
c     actnode    actual nodes in original matrix
 
14
c     adj        represents nodes found at all depths
 
15
c     maxclique  size of largest currently know clique
 
16
c     best       nodes in largest currently know clique
 
17
c     d          current depth of traversal
 
18
c     start      node currently being expanded at depth d
 
19
c     last       last node to (possibly) be expanded at depth d
 
20
      maxclique=1
 
21
c     -- maintain pointers to original matrix
 
22
      maxclique=0
 
23
      do 25 node = 1,n
 
24
        actnode(node) = node
 
25
        best(node)=0
 
26
25    continue
 
27
        do 30 row = 1,n
 
28
          edge(row) = 0
 
29
          do 35 col = 1,n
 
30
            if (mat(row,col).eq.1) edge(row) = edge(row)+1
 
31
35        continue
 
32
30      continue
 
33
        do 40 node = 1,n-2
 
34
          min = n
 
35
          do 45 row = node,n
 
36
            if (edge(row).lt.min) then
 
37
              min = edge(row)
 
38
              minnode = row
 
39
            end if
 
40
45        continue
 
41
          edge(minnode) = edge(node)
 
42
          if (node.ne.minnode) then
 
43
            temp = actnode(node)
 
44
            actnode(node) = actnode(minnode)
 
45
            actnode(minnode) = temp
 
46
            do 50 row = 1,n
 
47
              templog = mat(row,node)
 
48
              mat(row,node) = mat(row,minnode)
 
49
              mat(row,minnode) = templog
 
50
50          continue
 
51
            do 55 col = 1,n
 
52
              templog = mat(node,col)
 
53
              mat(node,col) = mat(minnode,col)
 
54
              mat(minnode,col) = templog
 
55
55          continue
 
56
          end if
 
57
          do 60 col = node,n
 
58
            if (mat(node,col).eq.1) edge(col) = edge(col) - 1
 
59
60        continue
 
60
40      continue
 
61
c      end if
 
62
      d = 1
 
63
      start(1) = 0
 
64
      last(1) = n
 
65
      do 65 col = 1,n
 
66
        adj(1,col) = col
 
67
65    continue
 
68
 
 
69
c     -- main algorithm
 
70
 
 
71
70    start(d) = start(d) + 1
 
72
      if ((d+last(d)-start(d)).gt.maxclique) then
 
73
        dtemp = d
 
74
        d = d + 1
 
75
        start(d) = 0
 
76
        last(d) = 0
 
77
c       -- determine node for next depth
 
78
        do 75 col = (start(dtemp)+1),last(dtemp)
 
79
          if (mat(adj(dtemp,start(dtemp)),adj(dtemp,col)).eq.1) then
 
80
            last(d) = last(d) + 1
 
81
            adj(d,last(d)) = adj(dtemp,col)
 
82
          end if
 
83
75      continue
 
84
c       -- if the next depth doesn't contain any nodes, see if a new
 
85
c       -- maxclique has been found and return to previous depth
 
86
        if (last(d).eq.0.) then
 
87
          d = d - 1
 
88
          if (d.gt.maxclique) then
 
89
            maxclique = d
 
90
            do 80 col = 1,d
 
91
              best(col) = adj(col,start(col))
 
92
80          continue
 
93
          end if
 
94
        end if
 
95
      else
 
96
c       -- prune, further expansion would not find a better incumbent
 
97
        d = d - 1
 
98
      end if
 
99
c     -- continue traversal until a depth of zero is reached
 
100
      if (d.gt.0.) goto 70
 
101
      return 
 
102
      end
 
103
 
 
104