Code covered by the BSD License  

Highlights from
grTheory - Graph Theory Toolbox

4.48387

4.5 | 31 ratings Rate this file 291 Downloads (last 30 days) File Size: 34.3 KB File ID: #4266

grTheory - Graph Theory Toolbox

by

 

16 Dec 2003 (Updated )

28 functions for different tasks of graph theory

| Watch this File

File Information
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;
grShortVerPath - for digraph with weighted vertexes solve the problem about the path with minimal weight of verticies;
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
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (45)
16 Oct 2014 Chenjie  
20 Aug 2014 Liang  
24 May 2014 Muhammad Abrar Akber

MIQP is missing to use grTravSale, How and where to get it?

10 Oct 2013 Rohini Sharma

Sir I am new to MATLAB . I have downloaded your codes for WSN, oneRoundWSN.m

please tell me how to rin this in MATLAB.

Thanks

31 Jul 2012 Yonggon

Sumantra, make sure your graph is connected. As long as your graph is connected, you should get correct result.

For this one, with arbitrary edges to make the graph connected without introducing any new cycle, I get
2-5-7-2, 2-5-8-11-7-2, and 2-5-8-14-15-11-7-2.

26 Jul 2012 Sumantra Sarkar

I think there is a bug in the grCycleBasis function. I have a large edge matrix, a part of which is:
2 5
2 7
5 8
5 7
7 11
8 11
8 14
11 15
14 15

Clearly, there are three cycles in this graph. viz. 2-5-7-2, 5-7-11-8-5 and 8-11-15-14-8. However, the function fails to recognize these three cycles individually and returns 2-5-8-7-11-2 and 2-5-8-14-15-11-7-2, completely ignoring the edges 5-7 and {5-7,8-11} respectively. It happens for several other subsets also. Please suggest a solution.
Thank you.
p.s. It calculates the number of cycles correctly though.

12 Mar 2012 Martin  
18 Jan 2012 kira

Hi:
I'm also trying to use grIsmorph, but is asking for function psimilar...
Where can you find this?

18 Nov 2011 Nina  
13 Apr 2011 Adina Stoica

Hi! I am trying to run grTheoryTest for isomorphism (case 12) but it's looking for the function or method psimilar. I googled for the file psimilar.m as well as search this site for it. Help? Please? Pretty please, I need this to work in a week :(
Also, do you know how to do subgraphs? Apart from doing a for while removing and adding various vertices?

28 Mar 2011 kira

Hi, I have a question using grplot...
For my purposes, I need to draw digraphs with 'vplotstyle'='ko'... and I also need that the arrows don't go to the center of the nodes, ie, not to the vertex position, but to the edge of the circles... I'm looking at the code, and I have identified the vector that generates the edges... but I still don't know how to modify them to do what I want... Could you give some clue...
Greetings...

02 Oct 2010 Tianfan XUE

Excellent Job! Thank you very much!

30 Jun 2010 Sergii Iglin

The size of task is determined by the function BINTPROG.

09 Jun 2010 Wang

There is something wrong with grMinVerCover.m and grMinEdgeCover.m when worked in large-scale complex networks(1000 nodes, 2500 edges). The result are both empty cell matrix. But it works well in small-scale networks.
So I want to konw whether there is limited to input data.
Thank you.

19 Apr 2010 Sergii Iglin

>> E=[1 2;1 4;1 5;2 3;2 4;2 5;3 4;3 5;4 5]
E =
1 2
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
>> nMS=grMaxComSu(E)
nMS =
1
2
4
5

30 Mar 2010 Tomaz

I think there is even more serious bug in grMaxComSu.m than Florian suggested.
For example, I forwarded the function following set:
E=[1 2;1 4;1 5;2 3;2 4;2 5;3 4;3 5;4 5]
function returned completely wrong result.

If I don't seriously misunderstand concept of max complete subgraph, the solution should be graph with nodes 1,2,4,5.
However, function suggests non-logical solution: 1,2.
Can somebody please re-test this and confirms the problem or explain to me, where does my logic go wrong?
If somebody already encountered this problem, I would appreciate if she/he would share with us the observation or even a solution.
Sergeii great overall work and it would be really nice to see this bug removed...
Does anybody know any other public file for solving the problem of searching max complete subgraph?

02 Sep 2009 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!

19 Nov 2008 Andrew Jackson  
11 Sep 2008 Chao Wang

good job

26 Aug 2008 rose rose

very good!

19 Aug 2008 li pengfei  
18 Aug 2008 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.

10 Aug 2008 fan fanwen  
23 May 2008 Swamy Korada

Great work

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

07 May 2008 Andi Patombongi  
06 May 2008 jason tharmaraj

can you send me complex networks analysis codes

05 Feb 2008 xm blade

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

19 Oct 2007 xue huiyan

thanks

19 Oct 2007 hiro mano  
28 Sep 2007 gloria macapagal  
21 Aug 2007 Ahmad AbdulWakeel

it is very good toolbox

28 Jun 2007 li yifan china  
22 Jul 2006 wael rashwan  
20 Oct 2005 giu giu

There are some bugs

31 Aug 2005 Pablo Riera

Excellent

25 May 2005 sanith Wijesinghe  
10 Apr 2005 Igor Yegorkin

Beautiful job!

02 Apr 2005 Vlastislav Weiner

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

29 Dec 2004 Zhenya Donchik

I`m very interesting by the theory of managment

13 Dec 2004 Alexandre Felt

Great job, works fine!

14 Jun 2004 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.

12 Mar 2004 ahmed kolsi  
23 Feb 2004 Nick Valuy  
12 Feb 2004 Alex Pesch

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

21 Dec 2003 x s  
Updates

A bug in grPlot is corrected.

24 Dec 2003

Draws the graph and solves the tasks: Maximal Flow, Maximal Matching, Minimal Vertex Cover, Minimal Spanning Tree, Shortest Path etc.

20 Jan 2004

Draws the graph and solves the tasks: Maximal Flow, Maximal Matching, Minimal Vertex Cover, Minimal Spanning Tree, Shortest Path etc.

09 Feb 2004

ShortPath had update for fast calculation

26 Aug 2004

The new e-mail is added

14 Sep 2004

PlotGraph is updated

11 Oct 2004

CycleBasis is updated

28 Mar 2006

All functions are updated, new functions are added.

30 Mar 2006

Summary title is updated

26 Apr 2006

The function grMinAbsEdgeSet are included.

09 May 2006

The grMinSpanTree had update;
two new functions are created.

16 May 2006

The function grPERT is added.

29 Jun 2006

Two new functions is added. One function with bugs is deleted.

05 Jul 2006

Two new functions is added

08 Aug 2006

The function grDecOrd has update.

11 Jul 2009

two new functions are added

09 Nov 2009

Bugs in some functions for work with the isolated vertexes were corrected. Thanks to Marcin Eichner!

30 Jan 2011

New function grShortVerPath is added.

Contact us