grTheory - Graph Theory Toolbox

27 functions for different tasks of graph theory

Description

GrTheory - Graph Theory Toolbox.
Functions:
grBase - find all bases of digraph;
grCoBase - find all contrabases of digraph;
grCoCycleBasis - find all independent cut-sets for a connected graph;
grColEdge - solve the color problem for graph edges;
grColVer - solve the color problem for graph vertexes;
grComp - find all components of graph;
grCycleBasis - find all independent cycles for a connected graph;
grDecOrd - solve the problem about decomposition of the digraph to the sections with mutually accessed vertexes (strongly connected components);
grDistances - find the distances between any vertexes of graph;
grEccentricity - find the (weighted) eccentricity of all vertexes, radius, diameter, center vertexes and the periphery vertexes;
grIsEulerian - find the Eulerian cycle of graph;
grIsomorph - solve the problem about isomorphism for two graphs;
grMaxComSu - solve the maximal complete sugraph problem for the graph;
grMaxFlows - solve the maximal flow problem for the digraph;
grMaxMatch - solve the maximal matching problem for the graph;
grMaxStabSet - solve the maximal stable set problem for the graph;
grMinAbsEdgeSet - solve the minimal absorbant set problem for the graph edges;
grMinAbsVerSet - solve the minimal absorbant set problem for the graph vertexes;
grMinCutSet - solve the minimal cut-set problem for the digraph;
grMinEdgeCover - solve the minimal edge cover problem for the graph;
grMinSpanTree - solve the minimal spanning tree problem for the graph;
grMinVerCover - solve the minimal vertex cover problem for the graph;
grPERT - solve the project evaluation research task;
grPlot - draw the plot of the graph (digraph);
grShortPath - solve the shortest path problem for the digraph;
grTranClos - built the transitive closure for the digraph;
grTravSale - solve the nonsymmetrical traveling salesman problem;
grValidation - auxiliary function (the data validation);
grTheoryTest - test program for all functions.

• Required Products: Optimization Toolbox
• MATLAB release: MATLAB 7.0.1 (R14SP1)
• Other requirements: PC

Other Files

Contents.m,
grBase.m,
grCoBase.m,
grCoCycleBasis.m,
grColEdge.m,
grColVer.m,
grComp.m,
grCycleBasis.m,
grDecOrd.m,
grDistances.m,
grEccentricity.m,
grIsEulerian.m,
grIsomorph.m,
grMaxComSu.m,
grMaxFlows.m,
grMaxMatch.m,
grMaxStabSet.m,
grMinAbsEdgeSet.m,
grMinAbsVerSet.m,
grMinCutSet.m,
grMinEdgeCover.m,
grMinSpanTree.m,
grMinVerCover.m,
grPERT.m,
grPlot.m,
grShortPath.m,
grTheoryTest.m,
grTranClos.m,
grTravSale.m,
grValidation.m,
license.txt

[x s]

 

[Alex Pesch]

I think, the Optimization Toolbox is required. The function MaxFlows for example is not running here, because 'linprog' doesn't exist.

[Nick Valuy]

 

[ahmed kolsi]

 

[Michael Waisberg]

The plotgraph function only works well with small graphs. It produces awful graphs when using more than four vertex. The toolbox could come with some function to format the data. I used one called cedge.m which worked well. Also, to use this toolbox you will need to install at least arrow.m.

[Alexandre Felt]

Great job, works fine!

[Zhenya Donchik]

I`m very interesting by the theory of managment

[Vlastislav Weiner]

Salesman problem doesn't work without miqp function. But where could I find it???

[Igor Yegorkin]

Beautiful job!

[sanith Wijesinghe]

 

[Pablo Riera]

Excellent

[giu giu]

There are some bugs

[wael rashwan]

 

[li yifan china]

 

[Ahmad AbdulWakeel]

it is very good toolbox

[gloria macapagal]

 

[hiro mano]

 

[xue huiyan]

thanks

[xm blade]

Good package it sounds!
One additional question: Could the input be thousands of nodes in one graph?

[jason tharmaraj]

can you send me complex networks analysis codes

[Andi Patombongi]

 

[Swamy Korada]

Great work

Is there a script to find all possible paths between 2 nodes?

[fan fanwen]

 

[Tim Davis]

Comment to Swamy Korada: Finding all possible paths between 2 nodes is an NP-hard problem. Any such algorithm would either give an approximate solution, or take exponential time.

[li pengfei]

 

[rose rose]

very good!

[Chao Wang]

good job

[Andrew Jackson]

 

[Florian]

does exactly what I'm looking for!
A minor bug in grMaxComSu.m

If the graph itself is a clique e.g. [1 2; 1 3; 2 3] the function gives an error. E1 in the code is then empty. Possibly account for this cas in a future version. Great work!