version 1.3.0.0 (34.3 KB) by
Sergii Iglin

28 functions for different tasks of graph theory

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.

Sergii Iglin (2020). grTheory - Graph Theory Toolbox (https://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox), MATLAB Central File Exchange. Retrieved .

Created with
R14SP1

Compatible with any release

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

handinhandUmit IsikdagAzam BoskabadiHi there,

I used grCycleBasis for a small network of 5 arcs/edges with two loops:

E =[1 2; 1 3; 2 3; 2 4; 3 4];

Cycles=[1 1

1 1

1 0

0 1

0 1]

which detects the second loop consists of Arcs 1,2,4,5 which is wrong!!

The two loops are 1,2,3 and 2,4,5.

Please advise!!

Am I making mistake??

Thank you

Vagif GuseynovFrancois ClemensHi When running grMaxMatch I receive the following messages:

Error using optimset (line 147)

No default options available: the function 'bintprog' does not exist on the path.

Error in grMaxMatch (line 27)

options=optimset('bintprog'); % the default options

Error in grTheoryTest (line 399)

nMM=grMaxMatch(E(:,1:2)); % the maximal matching

Am I missing some toolbox?

regards

Francois Clemens

Standardtrickynesswhat are bases of a digraph? do you mean a basis for it's cycle space?

mohammad javad majidiEmeka EzeanyaIs it possible to use a different number of nodes and degree of nodes apart from the ones given? What if you want to choose a fewer number of nodes?

Sergey KasyanovHan LiI'm trying to use grIsmorph, but is asking for function psimilar...

Where can I find this?

V Lkomalkindly give detail about how to install n use grtheory tool box. given information is not complete. help me please

abishek ganesani have installed this grtheory toolbox

Can anyone tel me how to work with it please

Ahmef Adelgood gooop

sam esadear sir, I would ask if matlab toolbox function have function or program on Binary Decision Diagram algorithm ... thank you

ChenjieLiangMuhammad Abrar AkberMIQP is missing to use grTravSale, How and where to get it?

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

please tell me how to rin this in MATLAB.

Thanks

YonggonSumantra, 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.

Sumantra SarkarI 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.

MartinkiraHi:

I'm also trying to use grIsmorph, but is asking for function psimilar...

Where can you find this?

NinaAdina StoicaHi! 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?

kiraHi, 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...

Tianfan XUEExcellent Job! Thank you very much!

Sergii IglinThe size of task is determined by the function BINTPROG.

WangThere 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.

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

TomazI 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?

Floriandoes 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!

Andrew JacksonChao Wanggood job

rose rosevery good!

li pengfeiTim DavisComment 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.

fan fanwenSwamy KoradaGreat work

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

Andi Patombongijason tharmarajcan you send me complex networks analysis codes

xm bladeGood package it sounds!

One additional question: Could the input be thousands of nodes in one graph?

xue huiyanthanks

hiro manogloria macapagalAhmad AbdulWakeelit is very good toolbox

li yifan chinawael rashwangiu giuThere are some bugs

Pablo RieraExcellent

sanith WijesingheIgor YegorkinBeautiful job!

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

Zhenya DonchikI`m very interesting by the theory of managment

Alexandre FeltGreat job, works fine!

Michael WaisbergThe 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.

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

x s