Création d'une matrice d'adjacence à partir d'un graphe

medfiras01 Messages postés 3 Date d'inscription   Statut Membre Dernière intervention   -  
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   -
Bonjour, Je voudrais savoir comment créer une matrice d'adjacence avec Java (un code) à partir d'un graphe orienté ( graphe sous un fichier graphml)
A voir également:

1 réponse

Réponse 1 / 1
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Bonjour,

Ci-dessous un exemple de fichier GraphML 

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <edge id="e1" source="n0" target="n1"/>
  </graph>
</graphml>

Pour représenter un tel graphe il te faut une matrice de taille 2 (car il y a 2 noeuds : n0 et n1), toutes les valeurs de la matrice sont 0, sauf pour représenter l'arrête e1 (entre n0 et n1) où l'on place une valeur 1.

Remarque : la définition 
<graph id="G" edgedefault="undirected">
indique que l'on est dans le cas particulier d'un graphe non-orienté, donc par symétrie il faudra aussi mettre une valeur 1 entre n1 et n0.

Et des cas particuliers il y en a un certain nombre à gérer avec le format GraphML qui autorise par exemple des sous-graphe, des hypergraphes, etc.
Cela rend le fichier XML plus difficile à analyser de manière exhaustive, mais tu peux aussi te limiter aux usages les plus basiques selon le besoin.
0
medfiras01 Messages postés 3 Date d'inscription   Statut Membre Dernière intervention  
 
en fait le grapheml vient de gephi donc à partir d'un graphe orienté comment je pourrais représenter une matrice d'adjacence (n*n)
0
medfiras01 Messages postés 3 Date d'inscription   Statut Membre Dernière intervention  
 
