gonum-quasi-clique

module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 28, 2019 License: MIT

README

gonum-quasi-clique

Implementation of algorithms for finding a.k.a. "quasi-cliques" (relaxation of clique) for Gonum graph representation.

Implemented algorithms

Prerequisites

  • Go v1.13 (tested only with this version)

Some algorithms require external solver to be installed (e.g. DDA), currently only the following solvers are supported:

Example

DDA
package main

import (
	"fmt"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/simple"
	
	"github.com/nskondratev/gonum-quasi-clique/dda"
	"github.com/nskondratev/gonum-quasi-clique/dda/solvers/glpk"
)

func main() {
	// Create simple graph with 6 vertices and 10 edges
	g := simple.NewUndirectedGraph()

	// Add nodes
	for i := 0; i < 6; i++ {
		g.AddNode(simple.Node(i))
	}

	// Add edges
	g.SetEdge(simple.Edge{F: simple.Node(0), T: simple.Node(1)})
	g.SetEdge(simple.Edge{F: simple.Node(0), T: simple.Node(3)})
	g.SetEdge(simple.Edge{F: simple.Node(0), T: simple.Node(4)})
	g.SetEdge(simple.Edge{F: simple.Node(0), T: simple.Node(5)})
	g.SetEdge(simple.Edge{F: simple.Node(1), T: simple.Node(2)})
	g.SetEdge(simple.Edge{F: simple.Node(1), T: simple.Node(3)})
	g.SetEdge(simple.Edge{F: simple.Node(1), T: simple.Node(4)})
	g.SetEdge(simple.Edge{F: simple.Node(2), T: simple.Node(3)})
	g.SetEdge(simple.Edge{F: simple.Node(3), T: simple.Node(4)})
	g.SetEdge(simple.Edge{F: simple.Node(4), T: simple.Node(5)})

	// Set up DDA options
	ddaOpts := dda.DDAOpts{
		InputGraph: g,
		Gamma:      0.5,
		GraphConstructor: func() dda.GraphBuilder {
			return simple.NewUndirectedGraph()
		},
		EdgeConstructor: func(n1, n2 graph.Node) graph.Edge {
			return simple.Edge{F: n1, T: n2}
		},
		// You can also specify dda.AllSolutions to get all maximal quasi-cliques
		SolveMode:  dda.OneSolution,
		YQCKSolver: glpk.Solve,
	}

	// Find solutions
	_, quasiCliqueSize, err := dda.DDA(ddaOpts)
	if err != nil {
		panic(err) // Just for example
	}
	fmt.Printf("Quasi-clique size: %d\n", quasiCliqueSize) // Output: Quasi-clique size: 5
}

Directories

Path Synopsis
dda
Package dda provides the implementation of Degree Decomposition Algorithm for finding maximal degree-based quasi-clique (QC)
Package dda provides the implementation of Degree Decomposition Algorithm for finding maximal degree-based quasi-clique (QC)
examples
dda command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL