Sujet Précédent Sujet Suivant

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

Fermé
medfiras01 Messages postés 3 Date d'inscription mardi 15 août 2017 Statut Membre Dernière intervention 15 août 2017 - Modifié le 15 août 2017 à 16:44
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 - 15 août 2017 à 23:04
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 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
15 août 2017 à 18:56
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 mardi 15 août 2017 Statut Membre Dernière intervention 15 août 2017
15 août 2017 à 21:54
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 mardi 15 août 2017 Statut Membre Dernière intervention 15 août 2017
Modifié le 15 août 2017 à 22:56
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 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
15 août 2017 à 23:04
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
Trouver un nom avec une adresse
lakshmi66 -
Nath01 -

11 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