voici une exemple de grapheml: 
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns">
<key attr.name="label" attr.type="string" for="node" id="label"/>
<key attr.name="Edge Label" attr.type="string" for="edge" id="edgelabel"/>
<key attr.name="weight" attr.type="double" for="edge" id="weight"/>
<key attr.name="Edge Id" attr.type="string" for="edge" id="edgeid"/>
<key attr.name="r" attr.type="int" for="node" id="r"/>
<key attr.name="g" attr.type="int" for="node" id="g"/>
<key attr.name="b" attr.type="int" for="node" id="b"/>
<key attr.name="x" attr.type="float" for="node" id="x"/>
<key attr.name="y" attr.type="float" for="node" id="y"/>
<key attr.name="size" attr.type="float" for="node" id="size"/>
<graph edgedefault="directed">
<node id="0">
<data key="label">1F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-22.43144</data>
<data key="y">-563.1415</data>
</node>
<node id="1">
<data key="label">2F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">42.7488</data>
<data key="y">-299.0222</data>
</node>
<node id="2">
<data key="label">3F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">345.97034</data>
<data key="y">50.132156</data>
</node>
<node id="3">
<data key="label">4F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">274.98978</data>
<data key="y">-213.37892</data>
</node>
<node id="4">
<data key="label">5F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">435.06195</data>
<data key="y">-392.64417</data>
</node>
<node id="5">
<data key="label">6F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">450.8194</data>
<data key="y">341.15085</data>
</node>
<node id="6">
<data key="label">7F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">575.94147</data>
<data key="y">115.72942</data>
</node>
<node id="7">
<data key="label">8F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">550.4859</data>
<data key="y">-150.858</data>
</node>
<node id="8">
<data key="label">9F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">216.41449</data>
<data key="y">-523.51843</data>
</node>
<node id="9">
<data key="label">10F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-107.83949</data>
<data key="y">21.86837</data>
</node>
<node id="10">
<data key="label">11F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">187.95181</data>
<data key="y">257.3524</data>
</node>
<node id="11">
<data key="label">12F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">106.6264</data>
<data key="y">-14.757194</data>
</node>
<node id="12">
<data key="label">13E</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-344.925</data>
<data key="y">-56.778553</data>
</node>
<node id="13">
<data key="label">13F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-277.4842</data>
<data key="y">211.0682</data>
</node>
<node id="14">
<data key="label">14F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-260.86053</data>
<data key="y">-512.34796</data>
</node>
<node id="15">
<data key="label">15F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-217.21619</data>
<data key="y">523.5796</data>
</node>
<node id="16">
<data key="label">16F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-575.7094</data>
<data key="y">-115.64241</data>
</node>
<node id="17">
<data key="label">17E</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-550.0405</data>
<data key="y">149.22021</data>
</node>
<node id="18">
<data key="label">17F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-436.54437</data>
<data key="y">391.2222</data>
</node>
<node id="19">
<data key="label">18F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-188.87279</data>
<data key="y">-259.29034</data>
</node>
<node id="20">
<data key="label">19F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-43.94921</data>
<data key="y">308.40833</data>
</node>
<node id="21">
<data key="label">20E</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">263.32483</data>
<data key="y">508.58838</data>
</node>
<node id="22">
<data key="label">20F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">26.544151</data>
<data key="y">567.8449</data>
</node>
<node id="23">
<data key="label">21F</data>
<data key="size">21.5</data>
<data key="r">0</data>
<data key="g">0</data>
<data key="b">0</data>
<data key="x">-451.00616</data>
<data key="y">-344.7857</data>
</node>
<edge source="0" target="1">
<data key="edgeid">1</data>
<data key="weight">1.0</data>
</edge>
<edge source="0" target="2">
<data key="edgeid">2</data>
<data key="weight">1.0</data>
</edge>
<edge source="1" target="2">
<data key="edgeid">3</data>
<data key="weight">1.0</data>
</edge>
<edge source="0" target="3">
<data key="edgeid">4</data>
<data key="weight">1.0</data>
</edge>
<edge source="2" target="3">
<data key="edgeid">5</data>
<data key="weight">1.0</data>
</edge>
<edge source="0" target="4">
<data key="edgeid">6</data>
<data key="weight">1.0</data>
</edge>
<edge source="3" target="4">
<data key="edgeid">7</data>
<data key="weight">1.0</data>
</edge>
<edge source="1" target="5">
<data key="edgeid">8</data>
<data key="weight">1.0</data>
</edge>
<edge source="2" target="6">
<data key="edgeid">9</data>
<data key="weight">1.0</data>
</edge>
<edge source="3" target="7">
<data key="edgeid">10</data>
<data key="weight">1.0</data>
</edge>
<edge source="4" target="8">
<data key="edgeid">11</data>
<data key="weight">1.0</data>
</edge>
<edge source="1" target="9">
<data key="edgeid">12</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="10">
<data key="edgeid">13</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="11">
<data key="edgeid">14</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="12">
<data key="edgeid">15</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="13">
<data key="edgeid">16</data>
<data key="weight">1.0</data>
</edge>
<edge source="12" target="13">
<data key="edgeid">17</data>
<data key="weight">1.0</data>
</edge>
<edge source="13" target="15">
<data key="edgeid">18</data>
<data key="weight">1.0</data>
</edge>
<edge source="13" target="16">
<data key="edgeid">19</data>
<data key="weight">1.0</data>
</edge>
<edge source="13" target="17">
<data key="edgeid">20</data>
<data key="weight">1.0</data>
</edge>
<edge source="13" target="18">
<data key="edgeid">21</data>
<data key="weight">1.0</data>
</edge>
<edge source="17" target="18">
<data key="edgeid">22</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="19">
<data key="edgeid">23</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="20">
<data key="edgeid">24</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="21">
<data key="edgeid">25</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="22">
<data key="edgeid">26</data>
<data key="weight">1.0</data>
</edge>
<edge source="21" target="22">
<data key="edgeid">27</data>
<data key="weight">1.0</data>
</edge>
<edge source="9" target="23">
<data key="edgeid">28</data>
<data key="weight">1.0</data>
</edge>
</graph>
</graphml>
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Dans ce cas il n'y a que trois types de lignes intéressantes pour ton problème : 

<graph edgedefault="directed">
pour savoir que c'est un graphe orienté (mais si c'est toujours le cas dans gephi on pourrait même s'en passer) 

<node id="0">
qui permet de connaître la taille de ta matrice, dans l'exemple tu as 24 nœuds, donc une matrice 24 lignes et 24 colonnes. 

<edge source="0" target="1">
qui permet de savoir où tu dois mettre les 1 dans ta matrice (ici ligne 0, colonne 1).

Donc tu n'as qu'à lire le fichier ligne par ligne, créer ta matrice dès que tu connais sa taille et la remplir au fur et à mesure...
0

Discussions similaires

Annuaire portable gratuit à partir d'un nom
dani26 -
Authority -

9 réponses
"Vous ne pouvez pas modifier une partie de matrice"
ptéranodon -
ptéranodon -

2 réponses
Trouver un numero de portable a partir d'un nom svp
Hafhoufti -
Babe -

2 réponses
Comment trouver un numéro à partir du nom et prénom
papillon -
guyguy -

10 réponses